next up previous
Next: About this document ... Up: Evaluation Measures of Multiple Previous: Discussion

Bibliography

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

Altschul and Lipman, 1989
Altschul, S. and Lipman, D. (1989).
Trees, stars, and multiple sequence alignment.
J. Appl. Math., 49:197-209.

Altschul, 1989
Altschul, S. F. (1989).
Gap costs for multiple sequence alignment.
J. theoretical Biology, 138:297-309.

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

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

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

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

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

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

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

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

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

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

Gonnet, 1994a
Gonnet, G. H. (1994a).
New algorithms for the computation of evolutionary phylogenetic trees.
In Suhai, S., editor, Computational Methods In Genome Research, pages 153-161.

Gonnet, 1994b
Gonnet, G. H. (1994b).
A tutorial introduction to computational biochemistry using Darwin.

Gonnet and Benner, 1996
Gonnet, G. H. and Benner, S. A. (1996).
Probabilistic ancestral sequences and multiple alignments.
In Fifth Scandinavian Workshop on Algorithm Theory, Reykjevik July 1996.

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

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

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

Gupta et al., 1995
Gupta, S., Kececioglu, J., and Schaffer, A. (1995).
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.

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

Higgins and Sharp, 1989
Higgins, D. and Sharp, P. (1989).
Fast and sensitive multiple sequence alignments on a microcomputer.
CABIOS, 5:151-153.

Huang, 1994
Huang, X. (1994).
On global sequence alignment.
CABIOS, 10(3):227-235.

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

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

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

Johnson, 1990
Johnson, D. (1990).
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. Springer Verlag.

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

Korostensky and Gonnet, 1999a
Korostensky, C. and Gonnet, G. H. (1999a).
Near optimal multiple sequence alignments using a traveling salesman problem approach.
SPIRE99.
submitted.

Korostensky and Gonnet, 1999b
Korostensky, C. and Gonnet, G. H. (1999b).
Using traveling salesman problem algorithms for evolutionary tree construction.
ISAAC99.
submitted.

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

Lipman et al., 1989
Lipman, D. J., Altschul, S. F., and Kececioglu, J. D. (June 1989).
A tool for multiple sequence alignment.
Proc. Natl. Acad. Sci. USA, 86:4412-4415.

Needleman and Wunsch, 1970
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.

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

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

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

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

Schwarz and Dayhoff, 1979
Schwarz, R. and Dayhoff, M. (1979).
Matrices for detecting distant relationships.
In Dayhoff, M., editor, Atlas of protein sequences, pages 353 - 58. Natl. Biomed. Res. Found.

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

Thompson et al., 1994
Thompson, J., Higgins, D., and Gibson, T. (1994).
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.

Thorne et al., 1993
Thorne, J., Kishino, H., and Felsenstein, J. (1993).
Inching toward reality: An improved likelihood model of sequence evolution.
J. Molecular Biology, 34:3-16.

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


Chantal Korostensky
1999-07-14