Title | ||
---|---|---|
Fast Convergence of MCMC Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species |
Abstract | ||
---|---|---|
We prove that a certain Markov chain for phylogenetic reconstruction using
SPR transitions converges quickly to its stationary distribution when the data
is generated from a tree with sufficiently short branch lengths. Our proofs
express the leading terms of the maximum likelihood function of a tree T as a
function of the size of the minimum cut in T needed to realize single edge cuts
of the generating 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 | Venue | Keywords |
---|---|---|
2010 | Clinical Orthopaedics and Related Research | minimum cut,stationary distribution,maximum likelihood,mixture distribution,data structure,markov chain |
Field | DocType | Volume |
Markov chain mixing time,Phylogenetic tree,Markov chain Monte Carlo,Tree rearrangement,Tree (data structure),Markov chain,Algorithm,Segment tree,Mathematics,Interval tree | Journal | abs/1003.5 |
Citations | PageRank | References |
1 | 0.43 | 2 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Daniel Stefankovic | 1 | 243 | 28.65 |
Eric Vigoda | 2 | 747 | 76.55 |