Multiple Sequence Alignment as a Facility-Location Problem

References

• Alimonti P., Kann V. Hardness of approximating problems on cubic graphs. Italian Conf. Algorithms Complexity 97, Lecture Notes in Computer Science (1997) (Springer Verlag, Berlin, Germany) 288–298No. 1203Crossref, Google Scholar
• Arkin E. M., Hassin M. Minimum diameter covering problems. Networks (2000) 36:147–155Crossref, Google Scholar
• Arora S., Karger D., Karpinski M. Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. Systems Sci. (1999) 58:193–210Crossref, Google Scholar
• Bafna V., Lawler E. L., Pevzner P. A. Approximation algorithms for multiple sequence alignment. Theoret. Comput. Sci. (1997) 182:233–244Crossref, Google Scholar
• Benner S. A., Cohen M. A., Gonnet G. H. Empirical and structural models for insertions and deletions in the divergent evolution of proteins. J. Molecular Biol. (1993) 229:1065–1082Crossref, Google Scholar
• Bonizzoni P., Della Vedova G. The complexity of multiple alignment with SP-score that is a metric. Theoret. Comput. Sci. (2001) 259:63–79Crossref, Google Scholar
• Chvátal V., Sankoff D., Sankoff D., Kruskal J. B. An upper-bound technique for lengths of common subsequences. Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparisons (1983) (Addison Wesley, Boston, MA) . Chapter 15Google Scholar
• Elias I. Settling the intractability of multiple alignment. Internat. Sympos. Algorithms Comput., Lecture Notes in Computer Science (2003) (Springer-Verlag, Berlin, Germany) 352–363No. 2906Crossref, Google Scholar
• Fitch W. M. Letter to the editor: Commentary on the letter by Ward C. Wheeler. Molecular Biol. Evolution (1993) 10:713–714Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (Freeman, New York) Google Scholar
• Garg N., Konjevod G., Ravi R. A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms (2000) 37:66–84Crossref, Google Scholar
• Gusfield D. Efficient methods for multiple sequence alignment with guaranteed error bounds. Bull. Math. Biol. (1993) 55:141–154Crossref, Google Scholar
• Jiang T., Kearney P., Li M. Some open problems in computational molecular biology. SIGACT News (1999) 30:43–49Crossref, Google Scholar
• Just W. Computational complexity of multiple sequence alignment with SP-score. J. Comput. Biol. (2001) 8:615–623Crossref, Google Scholar
• Just W., Della Vedova G., Balik M., Simanek M. Multiple Sequence Alignment as a Facility Location Problem. Proc. Prague Stringology Club Workshop 2000 (2000) 60–70Collaborative report DC-2000-03. Department of Computer Science and Engineering, Czech Technical University, PragueGoogle Scholar
• Li M., Ma B., Wang L. Finding similar regions in many strings. J. Comput. Systems Sci. (2002) 65:73–96Crossref, Google Scholar
• Manthey B. Non-approximability of weighted multiple sequence alignment. Theoret. Comput. Sci. (2003) 296:179–192Crossref, Google Scholar
• Pascarella S., Argos P. Analysis of insertions/deletions in protein structures. J. Molecular Biol. (1992) 224:461–471Crossref, Google Scholar
• Pevzner P. A. Multiple alignment, communication cost, and graph matchings. SIAM J. Appl. Math. (1992) 52:1763–1779Crossref, Google Scholar
• Sankoff D., Kruskal J. B.Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparisons (1983) (Addison Wesley, Boston, MA) Google Scholar
• Tamir A. A distance constrained p-facility location problem on the real line. Math. Programming (1994) 66:201–204Crossref, Google Scholar
• Wang L., Jiang T. On the complexity of multiple sequence alignment. J. Comput. Biol. (1994) 1:337–348Crossref, Google Scholar
• Wareham H. T. A simplified proof of the NP- and MAX SNP-hardness of multiple sequence tree alignment. J. Comput. Biol. (1995) 2:509–514Crossref, Google Scholar
• Wheeler W. C. Letter to the editor: The triangle inequality and character analysis. Molecular Biol. Evolution (1993) 10:707–712Google Scholar
• Wu B. Y., Lancia G., Bafna V., Chao K.-M., Ravi R., Tang C. Y. A polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM J. Comput. (1999) 29:761–778Crossref, Google Scholar