Random-Effects Substitution Models for Phylogenetics via Scalable Gradient Approximations

Andrew F. Magee, Andrew J. Holbrook, Jonathan E. Pekar, Itzue W. Caviedes-Solis, F. A. Matsen, Guy Baele, Joel O. Wertheim, Xiang Ji, Philippe Lemey, Marc A. SuchardSystematic 2024 · DOI

TL;DR

This paper introduces "random-effects substitution models" that offer a more flexible way to model how biological traits evolve along phylogenetic trees. To make these complex models computationally feasible, they develop a novel, efficient gradient approximation method that speeds up Bayesian inference by over an order of magnitude.

What Problem Does This Paper Address?

Phylogenetic inference, which reconstructs evolutionary relationships, relies on models of how traits (like DNA sequences or geographic locations) change over time. Traditional models, while useful, often make simplifying assumptions about these "substitution processes." For instance, they might assume the rate of change from A to T is the same as from T to A (reversibility). However, real biological processes can be much more complex, with varying rates and directions of change. These more realistic "random-effects substitution models" can capture this complexity but introduce a huge number of parameters, making statistical inference (especially Bayesian inference) computationally intractable. This paper aims to bridge this gap by providing a way to efficiently infer these richer models.

Methods

The core innovation lies in two areas:

  1. Random-Effects Substitution Models: These models extend standard continuous-time Markov chain (CTMC) models. They start with a "base" model (e.g., HKY for DNA) and add "random effects" that allow specific substitution rates to deviate from the base model's assumptions. This allows for capturing phenomena like non-reversibility or context-dependent rates.
  2. Scalable Gradient Approximation: To handle the large number of parameters in random-effects models, the authors derive an efficient approximation to the gradient of the phylogenetic likelihood function. This approximate gradient is crucial for gradient-based inference methods like Hamiltonian Monte Carlo (HMC). They also employ a "Bayesian bridge prior" for regularization, which helps to identify which random effects are truly significant and avoid overfitting.

Datasets

The paper uses three main datasets for evaluation:

  • SARS-CoV-2 genomes: A dataset of 583 sequences to test the model's ability to capture specific mutational biases (like C→T transitions) and non-reversibility.
  • Influenza A virus (H3N2) sequences: 1441 sequences from 14 regions to model phylogeographic spread, testing how well air travel volume predicts dispersal rates.
  • Hylid tree frog traits: Data on arboreality and swimming mode for 29 species to test for dependent evolution between morphological/ecological traits.

Key Insights and Ideas

  • Biological processes are often non-reversible: The SARS-CoV-2 analysis strongly suggests that the assumption of reversibility in substitution models is often violated in reality, leading to biased inferences if ignored.
  • Air travel is a strong predictor of pathogen spread: For influenza, the model found that air travel volume was a remarkably good predictor of dispersal between regions, with random effects only needed for a few specific pairs.
  • Complex models can be computationally tractable: The development of the approximate gradient makes sophisticated, data-rich evolutionary models accessible for inference, which was previously a major bottleneck.
  • Prior choice matters for regularization: The Bayesian bridge prior is effective at shrinking non-significant random effects towards zero, allowing the data to guide model complexity.

Key Results

  • Improved Model Fit: The HKY+RE model (with random effects) provided a significantly better fit to the SARS-CoV-2 data compared to a standard reversible GTR model, as evidenced by posterior predictive checks.
  • Efficient Inference: The HMC algorithm with the approximate gradient was 6.6 to 20.2 times more efficient than standard Metropolis-Hastings MCMC for nucleotide and phylogeographic models, respectively. For the most challenging sampling dimensions, efficiency gains reached 14.8 to 33.6-fold.
  • Significant Biological Findings:
    • Strong evidence for non-reversible C→T and G→T substitutions in SARS-CoV-2.
  • Air travel volume adequately explains most influenza dispersal, with only a few exceptions requiring additional random effects.
  • No significant evidence for arboreality impacting swimming mode in tree frogs.
  • Simulation Performance: Simulations showed that random effects can be accurately estimated, and the posterior sign probability is a reliable indicator of significance, especially for null and strong effects.

Limitations and Future Work

  • Approximation Error: The accuracy of the gradient approximation can decrease with longer branch lengths (more substitutions per branch). While the authors show it performs well even in non-near-perfect regimes and that HMC's accept-reject step mitigates issues, this remains a potential limitation for extremely divergent datasets.
  • GPU Acceleration: The current implementation is CPU-based. The authors suggest that GPU acceleration could lead to substantial speedups, especially for large state-space models.
  • More Complex Models: Extending the approach to handle epoch models (temporally inhomogeneous rates) and models with more complex character dependencies (beyond pairwise interactions) are identified as important future directions.
  • Defining Approximation Regimes: Further research is needed to precisely define the conditions under which the approximation becomes too poor for efficient inference, potentially requiring alternative methods.

Summary updated

Abstract

Phylogenetic and discrete-trait evolutionary inference depend heavily on an appropriate characterization of the underlying character substitution process. In this paper, we present random-effects substitution models that extend common continuous-time Markov chain models into a richer class of processes capable of capturing a wider variety of substitution dynamics. As these random-effects substitution models often require many more parameters than their usual counterparts, inference can be both statistically and computationally challenging. Thus, we also propose an efficient approach to compute an approximation to the gradient of the data likelihood with respect to all unknown substitution model parameters. We demonstrate that this approximate gradient enables scaling of sampling-based inference, namely Bayesian inference via Hamiltonian Monte Carlo, under random-effects substitution models across large trees and state-spaces. Applied to a dataset of 583 SARS-CoV-2 sequences, an HKY model with random-effects shows strong signals of nonreversibility in the substitution process, and posterior predictive model checks clearly show that it is a more adequate model than a reversible model. When analyzing the pattern of phylogeographic spread of 1441 influenza A virus (H3N2) sequences between 14 regions, a random-effects phylogeographic substitution model infers that air travel volume adequately predicts almost all dispersal rates. A random-effects state-dependent substitution model reveals no evidence for an effect of arboreality on the swimming mode in the tree frog subfamily Hylinae. Simulations reveal that random-effects substitution models can accommodate both negligible and radical departures from the underlying base substitution model. We show that our gradient-based inference approach is over an order of magnitude more time efficient than conventional approaches.
BibTeX
@inproceedings{magee2024random,
  author = {Andrew F. Magee and Andrew J. Holbrook and Jonathan E. Pekar and Itzue W. Caviedes-Solis and F. A. Matsen and Guy Baele and Joel O. Wertheim and Xiang Ji and Philippe Lemey and Marc A. Suchard},
  title = {{Random-Effects Substitution Models for Phylogenetics via Scalable Gradient Approximations}},
  booktitle = {Systematic},
  year = {2024},
  doi = {10.1093/sysbio/syae019},
}
Figure