title: A phase transition for a random cluster model on phylogenetic trees.
abstract: 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.
authors.affiliation: Computer Science and Statistics, University of California, Berkeley, CA, USA. mossel@stat.berkeley.edu
authors.forename: Elchanan
authors.initials: E
authors.lastname: Mossel
authors.forename: Mike
authors.initials: M
authors.lastname: Steel
mesh_terms: D016000:Cluster Analysis; D019143:Evolution, Molecular; D008390:Markov Chains; D008957:Models, Genetic; D010802:Phylogeny