Dynamic Programming Based Approximation Algorithms for Sequence Alignment with Constraints

References

• Altschul S., Gish W. Local alignment statistics. Methods Enzymology (1996) 266:460–480Crossref, Google Scholar
• Altschul S., Gish W., Miller W., Myers E., Lipman J. Basic local alignment search tool. J. Molecular Biol. (1990) 215:413–410Crossref, Google Scholar
• Altschul S., Madden T. L., Schaffer A. A., Zhang J., Zhang Z., Miller W., Lipman D. J. Gapped Blast and Psi-Blast: A new generation of protein database search programs. Nucleic Acids Res. (1997) 25:3389–3402Crossref, Google Scholar
• Arslan A. N., Eğecioğlu Ö. An improved upper bound on the size of planar convex-hulls. Proc. Seventh Internat. Comput. Combin. Conf. (COCOON'01), Guilin, China, Lecture Notes in Computer Science (2001) (Springer-Verlag, Heidelberg, Germany) 111–120No. 2108Crossref, Google Scholar
• Arslan A. N., Eğecioğlu Ö. Approximation algorithms for local alignment with length constraints. Internat. J. Foundations Comput. Sci. (2002) 13:751–767Crossref, Google Scholar
• Arslan A. N., Eğecioğlu Ö., Pevzner P. A. A new approach to sequence comparison: normalized local alignment. Bioinformatics (2001) 17:327–337Crossref, Google Scholar
• Bunke H., Bühler U. Applications of approximate string matching to 2d shape recognition. Pattern Recognition (1993) 26:1797–1812Crossref, Google Scholar
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.Introduction to Algorithms (2001) 2nd ed.(The MIT Press, Cambridge, MA) Google Scholar
• Craven B. D.Fractional Programming (1988) (Helderman Verlag, Berlin, Germany) Google Scholar
• Fitch W. M., Smith T. F. Optimal sequence alignments. Proc. Natl. Acad. Sci. USA (1983) 80:1382–1386Crossref, Google Scholar
• Goad W. B., Kanehisa M. I. Pattern recognition in nucleic acid sequences, I: A general method for finding local homologies and symmetries. Nucleic Acid Res. (1982) 10:247–163Crossref, Google Scholar
• Gusfield D.Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology (1997) (The Press Syndicate of The University of Cambridge, New York) Crossref, Google Scholar
• Gusfield D., Balasubramanian K., Naor D. Parametric optimization of sequence alignment. Algorithmica (1994) 12:312–326Crossref, Google Scholar
• Huang X., Pevzner P. A., Miller W. Parametric recomputing in alignment graph. Proc. Fifth Annual Sympos. Combin. Pattern Matching, Asilomar, California, Lecture Notes in Computer Science (1994) (Springer-Verlag, Hedeilberg, Germany) 87–101No. 807Crossref, Google Scholar
• Lin Y. L., Jiang T., Chao K. M. Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. J. Comput. System Sci. (2002) 65:570–586Crossref, Google Scholar
• Lipman D. J., Pearson W. R. Rapid and sensitive protein searches. Science (1985) 227:1435–1441Crossref, Google Scholar
• Maes M. On a cyclic string-to-string correction problem. Inform. Processing Lett. (1990) 35:73–78Crossref, Google Scholar
• Megiddo N. Combinatorial optimization with rational objective functions. Math. Oper. Res. (1979) 4:414–424Link, Google Scholar
• Sellers P. H. Pattern recognition in genetic sequences by mismatch density. Bull. Math. Biol. (1984) 46:501–504Crossref, Google Scholar
• Smith T. F., Waterman M. S. The identification of common molecular subsequences. J. Molecular Biol. (1981) 147:195–197Crossref, Google Scholar
• Sniedovich M.Dynamic Programming (1992) (Marcel Dekker, New York) Google Scholar
• Uliel S., Fliess A., Amir A., Unger R. A simple algorithm for detecting circular permutations in proteins. Bioinformatics (1999) 15:930–936Crossref, Google Scholar
• Waterman M. S.Introduction to Computational Biology (1995) (Chapman & Hall, London, U.K) Crossref, Google Scholar
• Zhang Z., Berman P., Miller W. Alignments without low-scoring regions. J. Comput. Biol. (1998) 5:197–200Crossref, Google Scholar
• Zhang Z., Berman P., Wiehe T., Miller W. Post-processing long pairwise alignments. Bioinformatics (1999) 15:1012–1019Crossref, Google Scholar