Matchings and phylogenetic trees
Abstract
This paper presents a natural coordinate system for phylogenetic trees using a correspondence with the set of perfect matchings in the complete graph. This correspondence produces a distance between phylogenetic trees, and a way of enumerating all trees in a minimal step order. It is useful in randomized algorithms because it enables moves on the space of trees that make random optimization strategies “mix” quickly. It also promises a generalization to intermediary trees when data are not decisive as to their choice of tree, and a new way of constructing Bayesian priors on tree space.
Acknowledgments
We are grateful to Richard Stanley, Phil Hanlon, and Louis Billera for useful feedback on these ideas. P.W.D. acknowledges support from National Science Foundation Grant DMS-9504379, and S.P.H. acknowledges support from a New York State Hatch Grant.
References
1
L R Foulds, R L Graham Adv Appl Math 3, 43–49 (1982).
2
M S Waterman, T F Smith J Theor Biol 73, 789–800 (1978).
3
L Lovasz, M D Plummer Matching Theory (North–Holland, Amsterdam, 1985).
4
P Diaconis, P Hanlon Contemp Math 138, 99–117 (1992).
5
E Schröder Z Math Phys 15, 361–376 (1870).
6
L L Cavalli-Sforza, A W F Edwards Evolution 21, 550–570 (1967).
7
R Stanley Enumerative Combinatorics (Cambridge Univ. Press, Cambridge, U.K.) II (1998).
8
P L Erdös, L A Székely Adv Appl Math 10, 488–496 (1989).
9
J Felsenstein phylip(Phylogeny Inference Package) (Department of Genetics, University of Washington, Seattle, Version 3.5c. (1993).
10
D E Critchlow Metric Methods for Analyzing Partially Ranked Data, Lecture Notes in Statistics (Springer, New York, 1985).
11
F Gray Bell Systems Technical Journal 18, 252 (1939).
12
P W Diaconis, S P Holmes Stat Comput 4, 287–302 (1994).
13
M D Hendy, D Penny Math Biosci 59, 277–290 (1981).
14
A Dress, M Krüger Adv Appl Math 8, 8–37 (1987).
15
D Barker LVB 1.0: Reconstructing Evolution with Parsimony and Simulated Annealing (Daniel Barker, Edinburgh, ). (1997).
16
H Matsuda Pacific Symposium on Biocomputing, eds L Hunter, T E Klein (World Scientific, London), pp. 512–523 (1996).
17
P O Lewis Mol Biol Evol 15, 277–283 (1998).
18
R Brauer Ann Math 38, 857–872 (1937).
19
P Hanlon, D Wales J Algebra 121, 446–476 (1989).
20
Li, S., Pearl, D. K. & Doss, H. (1999) J. Am. Stat. Assoc., in press.
21
Mau, B., Newton, M. A. & Larget, B. (1999) Biometrics, in press.
22
Z Yang, B Rannala Mol Biol Evol 14, 717–724 (1997).
23
matlab (The MathWorks, Inc., Natick, MA, Version 5. (1997).
Information & Authors
Information
Published in
Classifications
Copyright
Copyright © 1998, The National Academy of Sciences.
Submission history
Accepted: September 25, 1998
Published online: December 8, 1998
Published in issue: December 8, 1998
Acknowledgments
We are grateful to Richard Stanley, Phil Hanlon, and Louis Billera for useful feedback on these ideas. P.W.D. acknowledges support from National Science Foundation Grant DMS-9504379, and S.P.H. acknowledges support from a New York State Hatch Grant.
Authors
Metrics & Citations
Metrics
Altmetrics
Citations
Cite this article
Matchings and phylogenetic trees, Proc. Natl. Acad. Sci. U.S.A.
95 (25) 14600-14602,
https://doi.org/10.1073/pnas.95.25.14600
(1998).
Copied!
Copying failed.
Export the article citation data by selecting a format from the list below and clicking Export.
Cited by
Loading...
View Options
View options
PDF format
Download this article as a PDF file
DOWNLOAD PDFLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Personal login Institutional LoginRecommend to a librarian
Recommend PNAS to a LibrarianPurchase options
Purchase this article to access the full text.