Paper Info
Title
Fast Convergence of Markov Chain Monte Carlo Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species.
Abstract
This paper studies a Markov chain for phylogenetic reconstruction which uses a popular transition between tree topologies known as subtree pruning-and-regrafting (SPR). We analyze the Markov chain in the simpler setting where the generating tree consists of very short edge lengths, short enough so that each sample from the generating tree (or character in phylogenetic terminology) is likely to have only one mutation, and where there are enough samples so that the data looks like the generating distribution. We prove in this setting that the Markov chain is rapidly mixing, i.e., it quickly converges to its stationary distribution, which is the posterior distribution over tree topologies. Our proofs use that the leading term of the maximum likelihood function of a tree T is the maximum parsimony score, which is the size of the minimum cut in T needed to realize single edge cuts of the generating tree. Our main contribution is a combinatorial proof that, in our simplified setting, SPR moves are guaranteed to converge quickly to the maximum parsimony tree. Our results are in contrast to recent works showing examples with heterogeneous data (namely, the data is generated from a mixture distribution) where many natural Markov chains are exponentially slow to converge to the stationary distribution.
Year
DOI
Venue
2011
10.1137/100790550
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
Field
DocType
phylogeny,maximum likelihood,Bayesian inference,Markov chain Monte Carlo
Discrete mathematics,Combinatorics,Markov chain mixing time,Coupling from the past,Markov property,Markov chain Monte Carlo,Tree rearrangement,Markov model,Markov chain,Algorithm,Variable-order Markov model,Mathematics
Journal
Volume
Issue
ISSN
25
3
0895-4801
Citations 
PageRank 
References 
2
0.50
2
Authors
2
Name
Order
Citations
PageRank
Daniel Stefankovic124328.65
Eric Vigoda274776.55