Near-Optimal Sequence Alignments

Doug Brutlag

October 20, 2009

Altschul, S. F. and Erickson, B. W. (1986). Optimal sequence alignment using affine gap costs. Bull Math Biol, 48, 603-16.

Bellman, R. and Kalaba, R. (1960). On Kth best policies. J. SIAM, 8 (4), 582-588.

Chao, K. M., Hardison, R. C. and Miller, W. (1994). Recent developments in linear-space alignment methods: a survey. J Comput Biol, 1(4), 271-291.

Clarke, S., Krikorian, A. and Rausen, J. (1963). Computing the N best loopless paths in a network. J. SIAM., 11 (4), 1096-1102.

Eddy, S. R. (1995). Multiple alignment using hidden Markov models. Ismb, 3, 114-20.

Fox, B. (1973). Calculating the Kth Shortest Paths. Canadian Journal Operations and Information Processing 11 , 66-70.

Gusfield, D., Balasubramanian, K. and Naor, D. (January 1992). Parametric Optimization of Sequence Alignment. Proceedings of the third annual ACM-SIAM Joint Symposium Discrete Algorithms. Orlando Florida,

Hoffman, W. and Pavley, R. (1959). A Method for the Solution of the Nth Best Path Problem. J. ACM., 6, 506-514.

Lawler, E. L. (1972). A Procedure for Computing the K-best Solutions to Discrete Optimization Problems and its Appplications to the Shortest Paths Problem. Management Science 18 , 401-405.

Naor, D. and Brutlag, D. L. (1993). On Suboptimal Alignments of Biological Sequences.. Fourth International Symposium on Combinatorial Pattern Matching, Padova, Italy: Springer-Verlag, pp. 179-196.

Naor, D. and Brutlag, D. L. (1994). On Near-Optimal Alignments of Biological Sequences. J. Computational Biology 1 (4), 349-366.

Needleman, S. B. and Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48, 443-453.

Perko, A. (1986). Implementation of Algorithms for K shortest loopless paths. Networks, 16, 149-160.

Pollack, M. (1961). The kth Best Route Through A Network. Operations Research 9 (4), 578-580.

Saqi, M. A. S. and Sternberg, M. (1991). A Simple Method to Generate Non-trivial Alternate Alignments of Protein Sequences. J. Mol. Biol., 219, 727-732.

Saqi, M. A. S., Bates, P. and Sternberg, M. J. E. (1992). Towards an automatic method of predicting protein structure by homology: an evaluation of suboptimal sequence alignments. Protein Engineering, 5 (4), 305-311.

Shier, D. R. (1979). On Algorithms for finding the K shortest paths in a Network. Networks, 9, 195-214.

Thiele, R., Zimmer, R., & Lengauer, T. (1995). Recursive dynamic programming for adaptive sequence and structure alignment. Ismb, 3, 384-92.

Vingron, M. and Argos, P. (1990). Determination of reliable regions in protein sequence alignments. Protein Engineering, 3, 565-569.

Vingron, M. (1996). Near-Optimal Sequence Alignment. Current Opinion in Structural Biology, 6(3), 346-252.

Waterman, M. S. (1983). Sequence alignments in the neighborhood of the optimum with general application to dynamic programming. Proc. Nat. Acad. Sci., 80, 3123-3124.

Waterman, M. S. and Byers, T. H. (1985). A dynamic programming algorithm to find all solutions in a neighborhood of the optimum. Math. Biosci., 77, 179-188.

Waterman, M. S., Eggert, M. and Lander, E. (1992). Parametric sequence comparisons. Proc Natl Acad Sci U S A, 89(13), 6090-3.

Waterman, M. S. (1994). Parametric and ensemble sequence alignment algorithms. Bull Math Biol 56 (4), 743-67.

Zuker, M. (1991). Suboptimal Sequence Alignment in Molecular Biology: Alignment with Error Analysis. J. Mol. Biol. 221 , 403-420.

Back to Lecture

Back to Syllabus