Parallel algorithms for phylogenetic inference under a structured coalescent approximation

Area of Science:

• Computational Biology
• Epidemiology
• Evolutionary Biology

Background:

• Accurate spatiotemporal transmission reconstruction is vital for epidemic preparedness.
• Structured coalescent models are used for phylogeographic analysis.
• Existing Bayesian structured coalescent approximation (BASTA) implementations face computational limitations with large datasets.

Purpose of the Study:

• To develop a computationally efficient algorithm for structured coalescent likelihood calculation.
• To enable large-scale phylogeographic analyses of pathogen evolution and spread.
• To provide a scalable tool for real-time pathogen surveillance.

Main Methods:

• Algorithmic restructuring of the structured coalescent likelihood.
• Optimization of memory access and parallelization of computations.
• Integration into BEAST X and BEAGLE software packages.

Main Results:

• The restructured algorithm reduces coalescent likelihood computation by 7-8 fold.
• Parallelization further enhances performance by 10-26 fold.
• Enables large-scale analyses of dengue virus and H5N1 avian influenza.
• Backward-in-time approximations provide conservative posterior estimates.

Conclusions:

• The developed method significantly improves the scalability and speed of phylogeographic analyses.
• This facilitates real-time surveillance of rapidly evolving pathogens.
• The tool enhances epidemic preparedness and response capabilities.