樹形再配置は、最適な系統樹構造を探索するための決定論的アルゴリズムです。自然に樹形に配列されたあらゆるデータセットに適用できますが、計算系統学、特に系統樹の最大節約法や最大尤度探索において最も応用されています。これらの探索は、特定の遺伝子または種の進化史を最もよく説明する多数の樹形の中から、1つを特定することを目指します。
基本的なツリーの再配置
-
最近隣インターチェンジ（NNI）
-
サブツリーの剪定と再接ぎ木（SPR）
-
ツリー二分法と再接続（TBR）
最も単純なツリー再配置は、最近傍交換（nearest-neighbor interchange ）と呼ばれ、メインツリー内の4つのサブツリーの接続性を交換するものです。4つのサブツリーを接続する方法は3通りあり[1]、そのうち1つは元の接続性であるため、交換ごとに2つの新しいツリーが作成されます。各サブツリーの可能なセットについて、可能な最近傍を網羅的に検索する方法は、この検索を実行する最も遅い方法ですが、最も最適化された方法です。より広範囲な検索であるサブツリー剪定と再接ぎ木（SPR）は、メインツリーからサブツリーを選択して削除し、メインツリーの別の場所に再挿入して新しいノードを作成します。最後に、ツリー二分と再接続（TBR）は、サブツリーを内部ノードでメインツリーから切り離し、このようにして作成された2つのツリーのエッジ間の可能なすべての接続を試みます。ツリー再配置手法の複雑さが増すと、検索に必要な計算時間が増加しますが、必ずしもパフォーマンスが向上するわけではありません。[2]
SPRはさらにuSPR（Unrooted SPR）とrSPR（Rooted SPR）に分類されます。uSPRはルートなしのツリーに適用され、以下のように動作します：任意のエッジを切断します。エッジの一端（任意に選択）をツリー内の他の任意のエッジに接続します。rSPRはルート付きツリー*に適用され、以下のように動作します：ルートノードにつながるエッジ以外の任意のエッジを切断します。エッジの一端（具体的にはルートから最も遠いエッジの端）を接続、ツリー内の他の任意のエッジに接続します。[3]
* この例では、ツリーのルートは次数 1 のノードでマークされています。つまり、ツリー内のすべてのノードは次数 1 または次数 3 を持ちます。Bordewich と Semple で使用されている別のアプローチでは、ルート ノードが次数 2 であると見なし、rSPR に特別なルールを適用します。
ある木から別の木へ移動するために必要なSPR [4]またはTBR [5]の移動回数は、それぞれ根付き木または根なし木からなる最大合意森を生成することで計算できます。この問題はNP困難ですが、固定パラメータで計算可能です。
ツリー融合
最も単純なタイプのツリー融合は、既に準最適と判定された2つのツリーから開始されます。したがって、これらのツリーの大部分のノードは正しいと考えられますが、個々のツリーの「葉」を適切に解決できない可能性があります。例えば、枝の先端における分離((A,B),(C,D))と((A,C),(B,D))は未解決である可能性があります。[1]ツリー融合は、これら2つの解を、それ以外は準最適である2つのツリー間で交換します。この手法の派生版では、定義された目的関数を持つ標準的な遺伝的アルゴリズムを用いて、高得点のサブツリーを、全体的に高得点のメインツリーに交換します。[6]
セクター検索
別の戦略としては、ツリーの一部を切り離し（ランダムに選択することも、より戦略的なアプローチを用いることもできる）、このサブツリーに対してTBR/SPR/NNIを実行するという方法がある。この最適化されたサブツリーをメインツリーに置き換えることで、pスコアの向上が期待できる。[7]
木の漂流
局所最適解に陥るのを避けるために、「シミュレーテッドアニーリング」アプローチを使用することができます。このアプローチでは、アルゴリズムが最適解からどれだけ離れているかに関連した確率で、最適ではない候補ツリーを時々考慮することを許可します。[7]
木の融合
同等に最適なツリーを複数集めた後、個々のツリーの「良い部分」を組み合わせることで、より良いツリーを見つけることができる場合が多い。構成は同一だがトポロジーが異なるサブグループを入れ替え、結果として得られるツリーを評価することも可能である。[7]
参考文献
- ^ ab フェルゼンシュタイン、ジョゼフ (2004)。系統発生の推測。 Sinauer Associates: マサチューセッツ州サンダーランド。ISBN 9780878931774。
- ^ 高橋 啓; 根井 正俊 (2000年8月). 「多数の配列を用いた場合の最大節約、最小進化、最大尤度に基づく系統推論の高速アルゴリズムの効率」.分子生物学と進化. 17 (8): 1251– 1258. doi : 10.1093/oxfordjournals.molbev.a026408 . PMID 10908645.
- ^ Bordewich, Magnus; Semple, Charles (2005). 「根付き部分木剪定および再接ぎ木距離の計算複雑性について」Annals of Combinatorics . 8 (4): 409– 423. doi :10.1007/s00026-004-0229-z. S2CID 13002129.
- ^ Whidden, Chris; Beiko, Robert G.; Zeh, Norbert (2016). 「多分岐木の最大合意フォレストのための固定パラメータ近似アルゴリズム」. Algorithmica . 74 (3): 1019– 1054. arXiv : 1305.0512 . doi :10.1007/s00453-015-9983-z. S2CID 14297537.
- ^ Chen, Jianer; Fan, Jia-Hao; Sze, Sing-Hoi (2015). 「多分岐木における最大合意フォレストのためのパラメータ化アルゴリズムと近似アルゴリズム」.理論計算機科学. 562 : 496–512 . doi : 10.1016/j.tcs.2014.10.031 .
- ^ 松田 浩 (1996). 「遺伝的アルゴリズムを用いた最大尤度法によるタンパク質系統推定」(PDF) .太平洋バイオコンピューティングシンポジウム 1996. pp. 512– 523.
- ^ abc Goloboff, Pablo A. (1999). 「大規模データセットを合理的な時間で解析する：複合最適解法」. Cladistics . 15 (4): 415– 428. doi : 10.1006/clad.1999.0122 . PMID 34902941.
