Phase transitions in phylogeny

By Elchanan Mossel. Transactions of the American Mathematical Society, 2003

98 citations recorded by the source corpus.

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 e. Motivated by a conjecture by M. Steel, we show that if 2(1 - 2∈) 2 > 1, then for balanced trees, the topology of the underlying tree, having n leaves, can be reconstructed from O(logn) samples (characters) at the leaves. On the other hand, we show that if 2(1 - 2∈) 2 < 1, then there exist topologies which require at least n Ω(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.

Subfields: Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/cf616303da683b11166ef130f69205e9ec4a4e0e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Robust reconstruction on trees is determined by the second eigenvalue (2004, background): “]) and in phylogeny (molecular evolution, see [5, 26] for general background) [27]. Most recently, it is shown that the reconstruction problem is of crucial importance to basic questions in phylogeny [20, 19, 23]. In all of these applications the interest is to ﬁnd when is it possible to reconstruct”