next up previous
Next: Appendix Up: Using Traveling Salesman Problem Previous: Discussion


R. Agarwala, V. Bafna, M. Farach, B. Narangyan, M. Paterson, and M. Thorup.
On the approximability of numerical taxonomy: fitting distances with trees.
SIAM J. Comput., pages 365 - 72, 1996.

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

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

L. Cavalli-Sforza and A. Edwards.
Phylogenetic analysis: models and estimation procedures.
Evolution, 32:233 -57, 1967.

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

A. Dress and M. Steel.
Convex tree realization of partitions.
Appl. Math. Lett., 5:3 - 6, 1993.

G. Estabrook, C. Johnson, and F. McMorris.
An idealized concept of the true cladistic character.
Math. Biosciences, 23:263 - 72, 1975.

G. Estabrook, C. Johnson, and F. McMorris.
A mathematical foundation for the analysis of cladistic character compatibility.
Math. Biosciences, 29:181 - 87, 1976.

J. Felsenstein.
Maximum-likelihood estimation of evolutionary trees from continuous characters.
Amer. J. Human Genetics, 25:471-492, 1973.

J. Felsenstein.
The number of evolutionary trees.
Systematic Zoology, 27:401 - 410, 1978.

J. Felsenstein.
Evolutionary trees from gene frequencies and quantitative characters: finding maximum likelihood estimates.
Evolution, 35:1229-1242, 1981.

W.M. Fitch and E. Margoliash.
The construction of phylogenetic trees.
Science, 155:279 - 84, 1967.

Gaston H. Gonnet and Steven A. Benner.
Probabilistic ancestral sequences and multiple alignments.
In Fifth Scandinavian Workshop on Algorithm Theory, Reykjevik July 1996, 1996.

Gaston H. Gonnet, Mark A. Cohen, and Steven A. Benner.
Exhaustive matching of the entire protein sequence database.
Science, 256:1443-1445, 1992.

Gaston H. Gonnet and Chantal 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.

Sandeep K. Gupta, John Kececioglu, and Alejandro 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.

J. Hein.
An optimal algorithm to reconstruct trees from additive distance data.
Bull. Math. Biol., 51:597 - 603, 1989.

P. Hogeweg and P. Hesper.
The alignmen of sets of sequences and the construction of phylogenetic trees: an integrated method.
J. Mol. Evol., 20:175 -86, 1988.

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

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

D.S. 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.

Ch. Korostensky and G. Gonnet.
Gap heuristics and tree construction using gaps.
Technical Report, Inst. of Scientific Computing, ETH Zuerich, 321, 1999.

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.

D. Sankoff.
Minimal mutation trees of sequences.
SIAM J. Appl. Math., 28(35 - 42), 1975.

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

Jeffrey Thorne, Hirohisa Kishino, and Joseph Felsenstein.
Inching toward reality: An improved likelihood model of sequence evolution.
J. Molecular Biology, 34:3-16, 1993.

Chantal Korostensky