查看“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树空间中树之间的最短路径，包括路径的结构和如何通过这些路径保持共享的簇。
# '''添加叶子的影响'''：讨论了向两个树中添加新叶子时，它们之间的距离如何变化，特别是当存在不同位置的“流氓分类群”时，距离可能会减少。