Limitations of Markov chain Monte Carlo algorithms for Bayesian inference of phylogeny

Elchanan Mossel, Eric VigodaThe Annals of Applied Probability 2006 · DOI

Abstract: Markov chain Monte Carlo (MCMC) 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.

Introduction

Bayesian phylogenetic inference has become a cornerstone of modern evolutionary biology, with software like MrBayes widely used to reconstruct the "tree of life" from DNA sequences. These tools rely on Markov chain Monte Carlo (MCMC) algorithms to navigate the vast space of possible tree topologies. A critical assumption is that these chains will "mix" efficiently, reaching the true posterior distribution in a reasonable timeframe. However, Mossel and Vigoda (2005) provide a rigorous theoretical "reality check," demonstrating that popular MCMC algorithms can fail spectacularly under common biological scenarios.

Methods: MCMC Moves and Evolutionary Models

The authors analyze the mixing time of Markov chains using the most common topological "moves":

  • Nearest-Neighbor Interchange (NNI): Swapping adjacent subtrees.
  • Subtree Pruning and Regrafting (SPR): Removing a subtree and reattaching it elsewhere.
  • Tree-Bisection Reconnection (TBR): Breaking an edge and reconnecting the resulting components.
Figure 1: Illustration of Nearest-Neighbor Interchange (NNI) moves on a phylogenetic tree.

These moves are evaluated under standard evolutionary models, such as the Cavender–Farris–Neyman (CFN) binary model and the Jukes–Cantor DNA model. The study focuses on the challenge of mixture data, where different parts of a dataset (e.g., different genes) evolved according to distinct trees—a frequent occurrence due to horizontal gene transfer or incomplete lineage sorting.

Data and Model Construction

The paper uses synthetic data generated from a mixture of two specific 5-leaf unrooted trees, $T_1$ and $T_2$. These trees are constructed with specific branch lengths: internal branches are small ($a$), and terminal branches are even smaller ($a^2$).

Figure 6: The two 5-leaf trees, $T_1$ (left) and $T_2$ (right), used to construct the bimodal likelihood landscape.

The data is a 50/50 mixture where half the characters are generated from $T_1$ and half from $T_2$. The analysis then tracks how the MCMC mixing time scales with the sequence length ($N$).

Results: The Likelihood Valley and Exponential Slowdown

The core finding is that in a mixture setting, the likelihood surface becomes "bimodal." There are two sharp peaks of high probability centered around $T_1$ and $T_2$, separated by a vast "valley" of trees with extremely low likelihood. Standard MCMC moves are "local" and cannot easily jump across this desert.

  • Theorem 1: Exponential Mixing Time. For the 5-leaf mixture model, the mixing time ($T_{mix}$) is at least $c\epsilon \exp(cN)$. This means the time required to reach the stationary distribution grows exponentially with the number of characters ($N$).
  • The Paradox of More Data. Counter-intuitively, increasing the sequence length $N$ makes convergence harder. More data sharpens the peaks and deepens the valley, effectively trapping the MCMC in a local optimum.
  • Robustness. This exponential lower bound is robust across all major transition types (NNI, SPR, TBR) and various biologically realistic mutation models (Jukes-Cantor, Kimura).

Discussion

This work highlights a significant theoretical limitation: MCMC might appear to have converged on one tree while completely missing another equally likely tree in the posterior distribution. While the proof is currently limited to 5-leaf trees, the phenomenon likely persists in larger, more complex phylogenies.

Future research is needed to analyze Metropolis-coupled MCMC ($MC^3$), which uses "heated" chains to jump across likelihood valleys, and to identify specific data distributions where fast convergence can be guaranteed. For now, these results serve as a cautionary note for biologists interpreting Bayesian phylogenetic results from multi-gene datasets.

Summary updated

Abstract

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.
BibTeX
@article{mossel2006limitations,
  author = {Elchanan Mossel and Eric Vigoda},
  title = {{Limitations of Markov chain Monte Carlo algorithms for Bayesian inference of phylogeny}},
  journal = {The Annals of Applied Probability},
  year = {2006},
  doi = {10.1214/105051600000000538},
}
Figure