A phase transition for a random cluster model on phylogenetic trees.
We investigate a simple model that generates random partitions of the leaf set of a tree. Of particular interest is the reconstruction question: what number k of independent samples (partitions) are required to correctly reconstruct the underlying tree (with high probability)? We demonstrate a phase transition for k as a function of the mutation rate, from logarithmic to polynomial dependence on the size of the tree. We also describe a simple polynomial-time tree reconstruction algorithm that applies in the logarithmic region. This model and the associated reconstruction questions are motivated by a Markov model for genomic evolution in molecular biology.
Mossel
Elchanan
E
Computer Science and Statistics, University of California, Berkeley, CA, USA. mossel@stat.berkeley.edu
Steel
Mike
M
D016000:Cluster Analysis; D019143:Evolution, Molecular; D008390:Markov Chains; D008957:Models, Genetic; D010802:Phylogeny