next up previous
Next: About this document ... Up: Near Optimal Multiple Sequence Previous: The last step


S. Altschul and B. W. Erickson.
Optimal sequence alignment using affine gap costs.
J. Mol. Biol., 48:603 -1 6, 1986.

V. Bafna, E. Lawler, and P. Pevzner.
Approximation algorithms for multiple sequence alignment.
Proc. 5th Symp. on Combinatorial Pattern Matching, pages 43 - 53, 1994.

P. Baldi, Y. Chauvin, T. Hunkapiller, and M. A. McClure.
Hidden markov models of biological primary sequence information.
Proc. Natl. Acad. Sci. USA, 91:1059-1063, 1994.

S. A. Benner, M. A. Cohen, and G. H. Gonnet.
Empirical and structural models for insertions and deletions in the divergent evolution of proteins.
J. Molecular Biology, 229:1065-1082, 1993.

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

M. O. Dayhoff, R. M. Schwartz, and B. C. Orcutt.
A model for evolutionary change in proteins.
In M. O. Dayhoff, editor, Atlas of Protein Sequence and Structure, volume 5, pages 345-352. 1978.

D. Feng and R. F. Doolittle.
Progressive sequence alignment as a prerequisite to correct phylogenetic trees.
J. Mol. Evol., 25:351 - 60, 1987.

L. R. Foulds and R. L. Graham.
The steiner problem in phylogeny is np-complete.
Proc. Natl. Academy Science, 3:43 - 49, 1982.

G. H. Gonnet.
A tutorial introduction to computational biochemistry using Darwin.

G. H. Gonnet, M. A. Cohen, and S. A. Benner.
Exhaustive matching of the entire protein sequence database.
Science, 256:1443-1445, 1992.

G. H. Gonnet and C. Korostensky.
Evaluation measures of multiple sequence alignments.
J. Comp. Biol., 1999.

O. Gotoh.
An improved algorithm for matching biological sequences.
J. Mol. Biol., 162:705-708, 1982.

M. Groetschel and O. Holland.
Solution of large-scale symmetric traveling salesman problems.
Math. Programming, pages 141 - 202, 1991.

S. Gupta, J. Kececioglu, and A. Schaffer.
Making the shortest-paths approach to sum-of-pairs multiple sequence alignment more space efficient in practice.
Proc. 6th Symp. on Combinatorial Pattern Matching, pages 128 - 43, 1995.

S. K. Gupta, J. Kececioglu, and A. A. Schaffer.
Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment.
In J. Computational Biology, 1996.

D. Gusfield.
Efficient methods for multiple sequence alignment with guaranteed error bounds.
Bull. Math. Biol., 55:141 - 54, 1993.

S. Henikoff and J. G. Henikoff.
Amino acid substitution matrices from protein blocks.
Proc. Natl. Academy Science, 89:10915 - 19, 1992.

S. Henikoff and J. G. Henikoff.
Blocks database and its applicatioins.
In R. F. Doolittle, editor, Methods in Enzymology, volume 266 of Computer methods for macromolecular sequence analysis, pages 88 - 105. Academic Press, New York, 1996.

M. Hirosawa, Y. Totoki, M. Hoshida, and M. Ishikawa.
Comprehensive study on iterative algorithms of multiple sequence alignment.
CABIOS, 11(1):13 - 18, 1995.

T. Jiang and L. Wang.
On the complexity of multiple sequence alignment.
J. Comp. Biol., 1:337 - 48, 1994.

T. Jiang, L. Wang, and E. L. Lawler.
Approximation algorithms for tree alignment with a given phylogeny.
Algorithmica, 16:302 - 15, 1996.

D. Johnson.
More approaches to the travelling salesman guide.
Nature, 330:525, December 1987.

D. Johnson.
Local optimization and the traveling salesman problem.
In Proc. 17th Colloq. on Automata, Languages and Programming, volume 443 of Lecture Notes in Computer Science, pages 446 - 461, Berlin, 1990. Springer Verlag.

J. Kececioglu.
The maximum weight trace problem in multiple sequence alignment.
Proc. 4th Symp. on Combinatorial Pattern Matching, pages 106 - 19, 1993.

A. Krogh, M. Brown, I. S. Mian, K. Sjolander, and D. Haussler.
Hidden markov models in computational biology: Applications to protein modeling.
J. Molecular Biology, 235:1501-1531, 1994.

H. Martinez.
A flexible multiple sequence alignment program.
Nucleic Acids Res., 16:1683 - 1691, 1988.

M. McClure, T. Vasi, and W. Fitch.
Comparative analysis of mutliple protein sequence alignment methods.
J. Mol. Biol. Evol, 11(4):571 - 592, 1994.

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

M. Padberg and G. Rinaldi.
A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems.
SIAM Review, 33:60 - 100, 1991.

R. Roui and J. Kececioglu.
Approximation algorithms for multiple sequence alignments under a fixed evolutionary tree.
Discrete Applied Mathematics, pages 355 - 366, 1998.

D. Sankoff and R. Cedergren.
Simultaneous comparison of tree or more sequences related by a tree.
In D. Sankoff and G. Kruskal, editors, Time Warps, String Edits, and Marcomolecules: the Theory and Practice of Seqeunce Comparison, volume 28, pages 253 - 263. Addison Wesley, Reading MA, 1983.

T. F. Smith and M. S. Waterman.
Identification of common molecular subsequences.
J. Mol. Biol., 147:195-197, 1981.

W. Taylor.
Multiple sequence alignment by a pairwise algorithm.
Comput. Appl. Biosci., 3:81 -87, 1987.

W. Taylor.
A flexible method to align a large number of sequences.
J. Mol. Evol., 28:161 - 169, 1988.

J. Thompson, D. Higgins, and T. Gibson.
Clustal w: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice.
Nucleic Acids Research, 22:4673-4680, 1994.

L. Wang and D. Gusfield.
Improved approximation algorithms for tree alignment.
Proc. 7th Symp. on Combinatorial Pattern Matching, pages 220 - 33, 1996.

M. Waterman and M. Perlwitz.
Line geometries for sequence comparison.
Bull. Math. Biol., 46:567 - 577, 1984.

A. Wong, S. Chan, and D. Chiu.
A multiple sequence comparison method.
Society for Mathematical Biology, 55(2):465-486, 1993.

Chantal Korostensky