Parallel algorithms for phylogenetic inference under a structured coalescent approximation.

Area of Science:

• Computational biology
• Epidemiology
• Genomics

Background:

• Accurate spatiotemporal transmission dynamics are crucial for epidemic preparedness and outbreak response.
• Structured coalescent models provide a phylogeographic framework but face computational limitations with large datasets.
• Existing Bayesian structured coalescent approximation (BASTA) implementations struggle with numerous geographic locations and viral genomes.

Purpose of the Study:

• To enhance the computational efficiency of structured coalescent models for phylogeographic analysis.
• To enable large-scale phylogeographic studies of rapidly evolving pathogens.
• To provide a scalable and accessible tool for real-time pathogen surveillance.

Main Methods:

• Algorithmic restructuring of the structured coalescent likelihood to optimize computations.
• Implementation of parallelization techniques to accelerate calculations.
• Integration of the improved method into BEAST X and BEAGLE software packages.

Main Results:

• Achieved a 7-8 fold reduction in average coalescent likelihood computation time through algorithmic restructuring.
• Further boosted performance by 10-26 fold with parallelization.
• Enabled timely phylogeographic analyses of dengue virus and H5N1 avian influenza across multiple countries and regions.
• Demonstrated that backward-in-time approximations yield conservative posterior estimates.

Conclusions:

• The enhanced structured coalescent method significantly improves computational efficiency for phylogeographic analyses.
• This advancement facilitates large-scale pathogen surveillance and outbreak response.
• The integrated software provides researchers with a powerful tool for studying pathogen evolution and spread.