A phase transition for a random cluster model on phylogenetic trees
Related Experiment Video
Updated: Aug 7, 2026

A Novel Bayesian Change-point Algorithm for Genome-wide Analysis of Diverse ChIPseq Data Types
Published on: December 10, 2012
1Computer Science and Statistics, University of California, Berkeley, CA, USA. mossel@stat.berkeley.edu
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.
Related Concept Videos
Phylogenetic Trees
Phase Transitions
Phase Transitions: Melting and Freezing
Phylogenetic Trees
Phase Transitions
Microbial Phylogeny

