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操作進行數學研究的必要性。