Algorithms for SP-optimal multiple alignments

References

[Alt89] S. F. Altschul. Gap costs for multiple sequence alignment (1989). J. theor. Biol., 138, 297-309. [AW90] Richard Arratia and M.S. Waterman (1994) A phase transition for the score in matching random sequences allowing deletions. {Ann. Appl. Prob., 4, 200-225.

[BLP94] V. Bafna, E. L. Lawler, P. A. Pevzner. Approximation algorithms for multiple sequence alignment (1994) In M. Crochemore and D. Gusfield, editors, Combinatorial Pattern Matching, 5th Annual Symposium, CPM 94, Asilomar, CA, USA, June 5-8, 1994. Proceedings, number 807 in Lecture Notes in Computer Science, pages 43-53, Berlin 1994. Springer Verlag.

[CL88] H. Carillo and D. Lipman. The multiple sequence alignment problem in biology (1988). SIAM J. Appl. Math., 48(5):1073-1082.

[Gus93] D. Gusfield, Efficient methods for multiple sequence alignment with guaranteed error bounds (1993), Bull. Math. Biol., 55, 141-154.

[St98] J. Stoye, Multiple sequence alignment with the divide-and-conquer method (1998), Gene, 211 (2), GC45-GC56.

[Tö96] Udo Tönges, Sören W. Perrey, Jens Stoye and Andreas W.M. Dress, A General Method for Fast Multiple Sequence Alignment (1996). Gene 172 (1), GC33-GC41.

[WJ94] L. Wang and T. Jiang. On the complexity of multiple sequence alignment (1994), Journal of Computational Biology, 1, 337-348.

[WSB76] M. S. Waterman, T. F. Smith and W. A. Beyer. Some biological sequence metrics (1976) Adv. Math, 20, 367-387.