Department of Biomathematics, David Geffen School of Medicine at UCLA, University of California, Los Angeles, Los Angeles, CA, United States.
Department of Mathematics, School of Science & Engineering, Tulane University, New Orleans, LA, United States.
Bioinformatics. 2024 Feb 1;40(2). doi: 10.1093/bioinformatics/btae030.
Advancements in high-throughput genomic sequencing are delivering genomic pathogen data at an unprecedented rate, positioning statistical phylogenetics as a critical tool to monitor infectious diseases globally. This rapid growth spurs the need for efficient inference techniques, such as Hamiltonian Monte Carlo (HMC) in a Bayesian framework, to estimate parameters of these phylogenetic models where the dimensions of the parameters increase with the number of sequences N. HMC requires repeated calculation of the gradient of the data log-likelihood with respect to (wrt) all branch-length-specific (BLS) parameters that traditionally takes O(N2) operations using the standard pruning algorithm. A recent study proposes an approach to calculate this gradient in O(N), enabling researchers to take advantage of gradient-based samplers such as HMC. The CPU implementation of this approach makes the calculation of the gradient computationally tractable for nucleotide-based models but falls short in performance for larger state-space size models, such as Markov-modulated and codon models. Here, we describe novel massively parallel algorithms to calculate the gradient of the log-likelihood wrt all BLS parameters that take advantage of graphics processing units (GPUs) and result in many fold higher speedups over previous CPU implementations.
We benchmark these GPU algorithms on three computing systems using three evolutionary inference examples exploring complete genomes from 997 dengue viruses, 62 carnivore mitochondria and 49 yeasts, and observe a >128-fold speedup over the CPU implementation for codon-based models and >8-fold speedup for nucleotide-based models. As a practical demonstration, we also estimate the timing of the first introduction of West Nile virus into the continental Unites States under a codon model with a relaxed molecular clock from 104 full viral genomes, an inference task previously intractable.
We provide an implementation of our GPU algorithms in BEAGLE v4.0.0 (https://github.com/beagle-dev/beagle-lib), an open-source library for statistical phylogenetics that enables parallel calculations on multi-core CPUs and GPUs. We employ a BEAGLE-implementation using the Bayesian phylogenetics framework BEAST (https://github.com/beast-dev/beast-mcmc).
高通量基因组测序的进步以前所未有的速度提供了基因组病原体数据，使统计系统发生学成为监测全球传染病的关键工具。这种快速增长促使人们需要高效的推断技术，例如贝叶斯框架中的哈密顿蒙特卡罗（HMC），以便估计这些系统发生模型的参数，其中参数的维度随着序列数 N 的增加而增加。HMC 需要反复计算数据对数似然相对于所有分支长度特定（BLS）参数的梯度，传统上使用标准修剪算法需要 O(N2) 次运算。最近的一项研究提出了一种在 O(N) 中计算此梯度的方法，使研究人员能够利用基于梯度的采样器，如 HMC。该方法的 CPU 实现使基于核苷酸的模型的梯度计算具有计算可行性，但在更大状态空间大小模型（如 Markov 调制和密码子模型）中性能欠佳。在这里，我们描述了利用图形处理单元（GPU）计算所有 BLS 参数的对数似然梯度的新的大规模并行算法，这些算法的速度比以前的 CPU 实现快许多倍。
我们使用三个计算系统在三个进化推断示例中对这些 GPU 算法进行基准测试，这些示例探索了来自 997 种登革热病毒、62 种食肉动物线粒体和 49 种酵母的完整基因组，对于基于密码子的模型，我们观察到比 CPU 实现快 128 倍以上，对于基于核苷酸的模型则快 8 倍以上。作为实际演示，我们还根据放松分子钟的密码子模型，从 104 个完整病毒基因组中估计西尼罗河病毒首次引入美国大陆的时间，这是以前无法解决的推断任务。
我们在 BEAGLE v4.0.0 中提供了我们的 GPU 算法的实现（https://github.com/beagle-dev/beagle-lib），这是一个用于统计系统发生学的开源库，它支持多核 CPU 和 GPU 上的并行计算。我们在 BEAST（https://github.com/beast-dev/beast-mcmc）的贝叶斯系统发生学框架中使用 BEAGLE 实现。
