WikiEdge:BioRxiv-2023.05.16.541039

• 标题：Ranked Subtree Prune and Regraft
• 中文标题：排名子树修剪和接接
• 发布日期：2023-05-18
• 作者：Collienne, L.; Whidden, C.; Gavryushkin, A.
• 分类：evolutionary biology
• 原文链接：10.1101/2023.05.16.541039

摘要：系统发育树是生物、物种、基因、癌细胞等进化历史的数学形式化。对于许多应用，例如在分析病毒传播树或癌症进化时，人们对（系统发育）时间树感兴趣，其中分支长度代表时间。从（通常是分子）序列数据重建时间树的计算方法，例如使用马尔可夫链蒙特卡洛（MCMC）方法的贝叶斯系统发育推断，依赖于采样树空间的算法。他们采用诸如SPR（子树剪枝和接枝）和NNI（最近邻互换）之类的树重排操作，或者在推断时间树的情况下，采用考虑内部节点时间的这些操作的版本。虽然经典的SPR树重排已经被深入研究，但是时间树的变体却不太被理解，这限制了时间树方法的比较分析。 在本文中，我们考虑在排列系统发育树空间上对经典的SPR重排进行修改，这些树配备了对所有内部节点的排列。这种修改产生了两种新的树空间，我们建议研究。我们通过讨论这些树空间的算法属性开始这项研究，重点关注与计算在排列SPR操作下的距离的复杂性以及与已知基于树重排的树空间的相似性和差异性有关的属性。令人惊讶的是，我们显示出一个违反直觉的结果，即向树添加叶子实际上可以减少它们的排列SPR距离，这可能会影响给定不确定的"流浪类群"的时间树采样算法的结果。

问题与动机

作者面对的研究问题包括：

• 如何定义和理解对时间树进行操作的变体 SPR 动作？
• 在考虑时间信息的情况下，如何计算和理解树之间的距离？
• 如何分析和比较不同树排列操作的复杂性？
• 如何在存在时间信息的情况下，有效地进行树的推断和采样？
• 如何量化和理解在树空间中添加新的叶子（例如在病毒传播或癌症进化分析中）对树距离的影响？
• 如何在树空间中有效地探索和比较不同的树排列方法？

背景介绍

这篇文献的背景主要集中在以下几个方面：

系统发育树

• 系统发育树是生物进化历史的一种数学形式，用于描述生物、物种、基因、癌细胞等之间的进化关系。
• 系统发育树通常从DNA、RNA、氨基酸或其他类型的序列数据中推断得出，用于重建物种集的进化历史，例如构建生命之树、分析病毒传播模式和研究癌症进化。
• 研究目标是找到最佳解释给定序列数据之间进化关系的系统发育树。

系统发育树的推断方法

• 许多推断系统发育树的方法使用树采样或树空间搜索算法，包括贝叶斯方法和最大似然方法。
• 这些方法依赖于树提议，即对给定的树提出一个与当前树相似的新树，如果满足某些条件则接受。
• 树重排操作，如SPR操作（子树剪除和重新嫁接）和NNI操作（最近邻互换），通常用于这些树提议。

SPR操作的NP困难性

• 尽管SPR操作在树搜索算法中很受欢迎，但计算SPR距离（即通过SPR操作将一棵树转换为另一棵树所需的最小SPR操作次数）是NP困难的。
• 尽管如此，存在固定参数可解的算法用于计算SPR距离，这对于分析后验分布模式或计算超树是有用的。

时间树

• 时间树是表示进化事件时间的系统发育树，其分支长度代表时间，在许多应用中具有兴趣。
• 时间树的推断方法，如BEAST和BEAST2软件包，依赖于结合进化事件时间信息的树提议。
• 尽管SPR操作已广泛用于树提议，并且已适应于时间树，但关于考虑进化事件时间的SPR树空间的研究还相对较少。

综上所述，这篇文献的背景强调了系统发育树在描述生物进化关系中的重要性，以及推断这些树的方法，特别是SPR操作在树搜索算法中的应用和挑战。此外，文献还探讨了时间树的概念及其在进化分析中的应用，指出了在考虑进化事件时间时对SPR操作进行数学研究的必要性。