×

Matchings and phylogenetic trees. (English) Zbl 0908.92023

Summary: 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.

MSC:

92D15 Problems related to evolution
05C90 Applications of graph theory
05C05 Trees
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] ADV APPL MATH 3 pp 43– (1982) · Zbl 0489.92002
[2] Waterman, Journal of Theoretical Biology 73 (4) pp 789– (1978)
[3] CONTEMP MATH 138 pp 99– (1992)
[4] Z MATH PHYS 15 pp 361– (1870)
[5] Evolution 21 pp 550– (1967)
[6] ADV APPL MATH 10 pp 488– (1989) · Zbl 0723.05046
[7] BELL SYSTEMS TECHNICAL JOURNAL 18 pp 252– (1939)
[8] STAT COMPUT 4 pp 287– (1994)
[9] Mathematical biosciences 59 pp 277– (1981)
[10] ADV APPL MATH 8 pp 8– (1987) · Zbl 0637.92024
[11] Lewis, Molecular Biology and Evolution 15 (3) pp 277– (1998)
[12] ANN MATH 38 pp 857– (1937) · Zbl 0017.39105
[13] J ALGEBRA 121 pp 446– (1989) · Zbl 0695.20027
[14] Yang, Molecular Biology and Evolution 14 (7) pp 717– (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.