Evolutionary trees and the Ising model on the Bethe lattice: A proof of Steel's conjecture

DOI10.1007/S00440-009-0246-2zbMATH Open1221.92063arXivmath/0509575OpenAlexW1989307393WikidataQ122948222 ScholiaQ122948222MaRDI QIDQ718865FDOQ718865

Authors: Constantinos Daskalakis, Elchanan Mossel, Sebastien Roch 

Publication date: 27 September 2011

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on $n$ leaves, sample sequences of length $Omega(logn)$ are needed. It was conjectured by M. Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than $p^{ast}=(sqrt2-1)/2^{3/2}$, then the tree can be recovered from sequences of length $O(logn)$. The value $p^{ast}$ is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel's conjecture 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^{ast}$ then the length needed is $n^{Omega(1)}$. Here we show that Steel's conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from $O(logn)$-length sequences when the mutation probabilities are discretized and less than $p^{a}st$. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.

Full work available at URL: https://arxiv.org/abs/math/0509575

Recommendations

• Optimal phylogenetic reconstruction
• Phase transitions in phylogeny
• A phase transition for a random cluster model on phylogenetic trees.
• Full reconstruction of Markov models on evolutionary trees: identifiability and consistency.
• Phase transition in the sample complexity of likelihood-based phylogeny inference

zbMATH Keywords

phylogeneticsIsing modelphase transitionsreconstruction problemCFN modelJukes-Cantor

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Applications of graph theory (05C90) Problems related to evolution (92D15) Applications of branching processes (60J85) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Phase transitions (general) in equilibrium statistical mechanics (82B26) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Computational methods for problems pertaining to biology (92-08)

Cites Work

• Title not available (Why is that?)
• Gibbs measures and phase transitions
• Broadcasting on trees and the Ising model.
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
• Markov random fields on an infinite tree
• On the extremality of the disordered state for the Ising model on the Bethe lattice
• Full reconstruction of Markov models on evolutionary trees: identifiability and consistency.
• Taxonomy with confidence
• Information flow on trees
• On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
• Reconstruction on trees: Beating the second eigenvalue
• Title not available (Why is that?)
• Glauber dynamics on trees and hyperbolic graphs
• The Ising model and percolation on trees and tree-like graphs
• Optimal phylogenetic reconstruction
• A few logs suffice to build (almost) all trees (I)
• Glauber dynamics on trees: Boundary conditions and mixing time
• Reconstruction on trees and spin glass transition
• A phase transition for a random cluster model on phylogenetic trees.
• Remarks on the limiting Gibbs states on a (d+1)-tree
• Robust reconstruction on trees is determined by the second eigenvalue.
• Phase transitions in phylogeny
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (20)

• The impact and interplay of long and short branches on phylogenetic information content
• Dimensions of group-based phylogenetic mixtures
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• On the uniqueness of Gibbs measure in the Potts model on a Cayley tree with external field
• Fluctuations of the magnetization in the \(p\)-spin Curie-Weiss model
• Species tree estimation under joint modeling of coalescence and duplication: sample complexity of quartet methods
• Tensor recovery in high-dimensional Ising models
• Gibbs measures of Potts model on Cayley trees: a survey and applications
• Optimal phylogenetic reconstruction
• Gibbs-non-Gibbs properties for evolving Ising models on trees
• Title not available (Why is that?)
• Phase transitions in phylogeny
• The `Butterfly effect' in Cayley graphs with applications to genomics.
• Quantum channel simulation of phylogenetic branching models
• Broadcasting on random recursive trees
• Sufficient condition for root reconstruction by parsimony on binary trees with general weights
• On the inference of large phylogenies with long branches: how long is too long?
• Phase transition in the sample complexity of likelihood-based phylogeny inference
• Dynamic Ising model: reconstruction of evolutionary trees
• Combinatorial statistics and the sciences

This page was built for publication: Evolutionary trees and the Ising model on the Bethe lattice: A proof of Steel's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q718865)