Evolutionary Trees and the Ising Model on the Bethe Lattice: a Proof of Steel's Conjecture

Details 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

2005-09-23

arxiv.org/abs/math/0509575v3

Mathematics

Probability

Second major revision. Updated proofs and statements

Scientific paper

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 M. Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than $p^{\ast} = (\sqrt{2}-1)/2^{3/2}$, then the tree can be recovered from sequences of length $O(\log n)$. 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(\log n)$-length sequences when the mutation probabilities are discretized and less than $p^\ast$. 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.

Affiliated with

Also associated with

No associations

Rating

Evolutionary Trees and the Ising Model on the Bethe Lattice: a Proof of Steel's Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Evolutionary Trees and the Ising Model on the Bethe Lattice: a Proof of Steel's Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Evolutionary Trees and the Ising Model on the Bethe Lattice: a Proof of Steel's Conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-552934