查看“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操作进行数学研究的必要性。

== 章节摘要 ==
这篇论文是关于[[系统发育树]]的数学形式化以及它们在[[进化历史分析]]中的应用，主要内容包括：
# '''引言'''：介绍了系统发育树在展示[[生物]]、[[物种]]或[[基种]]之间的进化关系中的应用，并讨论了从[[序列数据]]推断系统发育树的方法，特别是[[贝叶斯方法]]和[[最大似然方法]]。这些方法依赖于树的重排操作，如[[SPR（子树剪枝和重接）]]和[[NNI（最近邻互换）]]。
# '''预备知识'''：定义了[[根系统发育树]]和[[排名系统发育树]]的概念，并描述了SPR操作在排名树上的变体，称为[[水平SPR（HSPR）]]和[[排名SPR（RSPR）]]。
# '''HSPR和RSPR的基本性质'''：探讨了HSPR和RSPR树空间的基本性质，包括它们是否连通，以及树邻域的大小和树空间的直径。
# '''最短路径'''：研究了在HSPR和RSPR树空间中树之间的最短路径，包括路径的结构和如何通过这些路径保持共享的簇。
# '''添加叶子的影响'''：讨论了向两个树中添加新叶子时，它们之间的距离如何变化，特别是当存在不同位置的“流氓分类群”时，距离可能会减少。

== 研究方法 ==
这篇论文通过[[数学建模]]和[[计算分析]]，研究了在带排名的[[系统发育树]]上应用SPR（子树剪枝和重接）操作的性质。以下是该研究方法论的主要组成部分：
# '''[[数学建模]]'''：
#* 定义了带排名的[[系统发育树]]，并引入了水平SPR（HSPR）和排名SPR（RSPR）操作，这些操作用于在[[树空间]]中重新排列树的结构。
#* 通过[[数学定理]]和证明，探讨了这些操作的算法特性，如树空间的连通性、邻域大小和树间最大距离（直径）。
#* 引入了[[聚类表示法]]来描述和分析HSPR和RSPR操作对树结构的影响。
# '''[[计算分析]]'''：
#* 开发了计算方法来确定树空间的属性，例如证明树空间的连通性，计算树的邻域大小，以及估算树空间的直径。
#* 利用[[计算实验]]验证理论结果，例如通过实现算法来近似HSPR距离，并探索不同树之间的最短路径。
#* 分析了添加叶子对树距离的影响，特别是在处理[[病毒传播]]等进化过程中的“流氓分类群”时。
# '''理论证明与算法实现相结合'''：
#* 通过理论证明和算法实现相结合的方法，研究了树空间的几何特性和计算复杂性。
#* 探讨了在树空间中计算最短路径的问题，并提出了可能的算法策略来解决这一问题。
这篇论文的方法论分析结果表明，通过数学建模和计算分析可以深入理解系统发育树的重排操作，这对于[[进化生物学]]中的树推断方法具有重要意义。

== 研究结论 ==
根据提供的文献内容，这篇论文的主要结论可以概括如下：
* 引入了两种新的树空间[[RSPR]]和[[HSPR]]，这些空间扩展了传统的[[SPR]]树空间到有排名的树。
* 证明了[[RSPR]]和[[HSPR]]空间是连通的，并且具有二次方数量的邻域大小和线性的直径，与根的（未排名的）[[SPR]]空间类似。 
* 发现[[RSPR]]和[[HSPR]]空间既不具有弱聚类属性也不具有强聚类属性，这意味着不能使用针对经典[[SPR]]的[[NP-hard]]证明技术。 
* 展示了在[[RSPR]]和[[HSPR]]中，最短路径的结构可能对开发计算或近似排名[[SPR]]距离的算法有用。 
* 揭示了在某些情况下，向两棵树添加一个新叶子可以线性地减少它们之间的距离，这在已知的基于树重排的树空间中是未观察到的行为。 
这些结论为理解基于排名的[[SPR]]树空间提供了新的视角，并为进一步研究提供了基础，特别是在树推断算法和时间树推断方法的分析中。

== 术语表 ==
这篇文章的术语表如下：
* [[系统发育树]]：数学形式化生物进化历史的树状图，用于表示生物、物种、基因等之间的进化关系。
* [[有序系统发育树]]：具有内部节点排序的系统发育树，根据相应进化事件的时间进行排序。
* [[子树剪切和重新嫁接]]：一种树重排操作，通过剪切树的一条边并重新将剪下的子树嫁接到树的另一个位置来改变树的结构。
* [[水平SPR]]：在有序系统发育树上进行的SPR操作，要求剪切和重新嫁接的节点具有相同的等级。
* [[有序SPR]]：包括水平SPR和等级交换操作的树重排空间。
* [[时间树]]：分支长度代表时间的系统发育树，常用于分析病毒传播或癌症进化等。
* [[贝叶斯系统发育推断]]：使用马尔可夫链蒙特卡洛（MCMC）方法等计算方法重建时间树。
* [[马尔可夫链蒙特卡洛]]：一种统计学中用于近似计算的算法，常用于贝叶斯推断。
* [[固定参数可解算法]]：一种算法，其运行时间可以表示为参数的函数，适合解决NP难问题。
* [[最大一致性森林]]：两个树之间通过删除最少数量的边得到的相同森林。
* [[聚类属性]]：如果两个树共享一个聚类，并且它们之间的最短路径都保留这个聚类，则称该树空间具有聚类属性。
* [[樱桃]]：由一个内部节点和两个叶子节点组成的子树。
* [[流氓分类群]]：在树中位置不同的叶节点，通常对树的距离有显著影响。
* [[有序树]]：内部节点具有唯一等级的树，通常用于表示有时间信息的系统发育树。
* [[树空间的直径]]：树空间中任意两棵树之间的最大距离。
* [[邻域大小]]：在树空间中，与给定树距离为1的树的数量。
* [[等级移动]]：在有序树上进行的操作，交换两个具有连续等级且不相连接的节点的等级。
* [[毛毛虫树]]：一种特殊的树，其中所有叶节点都是连续的，形成一个线性序列。
* [[树重排操作]]：用于改变树结构的一系列操作，如SPR和NNI。
* [[最近邻交换]]：一种局部树重排操作，只交换相邻节点。