Optimal phylogenetic reconstruction

ABSTRACT

One of the major tasks of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on the true evolutionary tree. Given samples from this Markov chain at the leaves of the tree, the goal is to reconstruct the evolutionary tree.It is well known that in order to reconstruct a tree on n leaves, sequences of length Ω(log n) are needed. It was conjectured by M. Steel that for the CFN evolutionary model, if the mutation probability on all edges of the tree is less than p* = (√2-1)/2^3/2, then the tree can be recovered from sequences of length O(log n). This was proven by the second author in the special case where the tree is "balanced". The second author also proved that if all edges have mutation probability larger than p* then the length needed is n^Ω(1). This "phase-transition" in the number of samples needed is closely related to the phase transition for the reconstruction problem (or extremality of free measure) studied extensively in statistical physics, probability and computer science.Here we complete the proof of Steel's conjecture and give a reconstruction algorithm using optimal (up to a multiplicative constant) sequence length. Our results further extend to obtain an optimal reconstruction algorithm for the Jukes-Cantor model with short edges. All reconstruction algorithms run in polynomial time.

REFERENCES

• 1: E. Mossel, Glauber Dynamics onTrees and Hyperbolic Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.568, October 14-17, 2001
• 2: P. M. Bleher, J. Ruiz, and V. A. Zagrebnov. On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice. J. Statist. Phys., 79(1-2):473--482, 1995.
• 3: J. A. Cavender. Taxonomy with confidence. Math. Biosci., 40(3-4), 1978.
• 4: J. Chang. Full reconstruction of markov models on evolutionary trees: identifiability and consistency. Math. Biosci., 137(51--73), 1996.
• 5: Péter L. Erdös , Michael A. Steel , Lázló A. Székely , Tandy J. Warnow, A few logs suffice to build (almost) all trees (l): part I, Random Structures & Algorithms, v.14 n.2, p.153-184, March 1999 [doi>10.1002/(SICI)1098-2418(199903)14:2<153::AID-RSA3>3.0.CO;2-R ]
• 6: W. S. Evans, C. Kenyon, Y. Y. Peres, and L. J. Schulman. Broadcasting on trees and the Ising model. Ann. Appl. Probab., 10(2):410--433, 2000.
• 7: Martin Farach , Sampath Kannan, Efficient algorithms for inverting evolution, Journal of the ACM (JACM), v.46 n.4, p.437-449, July 1999 [doi>10.1145/320211.320212]
• 8: J. S. Farris. A probability model for inferring evolutionary trees. Syst. Zool., 22(4):250--256, 1973.
• 9: J. Felsenstein. Inferring Phylogenies. Sinauer, New York, New York, 2004.
• 10: H. O. Georgii. Gibbs measures and phase transitions, volume 9 of de Gruyter Studies in Mathematics. Walter de Gruyter & Co., Berlin, 1988.
• 11: Y. Higuchi. Remarks on the limiting Gibbs states on a (d+1)-tree. Publ. Res. Inst. Math. Sci., 13(2):335--348, 1977.
• 12: D. Ioffe. On the extremality of the disordered state for the Ising model on the Bethe lattice. Lett. Math. Phys., 37(2):137--143, 1996.
• 13: S. Janson and E. Mossel. Robust reconstruction on trees is determined by the second eigenvalue. Ann. Probab., 32:2630--2649, 2004.
• 14: T. H. Jukes and C. Cantor. Mammalian protein metabolism. In H. N. Munro, editor, Evolution of protein molecules, pages 21--132. Academic Press, 1969.
• 15: F. Martinelli, A. A. Sinclair, and D. Weitz. Glauber dynamics on trees: boundary conditions and mixing time. Comm. Math. Phys., 250(2):301--334, 2004.
• 16: Fabio Martinelli , Alistair Sinclair , Dror Weitz, Fast mixing for independent sets, colorings and other models on trees, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 17: Elchanan Mossel, Recursive reconstruction on periodic trees, Random Structures & Algorithms, v.13 n.1, p.81-97, Aug. 1998 [doi>10.1002/(SICI)1098-2418(199808)13:1<81::AID-RSA5>3.0.CO;2-O ]
• 18: E. Mossel. Reconstruction on trees: beating the second eigenvalue. Ann. Appl. Probab., 11(1):285--300, 2001.
• 19: E. Mossel. Distorted metrics on trees and phylogenetic forests. IEEE Comp. Biol. and Bioinformatics, 2004.
• 20: E. Mossel. Phase transitions in phylogeny. Trans. Amer. Math. Soc., 356(6):2379--2404, 2004.
• 21: E. Mossel and Y. Peres. Information flow on trees. Ann. Appl. Probab., 13(3):817--844, 2003.
• 22: E. Mossel and M. Steel. A phase transition for a random cluster model on phylogenetic trees. Math. Biosci., 187(2):189--203, 2004.
• 23: J. Neyman. Molecular studies of evolution: a source of novel statistical problems. In S. S. Gupta and J. Yackel, editors, Statistical desicion theory and related topics, pages 1--27. 1971.
• 24: C. Semple and M. Steel. Phylogenetics, volume 22 of Mathematics and its Applications series. Oxford University Press, 2003.
• 25: F. Spitzer. Markov random fields on an infinite tree. Ann. Probability, 3(3):387--398, 1975.
• 26: M. Steel. My Favourite Conjecture. http://www.math.canterbury.ac.nz/~mathmas/conjecture.pdf, 2001.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Theory

Keywords:
CFN model, Ising model, Jukes Cantor, phase transitions, phylogenetics, reconstruction problem