**1**-
S. Altschul and B. W. Erickson.

Optimal sequence alignment using affine gap costs.*J. Mol. Biol.*, 48:603 -1 6, 1986. **2**-
V. Bafna, E. Lawler, and P. Pevzner.

Approximation algorithms for multiple sequence alignment.*Proc. 5th Symp. on Combinatorial Pattern Matching*, pages 43 - 53, 1994. **3**-
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. **4**-
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. **5**-
H. Carillo and D. Lipman.

The multiple sequence alignment problem in biology.*SIAM J. Appl. Math.*, 48(5):1073-1082, 1988. **6**-
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. **7**-
D. Feng and R. F. Doolittle.

Progressive sequence alignment as a prerequisite to correct phylogenetic trees.*J. Mol. Evol.*, 25:351 - 60, 1987. **8**-
L. R. Foulds and R. L. Graham.

The steiner problem in phylogeny is np-complete.*Proc. Natl. Academy Science*, 3:43 - 49, 1982. **9**-
G. H. Gonnet.

A tutorial introduction to computational biochemistry using Darwin.

1994. **10**-
G. H. Gonnet, M. A. Cohen, and S. A. Benner.

Exhaustive matching of the entire protein sequence database.*Science*, 256:1443-1445, 1992. **11**-
G. H. Gonnet and C. Korostensky.

Evaluation measures of multiple sequence alignments.*J. Comp. Biol.*, 1999.

submitted. **12**-
O. Gotoh.

An improved algorithm for matching biological sequences.*J. Mol. Biol.*, 162:705-708, 1982. **13**-
M. Groetschel and O. Holland.

Solution of large-scale symmetric traveling salesman problems.*Math. Programming*, pages 141 - 202, 1991. **14**-
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. **15**-
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. **16**-
D. Gusfield.

Efficient methods for multiple sequence alignment with guaranteed error bounds.*Bull. Math. Biol.*, 55:141 - 54, 1993. **17**-
S. Henikoff and J. G. Henikoff.

Amino acid substitution matrices from protein blocks.*Proc. Natl. Academy Science*, 89:10915 - 19, 1992. **18**-
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. **19**-
M. Hirosawa, Y. Totoki, M. Hoshida, and M. Ishikawa.

Comprehensive study on iterative algorithms of multiple sequence alignment.*CABIOS*, 11(1):13 - 18, 1995. **20**-
T. Jiang and L. Wang.

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

Approximation algorithms for tree alignment with a given phylogeny.*Algorithmica*, 16:302 - 15, 1996. **22**-
D. Johnson.

More approaches to the travelling salesman guide.*Nature*, 330:525, December 1987. **23**-
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. **24**-
J. Kececioglu.

The maximum weight trace problem in multiple sequence alignment.*Proc. 4th Symp. on Combinatorial Pattern Matching*, pages 106 - 19, 1993. **25**-
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. **26**-
H. Martinez.

A flexible multiple sequence alignment program.*Nucleic Acids Res.*, 16:1683 - 1691, 1988. **27**-
M. McClure, T. Vasi, and W. Fitch.

Comparative analysis of mutliple protein sequence alignment methods.*J. Mol. Biol. Evol*, 11(4):571 - 592, 1994. **28**-
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. **29**-
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. **30**-
R. Roui and J. Kececioglu.

Approximation algorithms for multiple sequence alignments under a fixed evolutionary tree.*Discrete Applied Mathematics*, pages 355 - 366, 1998. **31**-
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. **32**-
T. F. Smith and M. S. Waterman.

Identification of common molecular subsequences.*J. Mol. Biol.*, 147:195-197, 1981. **33**-
W. Taylor.

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

A flexible method to align a large number of sequences.*J. Mol. Evol.*, 28:161 - 169, 1988. **35**-
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. **36**-
L. Wang and D. Gusfield.

Improved approximation algorithms for tree alignment.*Proc. 7th Symp. on Combinatorial Pattern Matching*, pages 220 - 33, 1996. **37**-
M. Waterman and M. Perlwitz.

Line geometries for sequence comparison.*Bull. Math. Biol.*, 46:567 - 577, 1984. **38**-
A. Wong, S. Chan, and D. Chiu.

A multiple sequence comparison method.*Society for Mathematical Biology*, 55(2):465-486, 1993.