Parallel algorithms for phylogenetic inference under a structured coalescent approximation

作者：Yucai Shao, Marc A. Suchard, Andrew Rambaut, Xiang Ji, Philippe Lemey, Tetyana I. Vasylyeva, Guy Baele · 发表于：Proceedings of the National Academy of Sciences · 年份：2026 · DOI：10.1073/pnas.2602412123 · 被引用次数：1 · 研究领域：Genomics and Phylogenetic Studies、Evolution and Paleontology Studies、Genetic diversity and population structure

Advances in molecular epidemiology and computational modeling have improved our ability to track pathogen evolution, but accurate reconstruction of spatiotemporal transmission remains essential for epidemic preparedness and response. Structured coalescent models offer a phylogeographic framework by restricting coalescence to lineages within the same deme. Although the Bayesian structured coalescent approximation (BASTA) provides a tractable approach, contemporary phylogeographic analyses involving dozens of localities and hundreds to thousands of genomes exceed the computational capacity of existing implementations. The BASTA likelihood scales cubically with deme count and quadratically with sequence count due to matrix exponentiation and partial likelihood vectors update. Here, we introduce an algorithmic restructuring of the structured coalescent likelihood that eliminates redundancies, optimizes memory access, and exposes parallelization opportunities. Our approach reorganizes computations along three dimensions: i) independent calculation of deme-transition probability matrices across time intervals; ii) simultaneous evaluation of partial likelihood vectors within temporal slices; and iii) concurrent aggregation of coalescent probabilities. Algorithmic restructuring cuts average coalescent likelihood computation by 7 to 8 fold, and parallelization further boosts performance to 10 to 26 fold, enabling joint phylogeographic analyses of dengue virus across 10 South American ...