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