RAxML: A Parallel Program for Phylogenetic Tree Inference
RAxML: A Parallel Program for Phylogenetic Tree Inference
复制标题
RAxML：系统发育树推理的并行程序
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
T. Ludwig
中科院分区：
文献类型：
--
作者：
A. Stamatakis;H. Meier;T. Ludwig
基于最大似然标准的大型系统发育树的计算极其昂贵。我们提出了一种新的、部分随机的并行算法来重建大型系统发育树，该算法可以在更短的时间内产生同样好甚至更好的树。我们提供包含来自不同来源的 150 至 1000 个序列的初步比对结果。第一个结果表明，我们进行的实验的运行时间比 PAxML 至少提高了 2 倍。 1.随机A(x)加速最大似然简介：在之前的工作[8][7]中，我们引入了子树相等向量（SEV），用于显着加速基于最大似然的系统发育程序的拓扑评估函数。我们在 PAxML（并行 A(x) 加速最大似然）中实现了 SEV，它源自并行 fastDNAml [9]。与并行 fastDNAml 相比，PAxML 的运行时间缩短了约 25% 至 65%，为 PC 处理器架构上的大型比对（150 个序列）提供了最佳加速。 PAxML 的算法优化侧重于在更短的时间内获得与并行 fastDNAml 完全相同的结果。当前 RAxML 工作的目标是使用新颖的算法在更短的时间内获得比 PAxML 更好或同等好的树。我们简要描述了这个新颖程序的基本部分，并提供了一些初步的令人鼓舞的结果。随机方法：最初在[2]中提出并在并行fastDNAml中进行一些修改实现的逐步加法算法的主要缺点之一是最终的树强烈依赖于序列的输入顺序。因此，建议在高重排水平下使用不同的随机序列输入顺序排列多次运行程序，以获得可靠的结果。即使在超级计算机上，这种做法对于大型树（200 个序列）来说也是禁止的，因为彻底的重新排列和类群数量的增加会增加运行时间几个数量级。为了解决这些问题，我们设计了 RAxML，这是一个基于 MPI 的并行程序，它基于简单的主从架构。 RAxML 最初分析大量随机输入顺序排列，这些排列由工作进程进行评估，无需重新排列。主节点从工作节点收集树拓扑并维护良好的初始树列表。当指定数量的随机输入顺序排列被评估后，树列表中拓扑的一小部分或几个部分将用于使用来自 PHYLIP 的 CONSENSE [4] 构建多数规则共识树，我们将其集成到我们的代码中。然后，工作人员会评估这些共识拓扑，因为它们通常比列表中的原始最佳树表现出更好的可能性。在最后一步中，主设备以与并行 fastDNAml/PAxML 相同的方式重新排列树。测试数据和结果 为了测试我们的程序，我们从 ARB [5] 小亚基核糖体核糖核酸 (ssrRNA) 数据库中提取了包含 150、200、250、500 和 1000 个分类单元（150 ARB，...，1000 ARB）的比对。这些排列包含来自真核生物、细菌和古生菌三个王国的生物体。此外，我们使用[9]中的150个序列数据集（150 SC），并使用[9]中指定的PAxML执行完全相同的详尽搜索，使用10个随机输入顺序排列以及设置为5的全局和局部重新排列。所有测试都在HELICS [3] 512处理器Linux集群上进行。在表 1 中，我们列出了 PAxML 和 RAxML 各自比对所需的 CPU 时间和最终似然值、RAxML 评估的随机树数量、PAxML 进行的混乱数量 (J) 以及两个程序共有的重排设置 (R)。最后，我们表 1. PAxML 和 RAxML 的 CPU 小时总数和最终可能性 数据 CPU 小时 PAxML Lh J R CPU 小时 RAxML Lh # trees acc 150 SC 1635.66 -44146.90 10 5 64.29 -44145.98 500 25.44 150 ARB 300.40 -77189.78 1 5 106.14 -77189.69 500 2.83 200 ARB 774.56 -104743.33 1 5 287.57 -104743.32 500 2.69 250 ARB 1947.18 -131468.97 1 5 481.46 -131475.52 500 4.04 1000 ARB 9898.05 -402282.08 1 1 1070.59 -401501.57 3837 9.23 表 2. 具有最大似然性和简约性的 RAxML 随机阶段的 CPU 小时数和似然性 数据 CPU 小时最大。可能性 Lh CPU 小时简约性 Lh # 树 acc 150 SC 24.10 -44217.74 10.80 -44219.21 1732 2.23 150 ARB 53.80 -77235.17 5.89 -77235.49 508 9.13 200 ARB 110.70 -104859.28 12.69 -104822.64 517 8.72 250 ARB 177.44 -131683.32 5.41 -131625.73 171 32.80 500 ARB 913.09 -253103.57 41.93 -253132.42 731 21.77 1000 ARB 2882.22 -402683.21 178.63 -402416.93 3837 16.14 提供 RAxML 实现的加速度 (acc)。请注意，1000 个分类单元树已使用下面描述的基于简约的 RAxML 版本进行了计算。此外，我们还对使用并行 fastDNAml 的 150 SC 比对进行了额外的运行，这需要 343.09 个 CPU 小时，而使用 PAxML 则需要 165.50 个 CPU 小时，以证明 PAxML 的优势。在 RAxML 的第二个版本中，我们用 PHYLIP 的简约程序 dnapars 替换了随机输入序列排列的最大似然评估，该程序使用类似的逐步加法算法来构建树。我们首先使用简约性计算一组树，并以最大似然评估最终的拓扑。由于简约性和最大似然性之间似乎存在关系 [1]，并且简约性明显快于最大似然性，因此这种变化显着减少了计算初始好树集所需的时间。表 2 给出了随机树推理时间的比较。树数量和加速因子的巨大变化是由于实际树的数量无法预测，因为 dnapars 为每个输入顺序排列生成任意数量的同等简约树。可用性和未来工作：与 PAxML 一样，RAxML 很快将作为开源程序可供下载，网址为 [6]。此外，所有比对和树文件都将可供下载，以建立第一个最大似然基准套件，这是比较最大似然程序所迫切需要的。我们打算更广泛地利用共识树信息来加速重排过程。该信息可用于对频繁出现的子树执行局部优化。此外，我们目前正在开发 AxML@home，这是 RAxML 的 seti@homelike 版本。
The computation of large phylogenetic trees based on the maximum-likelihood criterion is extremely computationally expensive. We propose a new, partially randomized parallel algorithm for the reconstruction of large phylogenetic trees, which yields equally good or even better trees in less time. We provide initial results for alignments containing 150 up to 1000 sequences from various sources. First results show run time improvements of at least factor 2 over PAxML for the experiments we conducted. 1. Randomized A(x)ccelerated Maximum Likelihood Introduction: In previous work [8] [7] we have introduced Subtree Equality Vectors (SEVs) for significantly accelerating the topology evaluation function of maximum likelihood-based phylogeny programs. We implemented SEVs in PAxML (Parallel A(x)ccelerated Maximum Likelihood) which was derived from parallel fastDNAml [9]. PAxML shows run time improvements of approximately 25% to 65% compared to parallel fastDNAml, yielding best accelerations for large alignments ( 150 sequences) on PC processor architectures. The algorithmic optimizations of PAxML focused on obtaining exactly the same results as parallel fastDNAml in less time. The goal of current work on RAxML is to obtain better or equally good trees than PAxML in less time with a novel algorithm. We briefly describe the essential parts of the novel program and provide some initial encouraging results. A Randomized Approach: One of the main disadvantages of the stepwise addition algorithm initially proposed in [2] and implemented with some modifications in parallel fastDNAml is that the final tree strongly depends on the input order of the sequences. Thus, it is recommended to run the program several times with different randomized sequence input order permutations at high rearrangement levels for obtaining reliable results. This practice becomes prohibitive for large trees ( 200 sequences) even on supercomputers since thorough rearrangements and an augmentation in the number of taxa increases run time by orders of magnitude. In order to handle those problems we have designed RAxML, an MPI-based parallel program which is based on a simple master-worker architecture. RAxML initially analyzes a large number of randomized input order permutations, which are evaluated by the worker processes without rearrangements. The master collects the tree topologies from the workers and maintains a list of good initial trees. When the specified number of randomized input order permutations has been evaluated a fraction or several fractions of the topologies in the tree list are used for building a majority-rule consensus tree with CONSENSE [4] from the PHYLIP, which we integrated into our code. These consensus topologies are then evaluated by the workers, since they often show a better likelihood than the original best tree in the list. In the final step the master rearranges the tree in the same way as parallel fastDNAml/PAxML. Test Data & Results For testing our program we extracted alignments comprising 150, 200, 250, 500 and 1000 taxa (150 ARB,...,1000 ARB) from the ARB [5] small subunit ribosomal RiboNucleic Acid (ssrRNA) database. Those alignments contain organisms from the three kingdoms Eucarya, Bacteria and Archaea. In addition, we used the 150 sequence data set (150 SC) from [9] and performed exactly the same exhaustive search with PAxML as specified in [9] using 10 randomized input order permutations and global as well as local rearrangements set to 5. All tests have been conducted on the HELICS [3] 512 processor Linux Cluster. In Table 1 we list the required CPU hours and final likelihood values of PAxML and RAxML for the respective alignments, the number of randomized trees evaluated by RAxML, the number of jumbles (J) conducted with PAxML and the rearrangement setting (R) which is common to both programs. Finally we Table 1. Total Amount of CPU hours and final likelihoods for PAxML and RAxML Data CPU hrs PAxML Lh J R CPU hrs RAxML Lh # trees acc 150 SC 1635.66 -44146.90 10 5 64.29 -44145.98 500 25.44 150 ARB 300.40 -77189.78 1 5 106.14 -77189.69 500 2.83 200 ARB 774.56 -104743.33 1 5 287.57 -104743.32 500 2.69 250 ARB 1947.18 -131468.97 1 5 481.46 -131475.52 500 4.04 1000 ARB 9898.05 -402282.08 1 1 1070.59 -401501.57 3837 9.23 Table 2. Amount of CPU hours and likelihoods for the randomized phase of RAxML with maximum likelihood and parsimony Data CPU hrs max. likelihood Lh CPU hrs parsimony Lh # trees acc 150 SC 24.10 -44217.74 10.80 -44219.21 1732 2.23 150 ARB 53.80 -77235.17 5.89 -77235.49 508 9.13 200 ARB 110.70 -104859.28 12.69 -104822.64 517 8.72 250 ARB 177.44 -131683.32 5.41 -131625.73 171 32.80 500 ARB 913.09 -253103.57 41.93 -253132.42 731 21.77 1000 ARB 2882.22 -402683.21 178.63 -402416.93 3837 16.14 provide the acceleration (acc) achieved by RAxML. Note that the 1000 taxon tree has already been calculated with the parsimony-based version of RAxML described below. Furthermore, we conducted an additional run for on jumble of the 150 SC alignment with parallel fastDNAml which required 343.09 CPU hours in contrast to 165.50 CPU hours it required with PAxML to demonstrate the advantages of PAxML. In a second version of RAxML we replaced the maximum likelihood evaluation of randomized input sequence permutations by the parsimony program dnapars from PHYLIP which uses a similar stepwise addition algorithm for tree building. We first calculate a set of trees using parsimony and evaluate the final topologies with maximum likelihood. Since there seems to exist a relationship between parsimony and maximum likelihood [1] and parsimony is significantly faster than maximum likelihood this change significantly reduces the time required for calculating an initial set of good trees. A comparison of randomized tree inference times is given in Table 2. The great variations in tree number and acceleration factor are due to the fact that the number of actual trees can not be predicted since dnapars yields an arbitrary number of equally parsimonious trees for each input order permutation. Availability & Future Work: Like PAxML, RAxML will soon become available for download as open source program at [6]. In addition all alignments and tree files will become available for download in an effort to establish a first maximum-likelihood benchmark-suite, which is urgently needed for comparing maximum likelihood programs. We intend to make more extensive use of the consensus tree information for accelerating the rearrangement process. This information can be used to perform local optimizations of frequently appearing subtrees. Furthermore, we are currently developing AxML@home, a seti@homelike version of RAxML.