跳转到主要内容

根挖掘者:一个根放置程序为系统发生树

抽象的

背景

在系统发育分析中,它是常见的,推断出植物。然而,了解根源是为了下游分析和解释是理想的。存在几种方法来恢复根,例如分子时钟分析(包括中点根)或使用外群生根树。不可逆转的Markov模型也可用于计算潜在根位置的可能性。

结果

我们提出了一个调用的软件RootDigger它使用一个不可逆的马尔可夫模型来计算给定树上最可能的根位置,并为每个可能的根位置推断置信值。我们发现RootDigger与IQ-TREE和MAD等类似工具相比,在寻找根源方面是成功的,有时还会超过它们。此外,我们发现的穷举模式RootDigger在定量和解释生根位置的不确定性方面是有用的。

结论

RootDigger可以在现有的系统发作上使用以找到根,或者判断根部放置的不确定性。RootDigger可根据麻省理工学院许可证在https://www.github.com/computations/root_digger

背景

在标准系统发育推理中,大多数工具[12[连根拔起的树。这是因为他们通常采用时间可逆的核苷酸替代模型[3.,因为它们产生的系统发育推理问题可以用计算加以处理。然而,时间可逆的模型不能确定根源,因为它们忽视了进化的方向。这就是所谓的滑轮原理[3.]。然而,一个根植的系统发育常常需要下游分析和解释结果,因为它可以解决长期存在的争议,关于大型分支在生命之树的位置[4.]。通常,研究人员将不得不使用专门的工具或在分析中包含额外的信息来恢复推断的根源概述系统发育树。

当主要的系统发育推断是通过可逆模型进行时,研究人员通常采用以下两种方法之一:在分析中包括一组外群分类群,或使用某种形式的分子时钟分析。不幸的是,这两种方法都有自己的挑战和陷阱[5.]。在分析中包括外组分类群会增加推断树所需的工作量,更重要的是,还会以意想不到的方式影响内组拓扑[6.]。通过校准分子时钟的需要可以复杂的分子时钟分析,因为这通常需要适当的和足够数量的化石记录,这些化石记录与研究下的生物相关[5.7.]。

或者,可以使用不可逆的模型,如在这种模型下的根放置影响树的可能性[8.]。不可逆模型的例子包括基因树种和解释基因复制、丢失和转移的树调和方法[9.,或字符演化的不可逆转的马尔可夫替代过程。这是后一个过程RootDigger用来建立一个现存的系统发育。这允许RootDigger为了规避在不可逆转模型下推断树的计算密集型步骤,而是仅在最后一步中使用不可逆转的模型来罗根推断的树。通过这样做,可以将两者都在可逆模型下的快速树推理,并在不可逆转的模型下扎根树。

本文的其余部分安排如下。首先,我们在理论和操作提供了更多背景RootDigger,也证明了我们的方法是正确的。然后,我们描述了操作RootDigger在细节。接下来,我们概述了用于实验验证的方法RootDigger并提出各自的结果。最后,我们讨论了效果RootDigger

使用额外的拓扑信息的方法利用关于世界的先验知识,这不存在于用于推断树的一般分子数据中。特别地,可以包括关于不太远离有问题的物种的特定物种的知识,可以作为所谓的小组。然后可以使用此OutGroup将root放在树上,作为Ingroup的最新常见祖先和小组应该是树的根。

将外组包含在分析中存在挑战。Gatsey等人。[10[甚至对于已经存在于分析中已经存在的分析(即,INGROUP),甚至可以将单个分类群添加到分析中的分析。荷兰[6.]研究模拟中的这种现象,并发现影响或改变InGroup拓扑的小组是常见的。

或者,分子时钟分析可以用来放置一个没有先验拓扑知识的根[11]。分子时钟假设假定以随机恒定的速率将替代过程交换基础(即“蜱圈”)。使用该假设可以在现有的系统发育树上的根目录推断出一个可能的位置。简单版本的这是中点生根,它依赖于恒定的分子时钟假设,以产生系统饱和方式有意义的生根,但它可以应用于任何二叉树,无论它是超电流。其他方法,例如最小祖先偏差(MAD)[12迷你[13]也依赖于分子时钟假设。他们试图通过改变分子时钟的速率来解决在违反严格分子时钟的情况下中点生根的潜在不良表现。

分子时钟分析表现出自己的困难。特别是,时钟通常不会以树上的恒定速率“勾选”[1415]。放松时钟模型的存在可以缓解这个问题,但并不总是成功地正确识别根,如[5.]并具有自己的推理错误和方法论挑战。

可以在树上放置根的最终方法是在不可逆转的进化模型下进行系统发育分析。使用不可逆转的模型时,时间方向会影响树的可能性[8.]。使用此属性,可以找到root树上的最可能位置,只要模型适当的拟合即可。实际上,早期结果表明一些不可逆转的模型(特别是基于角色替代的模型)对根生根的目的是不合适的[16]。然而,在这项工作中,我们发现这些关注似乎大多被夸大了(见结果)。一些软件包能够在不可逆模型下推断或评分系统发生树,并作为副产品还能识别根[117]。

系统发育树的不可逆模型有多种形式。例如,考虑复制、传输和丢失事件会产生一个不可逆转的模型[9.]。特别是,重复事件已用于生根树[18]。另一种方法是主要用于本作作品的方法,是消除标准字符(例如核苷酸或氨基酸)替代模型的可逆性假设。不幸的是,消除这种假设显着提高了找到良好(高可能性)系统发育树所需的计算工作。这是由于皮带轮原理的不可占用性[3.],它允许系统发育推理工具在树推理期间忽略根部放置。因此,通过采用不可逆转的模型,根源发生树上的根部的位置会影响该树的可能性。

由于根的位置影响树的可能性,在使用标准树搜索技术时,需要对考虑的每棵树的所有可能的根进行评估,以找到可能性最高的根。在最坏的情况下,这会增加工作量每棵树在树期间被访问到一个因素\ ({\ mathcal {O}} (n) \)在哪里N是数据集中的分类行数。因此,消除可逆性假设大大增加了推断树所需的计算工作。因此,标准推理工具选择采用可逆性假设,因为系统发育树推断否则将是计算的难治性。

作为用根部推断一棵树的计算昂贵过程的替代方法,可以在可逆模型下推断的直接树可以在不可逆转的模型下对可能的根部位置进行评估。这需要较少的计算工作,因为它跳过了在树搜索期间寻找中间树中的“好”根的昂贵步骤。通过这种方法,我们可以找到给定的系统发育树的最有可能的根位置。即使这种方法仍然面临数值挑战,因为之前的研究表明,生根的似然函数可能表现出几种局部最大值[16,尽管我们没有发现这是一个主要问题在我们的实验(见讨论)。

我们实现了开源软件工具RootDigger它使用不可逆的字符替换模型来推断已经推断出的给定树的根。我们的工具的输入是一个多序列比对(MSA)和一个未生根的系统发育树。RootDigger然后返回一个有根的树。RootDigger实现快速和慢根发现模式,称为搜索模式和穷举模式。搜索模式简单地通过适当的启发式查找最有可能的root,并且适用于简单地打算root树的用户。由于探索可能的根源,我们提供了详尽的模式,该模式彻底评估了将根部放入给定树的每个分支的可能性,并报告了似然重量比[19]为在树上的每个分支放置该分支的根目录。换句话说,穷举模式允许量化根放置不确定性。

此外,RootDigger支持螺纹和过程级并行性,分别在系统托儿科对准的潜在数据分区和不同的搜索起始位置(即根搜索过程的并行化)上。最后,为了支持使用Compute Clusters对极大的数据集上的根推断,我们已经实现了一个检查点系统RootDigger,它允许在出现硬件故障或达到作业时间限制时暂停搜索,并在稍后的时间点恢复搜索。

软件

使用RootDigger是直接的。所有所需的都是Newick格式的树,以及Phylip或Fasta格式的MSA。RootDigger是在MIT许可下发布的开源,并用C ++写入,并在Linux平台上进行。可以找到代码,文档,测试套件以及对现有库的任何修改https://www.github.com/computations/root_digger

为了实现可能性计算和不可逆模型,RootDigger有三个主要依赖性:GNU科学图书馆(GSL)[20.,系统发育似然库(LibPLL) [21和L-BFGS-B [22]。GSL用于非对称替代率矩阵的分解,LibPLL用于高效似然计算,L-BFGS-B用于多参数优化。

执行

输入到RootDigger是一个MSA和一个系统发生树,每个位点的期望平均取代量是分支长度。RootDigger然后通过计算DNA的不可逆转模型下的根位置的可能性来使用树和分支长度来找到最可能的根位置脚注1替代(特别是动乱[23]使用用户指定的数量\γ(\ \)离散率类别,和一个可选比例不变的站点,即,动荡+\γ(\ \)+ I)。不安的模型被使用是因为许多其他的模型(包括在李群中详细的模型[24])是从这个模型中得出的。沿着长度特定分支的根的最佳位置T.通过将给定分支分成两个与结果分支长度来计算\(\ beta t \)\ (t(1 -β\)\),\(0 \le \beta \le 1.0\)。的最大似然值\(\ beta \),并报告给定分支的可能性是该分支对该分支的根位置的可能性。By formulating the problem this way, we can use single parameter optimization techniques such as Brent’s Method, which are computationally more efficient compared to multi-parameter optimization routines such as the BFGS algorithm (named for its creators: Broyden, Fletcher, Goldfarb, and Shanno). Note that we specifically selected Brent’s Method instead of Newton’s Method, because it does not require the calculation of the second derivative to optimize the function. While an analytical computation of the second derivative could be implemented, initial estimates showed that the savings were not sufficient to justify the increased complexity and potential numerical issues. Nonetheless, in principle, the computation of the second derivative of the likelihood is feasible and could be implemented.

布伦特方法和类似方法的一个潜在问题是,它们通过识别目标函数导数的根来求极值。不过,为了找到最大值,需要对目标函数的值进行评估,因为导数的根可能对应于最小值。另外,Brent的方法无法找到所有的极值。为了减轻这种情况,我们需要寻找可以用来安全找到极值的包围窗。不幸的是,我们不知道找到这样的包围窗口的一般方法,所以使用递归方法,是搜索范围被平分和适当地搜索适当的窗口。这里恰当的意思是,所讨论的函数的符号在窗口的各自端点具有相反的符号。

如前所述,RootDigger提供两种操作模式。将单独讨论这些模式,以搜索模式开头:

  1. 1.

    初始化数值模型参数:

    • \(\α\)- 分析参数\γ(\ \)比率为1.0(如适用),

    • 字符替代利率到\ \压裂{1}({4}(4 - 1)= \压裂{1}{12}\)

    • 基础频率\(\ frac {1} {4} \)

  2. 2.

    根据以下策略之一(默认1%的可能根位置)

    • 修改的MAD(默认)或,

    • 随机。

  3. 3.

    对于每个起始root:

    1. 1.

      优化模型参数

      • \(\α\)-shape参数\γ(\ \)分布式费率(如果适用,只有每10个迭代),

      • 字符替代利率,

      • 基频。

    2. 2.

      找到当前模型的最佳根位置

      1. 1.

        创建在每个分支的中点评估的高似然根位置列表。

      2. 2.

        对于顶部的根(默认1%),沿着其特定的分支优化根位置。

    3. 3.

      重复3(一种)直到满足停止条件:

      • 当前迭代和前一次迭代之间的可能性差异足够小(低于用户定义的参数阿托尔),

      • 如果启用了早期停止,则通过沿着分支的距离(下面的用户定义参数以下,新根位置足够接近旧根位置brtol) 或者,

      • 已经通过了500多个迭代。

  4. 4.

    报告最好的发现根,以及其日志可能性

为了在搜索模式下选择初始分支,我们开发了两种策略:修改了MAD和随机选择。在使用修改的MAD时,我们通过简化版本的MAD算法计算每个分支的近似疯狂排名,以便计算效率。这种近似度量标准用于将分支排名为选择作为初始根位置。此选项可能会偏向结果,因此我们还为这些情况提供了一个随机分支策略。

在搜索过程中,我们在每次迭代中重新估计基频率,以充分优化可能性,而且因为优化这些参数的成本很小(大约占总运行时间的10%)。此外,因为我们使用了一个不可逆的替换矩阵,所以基频率在树的每个分支上可能不是稳定的。因此,为了保证良好的拟合,我们每次都需要优化基频。穷举模式的算法是类似的;核心优化例程与搜索模式相同。主要的区别是,现在正在考虑所有的分支:

  1. 1.

    对于树上的每一根树枝:

    1. 1.

      将根部放在电流分支。

    2. 2.

      初始化数值参数:

      • \(\α\)- 分析参数\γ(\ \)比率为1.0(如适用),

      • 字符替代利率到\ \压裂{1}({4}(4 - 1)= \压裂{1}{12}\)

      • 基础频率\(\ frac {1} {4} \)

    3. 3.

      优化模型参数

      • \(\α\)-shape参数\γ(\ \)(如果适用,并且只有10次迭代),

      • 字符替代利率,

      • 基频。

    4. 4.

      重复从1 (C)直到满足停止条件:

      • 这种迭代与之前的迭代之间的可能性之间的差异足够小(下面阿托尔) 或者,

      • 如果启用了早期停止,则新根位置沿着分支的距离与旧根位置足够接近(如下所示)brtol)。

      • 已经通过了500多个迭代。

  2. 2.

    用每个分支的注释报告树:

    • 沿着分支的根位置,

    • 对数似,

    • 似然重量比例[19]。

我们在每次迭代中重新初始化初始模型参数(搜索模式从(3),穷举模式从(1)),以避免大量的局部最小值,如[16]。在这两种模式中,有500的迭代次数的上限。在实证和模拟数据集中,从未达到此限制,只有确保程序最终将停止。

除了这两种搜索模式外,还有一种可选的早期停止模式,它可以与任何一种根搜索模式结合使用。在这种早期停止模式中,如果根位置连续两次几乎相同,则搜索将终止。这就是说,如果最佳根位置的位置与前一次迭代中的相同分支该分支对该分支的根位置推断的值足够地关闭了先前迭代中的位置,程序将终止。虽然早期停止优化确实基本上改善了生根次数(在一些经验数据集上大约在1.7倍),但是每个根放置的可能性都不会完全优化。在实践中,这并不大大影响最终的根展示位置,但它确实使得与其他工具无效的结果进行比较。

我们同时使用OpenMP [25]和MPI,以并行化计算部分。首先,我们使用OpenMP的线程并行性来优化每个分区(对对齐的部分进行独立地给出它们自己的模型参数)。如果数据集中存在太少的分区以实现“良好”并行效率,我们还将转换矩阵计算并行于分支机构。我们使用流程级并行性并并行化在初始搜索位置上搜索。这在穷举模式中最有效,其中有许多可以并行进行的独立搜索。要同步进程,则每个独立搜索的结果都被写入仅附加二进制日志文件。通过使用Append仅文件,将由底层文件系统处理文件位置的同步,简化多个文件检查点。在搜索结束时,审查检查点中的结果(根位置及其关联的日志似然),以及相关的型号参数)并由主节点执行找到最佳根的最终步骤。使用这种策略,我们能够(具有足够的独立搜索)实现0.58的“良好”并行效率(见图。12有多少核?。此外,通过使用这个仅附加日志方法,我们还可以实现搜索的检查指向。如果计算在搜索期间中断,当重新开始搜索时,将考虑之前的结果,并从停止的地方继续搜索。为了确保在执行过程中没有发生写损坏,并且所有写操作都已完成,将计算一个校验和。为了计算校验和,我们使用Alder-32算法,它作为zlib [26]。为了避免校验和依赖于zlibRootDigger将算法包含在自己的代码库中。

结果

来验证RootDigger,我们分别对模拟数据和经验数据进行了实验。此外,我们还使用了似然权重比(LWR) [19]来评估根放置在经验数据集上的置信度。最后,我们研究了早期停止模式对最终结果的影响。

实验设计

在以下部分中,我们将描述模拟数据和经验数据的实验设置。在这里,我们将描述我们如何测量并计算每个方法的错误。对于模拟和经验数据,我们计算了拓扑距离估计根的距离(由IQ树和树RootDigger在搜索模式下)到真正的根,并根据树中的节点数量(包括内部节点和提示)对其进行规范化。如果选对了根,距离就是零。对于经验数据,取真根为外组表示的根。

评估穷举的搜索模式很难,因为我们知识没有其他任何其他工具执行相同的任务。相反,我们展示了已经注释到树上的实证数据的LWR分布。另外,这些树具有真正的根(再次,如OFFGROUP所示)。

模拟

使用模拟数据进行测试,验证软件,并与IQ树版本2.0.4进行比较[27],它也实现了不可逆转的动荡模型。我们创建了一个管道

  1. 1.

    使用ETE3生成随机根树[28]和随机模型参数。

    • 通过均匀地拉伸在0.01和1.01之间产生不可磨灭的替代参数。

    • 通过指数分布产生不可磨灭的频率参数,然后归一化参数使得频率参数总和为1。

    • 否则,INDELible的选项将被保留为默认选项。

    • 分支长度是通过指数分布生成的,使用的尺度参数为0.5

  2. 2.

    模拟一个不可消除的MSA [29]

  3. 3.

    执行RootDigger和iq-tree [27使用模拟的MSA,给出生成的随机树。

  4. 4.

    重复(2)总共100次迭代

  5. 5.

    计算比较

    1. 1.

      使用ETE3计算根射频距离[30.]

    2. 2.

      使用真正的根映射到原始树上的根放置。

IQ树和RootDigger给出了所有运行的相同型号选项。RootDigger用参数执行。

\ ({\ texttt {rd}} \ \ texttt {-} {} \ texttt {-} {\ texttt {msa }} \, {<}{\ texttt {MSA文件 }}{>} \, \ texttt {-} {} \ texttt {-} {\ texttt{树 }}\, {<}{\ texttt{树文件}}{>}\)

默认RootDigger不使用任何\γ(\ \)税率类别,目前只支持骚乱模型[23]。IQ-TREE是带参数执行的

\({\ texttt {iqtree2}} \,{\ texttt {-m 12.12}} \,{\ texttt {-s}} \,{<} {\ texttt {msa文件}} {msa文件}} {>} \,{\texttt {-te}} \,{<} {\ texttt {树文件}} {>}}

-m 12.12参数的IQ-TREE指定动荡模型应该被使用[24]和\({\ texttt {-te}} \,{<} {\ texttt {tree file}} {>}}选项将树搜索约束到给定用户树。当给定完全解决的大树树时,这具有根目录的效果。我们使用此选项来模拟操作RootDigger。对于所有的运行,都使用了骚动模型。此外,我们改变两个额外的参数来控制数据集的大小:MSA站点的数量和分类群。我们总共进行了9次模拟试验,其中MSA大小分别为1000、4000和8000个地点,树木大小分别为10、50和100个分类单元。实验结果和执行时间如图所示。1

图。1
图1

IQ-TREE和的结果和执行时间的框图RootDigger启用未提前停止的模拟数据

经验数据

除了模拟数据外,我们还使用IQ-TREE和MAD对经验数据进行了测试[12]。表中描述了使用的数据集1有关表中数据集的额外统计数据2。经验数据集选自TreeBASE [3132]并由研究人员有助于提供[33包括一个现有的、得到强有力支持的外组。对于每一个经验数据集,我们运行RootDigger在穷举模式下,为每个分支获得似然权重比率(LWR)。我们在包含的小组中运行了数据集的实验,以及除外的小组。

表1用于验证的经验数据集表
表2实验数据集统计量表

我们还进行了一些预处理。为了确保在每个站点的替换中指定所有树的所有分支长度,使用RAxML-NG对分支长度进行重新优化[34)版本0.9.0git。在已知时使用原始模型,否则分支长度在GTR +下进行了优化\γ(\ \)4.

具有小LWR的分支(小于0.0001)的分支被抑制注释。具有注释LWR的树木如图1和图2所示。23.4.5.6.7.8.9.,10。分析误差汇总见表3.和每个方法的运行时间总结在表中4.

图2
figure2

没有一个小组的蜘蛛分析数据集。LWR是将根放在树枝上的似然权重比。真正的根分支以红色表示

图3.
图3

用小组分析数据集的蜘蛛。LWR是将根放在树枝上的似然权重比。真正的根分支以红色表示

图4.
装具

SpidersMitocondrial数据集分析没有外群。LWR是将根放在树枝上的似然权重比。真正的根分支以红色表示

图5.
figure5

SpidersMitocondrial数据集用外群分析。LWR是将根放在树枝上的似然权重比。真正的根分支以红色表示

图6.
figure6

Angiospermscds12数据集在没有超组的情况下分析。LWR是将根放在树枝上的似然权重比。真正的根分支以红色表示

图7.
figure7

Angiospermscds12数据集与一个小组分析。LWR是将根放在树枝上的似然权重比。真正的根分支以红色表示

图8
figure8

没有一个小组的草地分析了数据集。LWR是将根放在树枝上的似然权重比。真正的根分支以红色表示

图9.
figure9

甲壳物数据集在没有小组的情况下分析。LWR是将根放在树枝上的似然权重比。真正的根分支以红色表示

图10
图10.

没有一个小组的甲虫分析数据集。LWR是将根放在树枝上的似然权重比。真正的根分支以红色表示

表3用于验证和结果的实证数据集表
表4用于验证和结果的实证数据集表

早期停药对疗效的影响

最后,我们研究了早期停止准则对最终LWR结果的影响。为了做到这一点,我们跑了RootDigger在详尽模式下,所有经验数据集启用和禁用早期停止。对于大多数试验,有和没有早期停止的结果显示没有意义(LWR的差异小于0.000001)。LWR差异最大的数据集如图所示。11。作为交换,这个启用了早期停止的数据集的运行时间大约快1.7倍。

图11
图11.

早期停药对疗效的影响。数据集为SpidersMitocondrial, LWR在有和没有早期停止时的观测差异最大

在搜索模式中提前停止的运行时改进并不明显。我们无法衡量启用和禁用早期停止在搜索模式的结果或速度上的任何显著差异。我们怀疑,这是因为在穷举模式中,从早期停止获得的速度增益主要是由于它“跳过”低可能性分支,这对LWR没有显著贡献。

并行效率

最后,我们还对并行效率进行了评估RootDigger。数字12绘制加速度(比1节点快几次)对数据集DS7的完美效率。我们选择DS7,因为它是手头的较大数据集之一,因此非常适合显示强度和弱点RootDigger的并行化策略。结果在集群上计算,使用MPI在节点之间通信RootDigger的详尽的模式。并行效率从2个节点上的0.94到32个节点上的0.50,每个节点有16个核。

图12
图12.

描绘并行效率,这是对数节点和对数加速。试验在1、2、4、8、16和32个节点上运行,每个节点16个线程,在穷尽模式下使用DS7,并关闭早期停止。并行效率从2个节点上的0.94到32个节点上的0.50

讨论

IQ-TREE相比,RootDigger竞争力地执行,如图2的两侧都可以看出。1。模拟的结果是混合的,在所有模拟场景中,IQ-TREE在根放置方面的表现稍好。RootDigger在我们测试的所有数据集上都比IQ-TREE快。在分析实证数据时,RootDigger也表现良好,尽管不如IQ-TREE或MAD对大多数数据集,在大多数情况下产生最小的错误。一个明显的例外是数据集DS3RootDigger比疯狂或智商树获得更好的结果。检查数据集RootDigger的穷举模式(见图。8.),我们看到有许多分支机构对根放置良好的支持。这表明信号与该数据集的根源存在冲突的信号,这自然导致疯狂的杂乱,如疯狂。

通常,穷举模式在识别正确的根位置方面更成功(见图)。23.6.7.8.,9.)。这是意料之中的,因为穷尽模式对最佳根位置执行更彻底的搜索。尽管如此,这表明RootDigger不仅能成功地确定正确的根位置,而且还能成功地确定手头数据集的任何不确定性或模糊信号。

并行效率RootDigger可以接受,但还可以进一步改进。目前,效率的损失很大程度上是由于不同的初始搜索位置需要不同的时间来完成。当这种情况发生时,一些节点提前完成,必须等待其余节点完成它们的计算。由于这种行为,并行效率RootDigger是依赖于数据集的。幸运的是,这种行为通常只在每个节点有少量初始起始位置分配给它时才会表现出来。在这种情况下,运行时中的小变化没有机会在许多初始起始位置上“平均”。相比之下,当数据集相对于类群数量较大时,初始起始位置的数量会增加,因此每个节点完成计算工作的平均时间收敛到平均数量。尽管如此,RootDigger可以从启发式方法中受益,以智能地将初始搜索位置分配给节点。

结论

在Huelsenbeck [16]的研究表明,当使用不可逆的字符替换模型时,根放置在样本树上的先验概率没有很强的信号。在执行我们的验证RootDigger根据经验数据,我们发现情况往往不是这样。例如,在AngiospermsCDS12数据集上(见图。6.),我们发现有和没有外组的根放置的明确信号。

即使在信号不那么强的情况下,例如蜘蛛的线粒体(见图。4.),与Huelsenbeck的结果相比,有一个明显更强的根放置信号[16]建议我们应该通过这种分析(即,使用不可逆转的模型分析)。Huelsenbeck的结果建议我们基本上无法恢复有信号吗。相反,至少在大多数时候,信号似乎是中等强度的。唯一的例外是ficus数据集,它在树的几乎所有分支上都显示了对根的支持。我们怀疑这是由于Huelsenbeck对4个类群树进行了分析,其中包括青蛙、鸟、老鼠和人类等远缘类群。由于只使用4个远缘类群,速率矩阵不受现有数据的约束,可能导致过拟合。相比之下,对于“本地化的支系”,我们相信我们已经证明了这里提出的方法通常会产生一棵树生根的明确信号,当它们不能时,我们可以使用使用来识别这种情况RootDigger“穷举的搜索模式”。

未来与RootDigger在美国,有几项发展将是有用的。其中之一是对附加模型的支持。目前,我们只支持最复杂的模型动荡,但在未来,它可能有助于支持不那么复杂的模型,如伍德汉姆[24]。特别是,具有较少参数的模型通常被认为不太容易过拟合,这可能会导致更好地评估真正的根位置。

除了更多的模型,还可以支持其他数据类型,特别是氨基酸(AA)数据。在这项工作中,我们决定不使用AA数据,因为它将增加自由参数的数量从12个DNA数据到380个AA。考虑到这个数字,我们怀疑它太容易过度拟合而没有用处,但这从未被研究过。

最后,有一些参数不是模型的一部分,可以以较少的天真方式设置。这些参数包括搜索模式中的初始候选根的数量和在搜索模式的每个步骤期间完全优化的根数。在这项工作中,这些参数在模拟时表现良好,但可能通过自适应策略获得更好的结果。

的并行效率RootDigger可以使用两种技术中的任何一种来改进:启发性地将初始搜索位置分配给节点;或者初始搜索位置的一些动态调度来计算节点。在第一种技术中,我们尝试估计每个root将采用相对术语的长度,然后以这样的方式分配初始搜索位置,以便更好地平衡计算负荷。传统上,这可能很难有效地确实,因为启发式通常需要精细调整,这可能导致非典型数据集的性能下降。或者,可以动态地分配初始搜索位置。在这种情况下,当节点没有进行计算的工作时,初始搜索位置被按需传递。从这一点来看,尚不清楚哪种方法更好,两者都应该被调查。

可用性和要求

项目名称:RootDigger项目主页:欧宝直播官网apphttps://www.github.com/computations/root_digger操作系统:Linux编程语言:c++其他要求:Bison/Flex,可选GNU Scientific库。许可:麻省理工学院非学者使用的任何限制:无。

可用性数据和材料

在当前研究中分析的数据集可在root_digger_exp库,https://github.com/computations/root_digger_exp.

笔记

  1. 1.

    通常使用AA数据的树推断不允许使用完全不受限制的一般时间可逆(GTR)速率矩阵,而是从几个预先计算的经验替换矩阵之一挑选。这基本上限制了自由参数的数量,从而降低了过度配件的风险。相比之下,完全不受限制的可逆AA速率矩阵将具有380个自由参数。因此,我们选择限制RootDigger因为AA数据的等效模型有太多的参数需要可靠地优化。

缩写

AA:

氨基酸

(L)蓄热(- b):

(有限记忆)Broyden-Fletcher-Goldfarb-Shanno(有限)

背景:

脱氧核糖核酸

LWR:

似然重量比

疯了:

最小的祖先的偏差

MP ::

消息传递接口

MSA:

多个物种对齐

OpenMP:

开放的多处理

参考文献

  1. 1.

    Nguyen LT, Schmidt HA, von Haeseler A, Minh BQ。IQ-TREE:一种快速有效的估计最大似然系统发育的随机算法。2015;32(1): 268-74。

    中科院文章谷歌学术

  2. 2.

    Stamatakis A. Raxml版本8:一种系统发育分析和大脑发育后的分析。生物信息学。2014; 30(9):1312-3。

    中科院文章谷歌学术

  3. 3.

    Felsenstein J.来自DNA序列的进化树:最大的似然方法。J Mol Evol。1981; 17(6):368-76。

    中科院文章谷歌学术

  4. 4.

    邓永强,李建平,李建平,等。动物系统发育及其进化意义。动物学报。生态发展系统。2014;45(1):371-95。

    文章谷歌学术

  5. 5.

    关键词:进化发散时间,松弛时钟方法,可信度区间中国生物医学工程学报,2010;

    中科院文章谷歌学术

  6. 6.

    荷兰BR,Penny D,Hendy MD。分子时钟-A模拟研究下的超组误差和系统发育不准确性。系统中的生物学。2003; 52(2):229-38。

    中科院文章谷歌学术

  7. 7.

    Baele G,Li WLS,Drummond AJ,Suchare Ma,Lemey P.贝叶斯语文产学中松弛分子钟的精确模型选择。mol Biol Evol。2012; 30(2):239-43。

    文章谷歌学术

  8. 8。

    用不可逆替代模型建立系统发育树。中国生物医学工程学报,2005;https://doi.org/10.1186/1471-2148-5-2

    文章PubMedpmed中央谷歌学术

  9. 9。

    Morel B, Kozlov AM, Stamatakis A, Szöllősi GJ。GeneRax:在基因复制、转移和丢失的情况下,基于最大似然的基因树推理工具。BioRxiv。2019年。https://doi.org/10.1101/779066v1

    文章谷歌学术

  10. 10.

    Gatesy J,Desalle R,Wahlberg N.系统的样本应该有多少基因?从系统核糖基质的相互矛盾的洞察力,其特征是复制的不一致。系统中的生物学。2007; 56(2):355-63。

    中科院文章谷歌学术

  11. 11.

    杨忠。计算分子进化。牛津:牛津大学出版社;2006.

    谷歌学术

  12. 12.

    利用最小祖先偏差(minimal ancestor deviation)进行系统发育生根。自然生态学报。2017;1(1):1 - 7。

    文章谷歌学术

  13. 13.

    关键词:系统发育树,最小变异生根,物种树重建PLoS ONE。2017; 12 (8): e0182238。

    文章谷歌学术

  14. 14.

    人体内的分子钟比猿和猴子体内的慢。大自然。1987;326(6108):93。

    中科院文章谷歌学术

  15. 15.

    Steiper ME, Young NM。灵长类分子分化日期。分子系统进化研究。2006;41(2):384-94。

    中科院文章谷歌学术

  16. 16.

    Huelsenbeck JP, Bollback JP, Levine AM。推断系统发生树的根。51系统杂志。2002;(1):32-43。

    文章谷歌学术

  17. 17.

    Ronquist F, Huelsenbeck JP。MrBayes 3:混合模型下的贝叶斯系统发育推理。生物信息学。2003;19(12):1572 - 4。

    中科院文章谷歌学术

  18. 18。

    来自基因复制事件的物种树根推断。中国生物医学工程学报。2017;34(12):3267-78。

    中科院文章谷歌学术

  19. 19。

    斯特米默·克,Rambaut A.推断可能错过的基因树的信心集。Proc R SoC Lond Ser B Biol Sci。2002; 269(1487):137-42。https://doi.org/10.1098/rspb.2001.1862

    文章谷歌学术

  20. 20.

    GNU科学图书馆参考手册。布里斯托尔:网络理论有限公司;2009.

    谷歌学术

  21. 21.

    flui T, izquierdo carrasco F, Darriba D, Aberer AJ, Nguyen LT, Minh BQ等。系统发育可能性库。系统医学杂志。2015;64(2):356 - 62。

    中科院文章谷歌学术

  22. 22.

    Zhu C,Byrd Rh,Lu P,Nocedal J.算法778:L-BFGS-B:用于大规模约束优化的Fortran子程序。ACM Trans Math Softw(Toms)。1997年; 23(4):550-60。https://doi.org/10.1145/279232.279236

    文章谷歌学术

  23. 23.

    杨铮。核苷酸取代模式的估计。化学学报,1994;39(1):105-11。https://doi.org/10.1007/BF00178256

    文章PubMed谷歌学术

  24. 24.

    Woodhams MD, Fernández-Sánchez J, Sumner JG。与异质替代率一致的系统发育模型的新层次。系统医学杂志。2015;64(4):638 - 50。

    中科院文章谷歌学术

  25. 25.

    OpenMP体系结构审查委员会。OpenMP应用程序接口4.5版;2015.可以从:https://www.openmp.org/wp-content/uploads/openmp-4.5.pdf

  26. 26.

    标记阿德勒。一个大规模的炫耀但精致的不引人注心的压缩库(也是免费的,更不用说专利不受限制)。

  27. 27.

    Minh BQ,Schmidt H,Chernomor O,Schrempf D,Woodhams M,Haeseler A等人。IQ树2:基因组时代的系统发育推论的新模型和有效方法。生物XIV。2019年。https://doi.org/10.1101/849372v1

    文章谷歌学术

  28. 28.

    系统基因组数据的重建、分析和可视化。中国生物医学工程学报。2016;33(6):1635-8。

    中科院文章谷歌学术

  29. 29.

    弗莱彻W,杨Z.不可磨灭:一种生物序列演化的灵活模拟器。mol Biol Evol。2009; 26(8):1879-88。

    中科院文章谷歌学术

  30. 30.

    罗宾逊,福尔兹。系统发育树的比较。数学Biosci。1981;53(1):131 - 47。

    文章谷歌学术

  31. 31。

    Piel W,Chan L,Dominus M,Ruan J,Vos R,Tannen V. TreeBase v.2:系统发育知识数据库。电子生物圈。伦敦;2009.

  32. 32.

    VOS RA,Balhoff JP,Caravas Ja,Holder Mt,Lapp H,Maddison WP等。NEXML:比较数据和元数据的丰富,可扩展和可核实的表示。系统中的生物学。2012; 61(4):675-89。

    文章谷歌学术

  33. 33.

    Vasilikopoulos A, Balke M, Beutel RG, Donath A, Podsiadlowski L, Pflug JM,等。蛾总科(鞘翅目:Adephaga)的系统基因组学及其系统冲突和系统错误评价分子系统进化。2019;135:270-85。

    文章谷歌学术

  34. 34.

    Kozlov Am,Darriba D,Blowi T,莫雷利B,Stamatakis A. RaxML-NG:用于最大似然性的最大似然推理的快速,可扩展和用户友好的工具。生物XIV。2019年。https://doi.org/10.1101/447110

    文章谷歌学术

  35. 35.

    冉杰,沉tt,王mm,王xq。系统核糖核生物学决定了种子植物的深层系统发育,表明了Gnetales和Agiosperms之间的部分收敛或同时塑性进化。proc r soc b biol sci。1881; 2018(285):20181012。

    谷歌学术

  36. 36.

    Christin Pa,Spriggs E,奥斯本CP,StrömbergCae,萨拉敏N,Edwards EJ。分子约会,进化率和草的年龄。系统中的生物学。2014; 63(2):153-65。

    文章谷歌学术

  37. 37.

    Cruaud A, Rønsted N, Chantarasuwan B, Chou LS, Clement WL, Couloux A, et al.;植物-昆虫共多样化的一个极端例子:无花果和为无花果传粉的黄蜂。系统医学杂志。2012;61(6):1029 - 47岁。

    文章谷歌学术

  38. 38.

    勒德-罗伯特G,麦迪森WP。Habronattus跳蛛的系统发育与渐渗(蜘蛛目:跳蛛科)生物医学工程学报。2018;18(1):24。https://doi.org/10.1186/s12862-018-1137-x

    中科院文章PubMedpmed中央谷歌学术

下载参考

确认

作者要感谢HITS的Exelixis实验室的同事们:Pierre Barbera、Lucas Czech、Alexey Kozlov、Benoit Morel和Sarah Lutteropp,感谢他们提供的宝贵建议。此外,作者感谢Klaus Tschira基金会的支持。最后,我们要感谢一位审稿人提出的非常有用的建议和评论。

资金

该项目已获得欧盟地平线2020研究和创新项目的资助,该项目由Marie Sklodowska-Curie拨款协议No 764840资助。此外,这项工作是由Klaus Tschira基金会资助的。资助来源对本文的选题、实验设计、分析和结果解释均无影响。

作者信息

从属关系

作者

贡献

BB设计了很多RootDigger,写了所有代码,设计和运行实验,并写了这篇论文。促成了设计的设计RootDigger,并参与了该报的编辑工作。所有作者均已阅读并批准本稿件。

相应的作者

对应到本Bettisworth

道德声明

伦理批准和同意参与

不适用。

同意出版物

不适用。

利益争夺

提交人声明他们没有竞争利益。

额外的信息

出版商的注意

欧宝体育黑玩家Springer Nature在发表地图和机构附属机构中的司法管辖权索赔方面仍然是中立的。

权利和权限

开放获取本文根据创意公约归因于4.0国际许可证,这允许在任何中或格式中使用,共享,适应,分发和复制,只要您向原始作者和来源提供适当的信贷,提供了一个链接到Creative Commons许可证,并指出是否进行了更改。除非信用额度另有说明,否则本文中的图像或其他第三方材料包含在文章的创造性公共许可证中,除非信用额度另有说明。如果物品不包含在物品的创造性的公共许可证中,法定规定不允许您的预期用途或超过允许使用,您需要直接从版权所有者获得许可。要查看本许可证的副本,请访问http://creativecommons.org/licenses/by/4.0/。“创作共用公共领域”豁免书(http://creativecommons.org/publicdomain/zero/1.0/)适用于本文提供的数据,除非在数据的信用额度中另有说明。

重印和权限

关于这篇文章

通过Crossmark验证货币和真实性

引用这篇文章

Bettisworth,B.,Stamatakis,A. Root Digger:系统发育树的根部放置程序。欧宝娱乐合法吗22日,225(2021)。https://doi.org/10.1186/s12859-021-03956-0.

下载引用

关键词

  • 系统发育分析
  • 系统支持
  • 最大似然
\