Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel's conjecture
Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel's conjecture
复制标题
DOI：
10.1007/s00440-009-0246-2
复制
发表时间：
2011-02-01
影响因子：
2
通讯作者：
Roch, Sebastien
中科院分区：
文献类型：
--
作者：
Daskalakis, Constantinos;Mossel, Elchanan;Roch, Sebastien
进化生物学的主要任务是从分子数据中重建系统发育树。进化模型由树上的马尔可夫链给出。给定来自马尔可夫链叶的样品，目标是重建叶片标记的树。众所周知，要重建在n叶上的树，需要长度欧米茄（log n）的样本序列。通过钢提出，对于CFN/ISING进化模型，如果树的所有边缘的突变概率小于p* =（root 2-1）/2（3/2），则可以恢复树从长度o（log n）的序列。值p*由二进制树上自由吉布斯的极端测量的过渡点给出。在树“平衡”的特殊情况下，第二作者证明了钢铁的猜想。第二作者还证明，如果所有边缘的突变概率都大于p*，则所需的长度为n（Omega（1））。在这里，我们表明，当突变概率被离散化并且小于p*时，钢的猜想对于一般树而言是正确的，该算法从O（log n）长度序列中恢复了树。我们的证明和结果表明，自由吉布斯在无限二进制树上的极端性测量，该树概率，统计物理学和计算机科学之前已经研究过，它决定了有限二进制树的Gibbs测量方法。
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.