期刊
PROBABILITY THEORY AND RELATED FIELDS
卷 149, 期 1-2, 页码 149-189出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s00440-009-0246-2
关键词
Phylogenetics; CFN model; Ising model; Phase transitions; Reconstruction problem; Jukes-Cantor
资金
- CIPRES (NSF ITR) [NSF EF 03-31494]
- Miller fellowship in Statistics and Computer Science
- Sloan fellowship in Mathematics
- NSF [DMS-0504245, DMS-0528488, DMS-0548249]
- ONR [N0014-07-1-05-06]
- ISF [1300/08]
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [953960] Funding Source: National Science Foundation
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据