Gradients Do Grow on Trees: A Linear-Time O(N)-Dimensional Gradient for Statistical Phylogenetics
Gradients Do Grow on Trees: A Linear-Time O(N)-Dimensional Gradient for Statistical Phylogenetics
复制标题
DOI：
10.1093/molbev/msaa130
复制
发表时间：
2020-10-01
影响因子：
10.7
通讯作者：
Suchard, Marc A.
中科院分区：
文献类型：
--
作者：
Ji, Xiang;Zhang, Zhenyu;Suchard, Marc A.
对数似然的计算是许多统计系统发育算法的计算瓶颈。更糟糕的是它的梯度评估，通常用于针对高概率区域。基于标准剪枝算法的O（N）维梯度计算需要O（N-2）次运算，其中N是采样分子序列的数量。随着高通量测序的出现，最近的系统发育研究已经分析了数百到数千个序列，由于技术的进步，数据集明显趋向于更大。这种大规模的分析挑战系统发育重建，需要推断更大的过程参数集，以模拟不断增加的数据异质性。为了使这些分析易于处理，我们提出了一个线性时间算法的O（N）维梯度评估和应用它一般连续时间马尔可夫过程的序列替换的系统发育树，而不需要假设平稳性或可逆性。我们应用这种方法来学习三种致病病毒的分支特异性进化速率：西尼罗河病毒，登革热病毒和拉沙病毒。我们提出的算法显着提高了推理效率，最大似然优化增加了126至234倍，贝叶斯框架中的计算性能增加了16至33倍。
Calculation of the log-likelihood stands as the computational bottleneck for many statistical phylogenetic algorithms. Even worse is its gradient evaluation, often used to target regions of high probability. Order O(N)-dimensional gradient calculations based on the standard pruning algorithm require O(N-2) operations, where N is the number of sampled molecular sequences. With the advent of high-throughput sequencing, recent phylogenetic studies have analyzed hundreds to thousands of sequences, with an apparent trend toward even larger data sets as a result of advancing technology. Such large-scale analyses challenge phylogenetic reconstruction by requiring inference on larger sets of process parameters to model the increasing data heterogeneity. To make these analyses tractable, we present a linear-time algorithm for O(N)-dimensional gradient evaluation and apply it to general continuous-time Markov processes of sequence substitution on a phylogenetic tree without a need to assume either stationarity or reversibility. We apply this approach to learn the branch-specific evolutionary rates of three pathogenic viruses: West Nile virus, Dengue virus, and Lassa virus. Our proposed algorithm significantly improves inference efficiency with a 126- to 234-fold increase in maximum-likelihood optimization and a 16- to 33-fold computational performance increase in a Bayesian framework.