Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Phase transitions in phylogeny
HTML articles powered by AMS MathViewer

by Elchanan Mossel PDF
Trans. Amer. Math. Soc. 356 (2004), 2379-2404 Request permission

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
Similar Articles
Additional Information
  • Elchanan Mossel
  • Affiliation: Department of Statistics, Evans Hall, University of California, Berkeley, California 94720-3860
  • MR Author ID: 637297
  • Email: mossel@stat.berkeley.edu
  • 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.
  • © Copyright 2003 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 356 (2004), 2379-2404
  • MSC (2000): Primary 60K35, 92D15; Secondary 60J85, 82B26
  • DOI: https://doi.org/10.1090/S0002-9947-03-03382-8
  • MathSciNet review: 2048522