Phylogeny reconstruction, distinguishing and decision problems
Seminar Room 2, Newton Institute Gatehouse
A widely-studied model for generating binary sequences is to `evolve' them on a tree according to a symmetric Markov process. This model is known as the Cavender-Farris-Neyman model in phylogeny, and the `symmetric binary channel' and the `symmetric 2-state Poisson model' in other areas. The CFN model provides a simple model for the evolution of purine-pyrimidine sequences. The significance of this simple model is, that phenomena shown for the CFN model often extend to more realistic models of sequence evolution. The abstract phylogeny reconstruction problem is telling the true (model) tree from the generated sequences with high probability (whp). We show that under the CFN model distinguishing the true tree from a false one whp, using sequences generated on the true tree, is substantially `easier' (in terms of the sequence length needed) than determining the true tree whp. On the other hand the decision problem whether an input tree is true or false whp is not `easier' than reconstructing the true tree whp. This is joint work with E. Mossell and M. A. Steel.