  Markov chain Monte Carlo algorithms play a key role in the Bayesian approach
to phylogenetic inference. In this paper, we present the first theoretical work
analyzing the rate of convergence of several Markov chains widely used in
phylogenetic inference. We analyze simple, realistic examples where these
Markov chains fail to converge quickly. In particular, the data studied are
generated from a pair of trees, under a standard evolutionary model. We prove
that many of the popular Markov chains take exponentially long to reach their
stationary distribution. Our construction is pertinent since it is well known
that phylogenetic trees for genes may differ within a single organism. Our
results shed a cautionary light on phylogenetic analysis using Bayesian
inference and highlight future directions for potential theoretical work.
