Parallel algorithms for phylogenetic inference under a structured coalescent approximation

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 countries and H5N1 avian influenza across 20 Eurasian regions to finish in a fraction of prior time. This computational efficiency also enables comparison between backward-in-time structured coalescent approximations and forward-in-time phylogeographic methods, revealing that the former provides appropriately conservative posterior estimates, particularly at intermediate phylogenetic depths. We integrate our implementation into the BEAST X and BEAGLE software packages, providing researchers with an accessible and scalable tool for real-time phylogeographic surveillance of rapidly evolving pathogens.