CPU Parallelization Accelerates Pathogen Phylogeographic Inference with a Structured Coalescent Approximation

Computational bottlenecks in inferring movement between regions
A study published in PNAS redesigned computation for a structured coalescent approximation used to infer pathogen spread between regions, accelerating likelihood calculations 10–26-fold over the previous implementation. The researchers used multicore central processing units (CPUs) and also reduced total analysis time in dengue and avian influenza datasets.
Structured coalescent models infer phylogenies and movement histories from genomic data while accounting for regional subpopulations and migration between them. They reflect the condition that, going backward in time, lineages can coalesce into a common ancestor only when they belong to the same subpopulation. However, an exact model that accounts for all unobserved migration histories is computationally difficult to run on large datasets.
The Bayesian structured coalescent approximation (BASTA) reduces this burden, but likelihood calculations in the previous implementation include operations that scale with the cube of the number of regions and the square of the number of sequences. Even with an approximate model, a computational bottleneck remained when analyzing dozens of regions alongside hundreds to thousands of genomes.
Effects of eliminating redundant calculations and CPU parallelization
The researchers stored intermediate values for reuse and improved memory access. They then parallelized the calculation of regional transition probability matrices for each time interval, updates to partial likelihood vectors within each interval, and aggregation of interval-specific likelihood contributions. The implementation was integrated into BEAST X and the high-performance computing library BEAGLE.
The algorithmic redesign alone made serial execution an average of 7–8 times faster; adding CPU parallelization brought the total speedup to 10–26-fold, depending on the comparison conditions. The comparator was BASTA in BEAST 2.7.7. These figures came from the average likelihood calculation time over 400 iterations in a Markov chain Monte Carlo (MCMC) run that held the phylogenetic tree, branch lengths, and population sizes fixed while updating only the migration-rate matrix. They do not mean that every full analysis will be faster by the same factor.
In a real-data analysis, the researchers used 287 dengue virus serotype 1 genomes from 10 South American regions. Reaching an effective sample size (ESS) above 100 for all parameters took more than 7 days with the previous implementation and about 1.5 days with the new implementation using 2 CPU cores. ESS indicates how many independent samples would contain the same amount of information as the correlated MCMC samples. In an analysis of 192 H5N1 hemagglutinin (HA) gene sequences from 20 Eurasian regions, the new implementation using 2 CPU cores achieved adequate ESS in about one-third of a day. The previous implementation took more than 5 days, and the researchers reported ESS values above 200 for the main parameters in this analysis.
Uncertainty in location inference remains despite faster analysis
On real data, the backward-time structured coalescent approximation distributed ancestral-location posterior probabilities more broadly across regions than a forward-time phylogeographic model. The two methods were similar in the major periods and broad patterns of spread, but differed in how certain they were about the region of origin of a specific ancestor. A broad posterior distribution reveals uncertainty about location; by itself, it does not establish the accuracy of the inferred migration route.
The speedup also did not remove bias from the approximation’s assumptions. BASTA uses the state-independent structured coalescent approximation (SISCO), which assumes that between events each lineage’s location state changes according to migration rates, independently of other lineages and the coalescent process. This can bias estimates of migration rates or ancestral locations. The paper reports that, given sufficient runtime, the posterior distributions from the new and previous implementations were essentially the same; this should be distinguished from the accuracy of the approximate model itself.
Increasing the number of threads does not always improve speed. When the number of threads was large relative to the dataset, management overhead and memory constraints reduced performance. A graphics processing unit (GPU) implementation is under development, and the study did not validate capabilities for updating phylogenies as data arrive or predicting spread.
Source: PNAS paper, with the provided open full text from Europe PMC.
Proceedings of the National Academy of Sciences, Volume 123, Issue 18, May 2026. SignificanceTimely reconstruction of epidemic dynamics is essential for public health, and structured coalescent models constitute an essential tool for this purpose. However, statistical and computational challenges pose a critical barrier to their ...
Research teams analyzing pathogen genomes can use the CPU implementation in BEAST X and BEAGLE to reduce the computational burden of evaluating hypotheses about movement between regions. For example, when analyzing dengue sequences from multiple regions, they could use a short trial run to choose an appropriate number of threads, then check MCMC convergence and compare probabilities for ancestral locations. This creates more room for repeated analyses and uncertainty assessment within the same computing budget. Bias arising from uneven sampling or approximation assumptions remains, however, even when calculations are faster. Results should be interpreted as possible histories of spread and their uncertainty; improvements to public-health responses or patient benefit were not outcomes directly assessed in this study.