Many-core algorithms for high-dimensional gradients on phylogenetic trees.

Area of Science:

• Computational Biology
• Phylogenetics
• Genomic Data Analysis

Background:

• Estimating phylogenetic model parameters from large genomic datasets is computationally intensive.
• Hamiltonian Monte Carlo (HMC) requires efficient gradient calculations, which traditionally scale poorly with the number of sequences (N).
• Existing CPU implementations of optimized gradient calculations are insufficient for complex models like codon models.

Approach:

• Developed novel, massively parallel algorithms for calculating log-likelihood gradients with respect to branch-length-specific (BLS) parameters.
• Leveraged graphics processing units (GPUs) to achieve significant speedups over CPU-based methods.
• Integrated GPU algorithms into the BEAGLE v4.0.0 library for broad accessibility.

Key Points:

• Achieved >128x speedup for codon models and >8x for nucleotide models compared to CPU implementations.
• Demonstrated feasibility of previously intractable phylogenetic inference, such as estimating West Nile virus introduction timing.
• GPU algorithms enable efficient analysis of large-scale genomic pathogen data.

Conclusions:

• Massively parallel GPU algorithms substantially accelerate phylogenetic inference.
• These advancements make complex evolutionary analyses computationally tractable.
• The implementation in BEAGLE v4.0.0 facilitates wider adoption in phylogenetics research.