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

背景介绍

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

• 系统发育树

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

• 系统发育树的推断方法

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

• SPR操作的NP困难性

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

• 时间树

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

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

章节摘要

这篇论文是关于系统发育树的数学形式化以及它们在进化历史分析中的应用，主要内容包括：

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

研究方法

这篇论文通过数学建模和计算分析，研究了在带排名的系统发育树上应用SPR（子树剪枝和重接）操作的性质。以下是该研究方法论的主要组成部分：

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

这篇论文的方法论分析结果表明，通过数学建模和计算分析可以深入理解系统发育树的重排操作，这对于进化生物学中的树推断方法具有重要意义。