WikiEdge:BioRxiv-2023.05.16.541039

出自WikiEdge
跳至導覽 跳至搜尋
  • 標題：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距離，這可能會影響給定不確定的"流浪類群"的時間樹採樣算法的結果。

問題與動機

作者面對的研究問題包括：

背景介紹

這篇文獻的背景主要集中在以下幾個方面：

  1. 系統發育樹
  2. 系統發育樹的推斷方法
    • 許多推斷系統發育樹的方法使用樹採樣或樹空間搜索算法，包括貝葉斯方法和最大似然方法。
    • 這些方法依賴於樹提議，即對給定的樹提出一個與當前樹相似的新樹，如果滿足某些條件則接受。
    • 樹重排操作，如SPR操作（子樹剪除和重新嫁接）和NNI操作（最近鄰互換），通常用於這些樹提議。
  3. SPR操作的NP困難性
    • 儘管SPR操作在樹搜索算法中很受歡迎，但計算SPR距離（即通過SPR操作將一棵樹轉換為另一棵樹所需的最小SPR操作次數）是NP困難的。
    • 儘管如此，存在固定參數可解的算法用於計算SPR距離，這對於分析後驗分佈模式或計算超樹是有用的。
  4. 時間樹
    • 時間樹是表示進化事件時間的系統發育樹，其分支長度代表時間，在許多應用中具有興趣。
    • 時間樹的推斷方法，如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. 理論證明與算法實現相結合：
    • 通過理論證明和算法實現相結合的方法，研究了樹空間的幾何特性和計算複雜性。
    • 探討了在樹空間中計算最短路徑的問題，並提出了可能的算法策略來解決這一問題。

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

研究結論

根據提供的文獻內容，這篇論文的主要結論可以概括如下：

  • 引入了兩種新的樹空間RSPR和HSPR，這些空間擴展了傳統的SPR樹空間到有排名的樹。
  • 證明了RSPR和HSPR空間是連通的，並且具有二次方數量的鄰域大小和線性的直徑，與根的（未排名的）SPR空間類似。
  • 發現RSPR和HSPR空間既不具有弱聚類屬性也不具有強聚類屬性，這意味着不能使用針對經典SPR的NP-hard證明技術。
  • 展示了在RSPR和HSPR中，最短路徑的結構可能對開發計算或近似排名SPR距離的算法有用。
  • 揭示了在某些情況下，向兩棵樹添加一個新葉子可以線性地減少它們之間的距離，這在已知的基於樹重排的樹空間中是未觀察到的行為。

這些結論為理解基於排名的SPR樹空間提供了新的視角，並為進一步研究提供了基礎，特別是在樹推斷算法和時間樹推斷方法的分析中。

術語表

這篇文章的術語表如下：

  • 系統發育樹：數學形式化生物進化歷史的樹狀圖，用於表示生物、物種、基因等之間的進化關係。
  • 有序系統發育樹：具有內部節點排序的系統發育樹，根據相應進化事件的時間進行排序。
  • 子樹剪切和重新嫁接：一種樹重排操作，通過剪切樹的一條邊並重新將剪下的子樹嫁接到樹的另一個位置來改變樹的結構。
  • 水平SPR：在有序系統發育樹上進行的SPR操作，要求剪切和重新嫁接的節點具有相同的等級。
  • 有序SPR：包括水平SPR和等級交換操作的樹重排空間。
  • 時間樹：分支長度代表時間的系統發育樹，常用於分析病毒傳播或癌症進化等。
  • 貝葉斯系統發育推斷：使用馬爾可夫鏈蒙特卡洛（MCMC）方法等計算方法重建時間樹。
  • 馬爾可夫鏈蒙特卡洛：一種統計學中用於近似計算的算法，常用於貝葉斯推斷。
  • 固定參數可解算法：一種算法，其運行時間可以表示為參數的函數，適合解決NP難問題。
  • 最大一致性森林：兩個樹之間通過刪除最少數量的邊得到的相同森林。
  • 聚類屬性：如果兩個樹共享一個聚類，並且它們之間的最短路徑都保留這個聚類，則稱該樹空間具有聚類屬性。
  • 櫻桃：由一個內部節點和兩個葉子節點組成的子樹。
  • 流氓分類群：在樹中位置不同的葉節點，通常對樹的距離有顯著影響。
  • 有序樹：內部節點具有唯一等級的樹，通常用於表示有時間信息的系統發育樹。
  • 樹空間的直徑：樹空間中任意兩棵樹之間的最大距離。
  • 鄰域大小：在樹空間中，與給定樹距離為1的樹的數量。
  • 等級移動：在有序樹上進行的操作，交換兩個具有連續等級且不相連接的節點的等級。
  • 毛毛蟲樹：一種特殊的樹，其中所有葉節點都是連續的，形成一個線性序列。
  • 樹重排操作：用於改變樹結構的一系列操作，如SPR和NNI。
  • 最近鄰交換：一種局部樹重排操作，只交換相鄰節點。
取自 "http://zh.wikiedge.org/index.php?title=WikiEdge:BioRxiv-2023.05.16.541039&oldid=1937"