Optimal Solutions for the Closest-String Problem via Integer Programming

References

• Ben-Dor A., Lancia G., Perone J., Ravi R., Apostolico A., Hein J. Banishing bias from consensus sequences. Proc. Eighth Annual Sympos. Combin. Pattern Matching, Aarhus, Denmark, Lecture Notes in Computer Science (1997) (Springer-Verlag, Heidelberg, Germany) 247–261No. 1264Crossref, Google Scholar
• Downey R. G., Fellows M. R.Parameterized Complexity (1999) (Springer-Verlag, Heidelberg, Germany) Crossref, Google Scholar
• Frances M., Litman A. On covering problems of codes. Theoret. Comput. System (1997) 30:113–119Crossref, Google Scholar
• Gasieniec L., Jansson J., Lingas A. Efficient approximation algorithms for the Hamming center problem. Proc. Tenth ACM-SIAM Sympos. Discrete Algorithms, Baltimore, Maryland (1999) (Society for Industrial and Applied Mathematics, Philadelphia, PA) S905–Google Scholar
• Gramm J., Niedermeier R., Rossmanith P. Exact solutions for closest string and related problems. Proc. Twelfth Annual Internat. Sympos. Algorithms Comput. (ISAAC 2001), Lecture Notes in Computer Science (2001) (Springer-Verlag, Heidelberg, Germany) 441–452No. 2223Crossref, Google Scholar
• Hertz G., Stormo G. Identification of consensus patterns in unaligned DNA and protein sequences: A large-deviation statistical basis for penalizing gaps. Lim, Cantor, eds. Proc. Third Internat. Conf. Bioinformatics Genome Res. (1995) (World Scientific, Singapore) 201–216Google Scholar
• ILOG Inc.CPLEX 8.1 User's Manual (2003) (ILOG, Incline Village, NV, USA) Google Scholar
• Lanctot K., Li M., Ma B., Wang S., Zhang L. Distinguishing string selection problems. Inform. Comput. (2003) 185:41–55Crossref, Google Scholar
• Lee E., Mitchell J., Floudas C., Pardalos P. Integer programming: Branch and bound methods. Encyclopedia of Optimization (2001) 2(Kluwer Academic Publishers, Dordrecht, Netherlands) 509–519Crossref, Google Scholar
• Li M., Ma B., Wang L. Finding similar regions in many strings. Proc. Thirty First Annual ACM Sympos. Theory Comput. (1999) (ACM Press, Atlanta, GA) 473–482Crossref, Google Scholar
• Li M., Ma B., Wang L. On the closest string and substring problems. J. ACM (2002) 49:157–171Crossref, Google Scholar
• McClure M., Vasi T., Fitch W. Comparative analysis of multiple protein-sequence alignment methods. Mol. Biol. Evol. (1994) 11:571–592Google Scholar
• Park S., Miller K. Random number generators: Good ones are hard to find. Comm. ACM (1988) 31:1192–1201Crossref, Google Scholar
• Rajasekaran S., Hu Y., Luo J., Nick H., Pardalos P., Sahni S., Shaw G. Efficient algorithms for similarity search. J. Combin. Optim. (2001a) 5:125–132Crossref, Google Scholar
• Rajasekaran S., Nick H., Pardalos P., Sahni S., Shaw G. Efficient algorithms for local alignment search. J. Combin. Optim. (2001b) 5:117–124Crossref, Google Scholar
• Roman S.Coding and Information Theory. Graduate Texts in Mathematics (1992) (Springer-Verlag, Heidelberg, Germany) . No. 134Google Scholar
• Stojanovic N., Berman P., Gumucio D., Hardison R., Miller W. A linear-time algorithm for the 1-mismatch problem. Workshop on Algorithms and Data Structures, Halifax, Nova Scotia, Canada, Lecture Notes in Computer Science (1997) (Springer-Verlag, Heidelberg, Germany) 126–135No. 1272Crossref, Google Scholar
• Stormo G., Hartzell G. Identifying protein-binding sites from unaligned DNA fragments. Proc. National Acad. Sci. USA (1991) 88:5699–5703Crossref, Google Scholar