Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Phase transitions in phylogeny


Author: Elchanan Mossel
Journal: Trans. Amer. Math. Soc. 356 (2004), 2379-2404
MSC (2000): Primary 60K35, 92D15; Secondary 60J85, 82B26
Published electronically: October 28, 2003
MathSciNet review: 2048522
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We apply the theory of Markov random fields on trees to derive a phase transition in the number of samples needed in order to reconstruct phylogenies.

We consider the Cavender-Farris-Neyman model of evolution on trees, where all the inner nodes have degree at least $3$, and the net transition on each edge is bounded by $\epsilon$. Motivated by a conjecture by M. Steel, we show that if $2 (1 - 2 \epsilon)^2 > 1$, then for balanced trees, the topology of the underlying tree, having $n$ leaves, can be reconstructed from $O(\log n)$ samples (characters) at the leaves. On the other hand, we show that if $2 (1 - 2 \epsilon)^2 < 1$, then there exist topologies which require at least $n^{\Omega(1)}$ samples for reconstruction.

Our results are the first rigorous results to establish the role of phase transitions for Markov random fields on trees, as studied in probability, statistical physics and information theory, for the study of phylogenies in mathematical biology.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 60K35, 92D15, 60J85, 82B26

Retrieve articles in all journals with MSC (2000): 60K35, 92D15, 60J85, 82B26


Additional Information

Elchanan Mossel
Affiliation: Department of Statistics, Evans Hall, University of California, Berkeley, California 94720-3860
Email: mossel@stat.berkeley.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-03-03382-8
PII: S 0002-9947(03)03382-8
Keywords: Phylogeny, phase transition, Ising model
Received by editor(s): May 21, 2002
Received by editor(s) in revised form: April 10, 2003
Published electronically: October 28, 2003
Additional Notes: The author was supported by a Miller Fellowship. Most of the research reported here was conducted while the author was a PostDoc in theory group, Microsoft Research.
Article copyright: © Copyright 2003 American Mathematical Society