BEAGLE in Action: Phylogenetic Likelihoods for Very Large State Spaces
Abstract
Computing phylogenetic likelihoods becomes challenging when the continuous-time Markov chain has a large state space. At each branch, pruning algorithms require terms of the form eQ t· B, where Q is an S × S rate matrix (e.g., for S states), t is a branch length, and the columns of matrix B (e.g., B ∈ ℝ+S × L) are partial-likelihood vectors for L site patterns. Many implementations calculate the dense transition matrix P(t)=eQ t via eigendecomposition and multiply it by B. This strategy is efficient for small state spaces, but it can be inefficient for large sparse rate matrices because forming P(t) or its eigen vector matrices destroys sparsity and its cost may not be well amortized when L is small. We implement an alternative likelihood kernel based on the Al-Mohy and Higham (2011) algorithm for computing the action of the matrix exponential directly, avoiding explicit construction of P(t) or its eigen vector matrices. The resulting method takes full advantage of the sparsity of Q. We implement this method as a CPU-based extension to the BEAGLE library and evaluate it on two large-state molecular models: a Markov-modulated codon model of heterotachy with M selective regimes and 61· M possible states, and a codon-pair model of interlocus gene conversion between two paralogs with 612=3 721 possible states. Our results characterize when action-based likelihood computation improves performance over calculating eQ t directly. We show that this method enables fast, scalable inference for complex models, removing a key computational barrier to the study of evolution with large state space models.
Related
- DIMPLE: A Tree-Guided Divide-and-Conquer Framework for ILS-Aware Phylogenetic Network Inference on Large-Scale Data
- Active Visual Semantics: A large-scale MEG and eye-tracking dataset for understanding visual intelligence in action
- Shank3 mutation disrupts affective touch encoding in the dorsal medial prefrontal cortex of Beagle dogs
- Evaluation and primer for using DeepLabCut to track small animals in large spaces
- Recovery-Directed Symbolic Distillation of Neural Likelihoods
BibTeX
@misc{redelings2026beagle,
title = {{BEAGLE in Action: Phylogenetic Likelihoods for Very Large State Spaces}},
author = {Benjamin D Redelings and April Wright and Karthik Gangavarapu and Yucai Shao and Filippo Monti and Wu-Min Deng and Shuo Su and Andrew Rambaut and Guy Baele and Philippe Lemey and Marc A. Suchard and Xiang Ji},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03873},
eprint = {2611.03873},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03873},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - BEAGLE in Action: Phylogenetic Likelihoods for Very Large State Spaces
AU - Benjamin D Redelings
AU - April Wright
AU - Karthik Gangavarapu
AU - Yucai Shao
AU - Filippo Monti
AU - Wu-Min Deng
AU - Shuo Su
AU - Andrew Rambaut
AU - Guy Baele
AU - Philippe Lemey
AU - Marc A. Suchard
AU - Xiang Ji
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03873
UR - https://arxiv.org/abs/2611.03873
AB - Computing phylogenetic likelihoods becomes challenging when the continuous-time Markov chain has a large state space. At each branch, pruning algorithms require terms of the form e^Q t· B, where Q is an S × S rate matrix (e.g., for S states), t is a branch length, and the columns of matrix B (e.g., B ∈ ℝ_+^S × L) are partial-likelihood vectors for L site patterns. Many implementations calculate the dense transition matrix P(t)=e^Q t via eigendecomposition and multiply it by B. This strategy is efficient for small state spaces, but it can be inefficient for large sparse rate matrices because forming P(t) or its eigen vector matrices destroys sparsity and its cost may not be well amortized when L is small. We implement an alternative likelihood kernel based on the Al-Mohy and Higham (2011) algorithm for computing the action of the matrix exponential directly, avoiding explicit construction of P(t) or its eigen vector matrices. The resulting method takes full advantage of the sparsity of Q. We implement this method as a CPU-based extension to the BEAGLE library and evaluate it on two large-state molecular models: a Markov-modulated codon model of heterotachy with M selective regimes and 61· M possible states, and a codon-pair model of interlocus gene conversion between two paralogs with 61^2=3 721 possible states. Our results characterize when action-based likelihood computation improves performance over calculating e^Q t directly. We show that this method enables fast, scalable inference for complex models, removing a key computational barrier to the study of evolution with large state space models.
ER -