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. 理論證明與算法實現相結合：
   • 通過理論證明和算法實現相結合的方法，研究了樹空間的幾何特性和計算複雜性。
   • 探討了在樹空間中計算最短路徑的問題，並提出了可能的算法策略來解決這一問題。

這篇論文的方法論分析結果表明，通過數學建模和計算分析可以深入理解系統發育樹的重排操作，這對於進化生物學中的樹推斷方法具有重要意義。