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

• 成果类型: Article
• 署名作者: Daskalakis, Constantinos; Mossel, Elchanan; Roch, Sebastien
• 署名单位: University of California System; University of California Los Angeles; Massachusetts Institute of Technology (MIT); University of California System; University of California Berkeley; Weizmann Institute of Science
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-009-0246-2
• 发表日期: 2011
• 页码: 149-189
• 关键词: glauber dynamics; reconstruction; TRANSITION; graphs; state

摘要

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 (log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than p* = (root 2 - 1)/2(3/2), then the tree can be recovered from sequences of length O(log n). The value p* 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* 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(log n)-length sequences when the mutation probabilities are discretized and less than p*. 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.