最小限の進化

最小進化法は、系統モデル化において用いられる距離法の一種である。最大節約法と同様に、枝の長さの総和が最小となる系統を探索するという側面を持つ。 [1] [2]

最小進化（ME）基準の理論的基礎は、キッドとスガラメラ＝ゾンタ（1971）[3]とルジェツキーとネイ（1993）[4]の両氏の独創的な研究に立脚している。これらの枠組みでは、分類群の分子配列は、それらの相違度を表す一連の尺度（いわゆる「進化距離」）に置き換えられ、その距離が分類群からの真の進化距離（すなわち、分類群のすべての分子データが利用可能であった場合に得られるであろう距離）の不偏推定値である場合、分類群の真の系統樹は、それらの距離と適合する他のどの系統樹Tよりも短いと予想される長さを持つという基本的な結論が導かれる。

他の方法との関係および比較

系統樹構築方法の比較表
原理 使用例 時間計算量
最小進化（ME） 枝の長さの合計が最短となるものを探す 文字ベースの方法では要求が厳しすぎる大規模なデータセット ヒューリスティックを利用せずにNP困難
最大限の節約 進化のステップ（つまり突然変異）の最小数を探す 類似配列の比較 大規模データセットではNP困難
近隣参加 最短の枝の長さを反復的に結合して単一のツリーを構築します 大規模なデータセット / 情報提供サイトが少ないデータセット O (N 3 )はヒューリスティックスを使って改善できる
最大尤度 与えられたデータパラメータに基づいて、最も可能性の高い関数を探します 低バイアスが重要な大規模データセット O (N)、データセットが大きいほど改善される
加重なしペアグループ法（算術平均法）（UPGMA） クラスターのクラスターを作成し、クラスターの算術平均を求めます データの初期検査 酸素（窒素2）

最大限の節約

ここで、最大節約基準とME基準の微妙な違いについて言及する価値がある。最大節約基準は、より複雑な分類群に対する最も単純な分類群の進化仮説の妥当性といった、アブダクション的ヒューリスティックに基づいているのに対し、ME基準はキッドとスガラメラ・ゾンタの推測に基づいており、その推測は22年後にルジェツキーとネイによって正しいと証明された[4] 。これらの数学的結果により、ME基準はオッカムの剃刀原理から解放され、確固とした理論的かつ定量的な基盤が与えられた。

MEと同様に、最大節約法は最適なツリー[5] （つまり、形質状態の変化が最も少ないツリー）を見つけようとするとNP困難問題となる。そのため、ツリーの選択にはヒューリスティックがしばしば用いられるが、これは入力データセットに対してツリーが最適な選択であることを保証するものではない。この手法は、非常に類似した配列を解析する際によく用いられる。これは、その解析プロセスの一環として、配列中に顕著な数の置換が見られる情報提供部位を特定するためである[6] 。

ハミング距離の枝の長さを用いた最大節約基準は、1978年に統計的に矛盾していることが示されました。このことが、MEのような統計的に矛盾のない代替基準への関心につながりました。[7]

近隣参加

近傍結合は、均衡最小進化（BME）基準のための貪欲なヒューリスティックと見なすことができます。斎藤と根井による1987年のNJアルゴリズムは、2000年のBME基準よりはるかに古いものです。20年間にわたり、研究者たちはNJがなぜ機能するのかについての確固たる理論的根拠がないまま、NJアルゴリズムを用いてきました。[8]

近傍結合は、進化の最小ステップを優先するという同じ基本原理を共有していますが、文字ベースの手法である最大節約法とは対照的に、距離法であるという点で異なります。近傍結合のような距離法は、実装がより簡単かつ効率的であることが多いため、特に計算速度が重要となる大規模なデータセットの解析で人気を博しています。近傍結合は比較的高速な系統樹構築手法ですが、ヒューリスティックな実装を用いてこれを改善しない限り、最悪の場合でも計算量はO (N 3 ) になる可能性があります。 [9]また、他の多くの手法では考慮されていない、枝間の進化速度の違いも考慮します。

近傍結合法もまた、誤差がほとんどない、あるいは全くない入力距離行列から得られる出力木は、多くの場合、誤差が最小限に抑えられるという点で、かなり一貫性のある手法です。しかし、最大節約法のように完全な配列情報ではなく単純な距離値を用いると、問題の単純化によって情報が失われる可能性が高くなります。[10]

最大尤度

最尤法は、データから得られる最も可能性の高いツリーの検定を組み合わせたものであるという点で、最小進化法とは対照的です。しかし、関連する数学的性質上、データセットが小さい場合は精度が低くなりますが、サンプルサイズが大きくなるにつれてバイアスが大幅に減少します。これは、誤差率が1/log(n)であるためです。最小進化法も同様ですが、非常に大きなデータセットでは精度が低くなります。同様に強力ですが、UPGMAなどの他の選択肢と比較すると、全体的にはるかに複雑です。[11]

UPGMA

UPGMAはクラスタリング手法の一種です。まずクラスター群を構築し、次にそれらをさらにクラスタリングして、最大の潜在的クラスターが得られるまでクラスタリングを行います。その後、逆方向に計算することでグループ間の関係を決定します。特に算術平均を用いることで、より安定したクラスタリングを実現します。全体的に見て、UPGMAは他の比較手法に比べると強力ではありませんが、作成ははるかにシンプルで簡単です。一方、最小進化は全体的に強力ですが、設定が複雑で、NP困難でもあります。[12]

統計的一貫性

ME基準は、通常最小二乗法（OLS）または線形計画法を介して枝長を推定する場合は常に、統計的に一貫していることが知られています。[4] [13] [14] しかし、RzhetskyとNeiの論文で指摘されているように、OLS枝長推定モデルによる最小長を持つ系統樹は、状況によっては、残念ながら生物学的な意味を持たない負の枝長を持つことがあります。[4] この欠点を解決するために、Pauplin [15]は、OLSをバランスのとれた基本進化（BME）と呼ばれる新しい特定の枝長推定モデルに置き換えることを提案しました。 Richard DesperとOlivier Gascuel [16]は、分類群からの推定された進化距離が三角不等式を満たす場合は常に、BME枝長推定モデルによって、最小長系統樹の一般的な統計的一貫性とその枝長の非負性が保証されることを示しました。

Le Sy VinhとArndt von Haeseler [17]は、大規模で体系的なシミュレーション実験によって、BME枝長推定モデルにおけるME基準の精度が距離法の中で群を抜いて高く、最大尤度やベイズ推論などに基づく他の基準の精度に劣らないことを示した。さらに、Daniele Catanzaro、Martin Frohn、Raffaele Pesenti [18]が示したように、BME枝長推定モデルにおける最小長系統は、n個の解析対象分類群を根とするn系統の森によってエンコードされた同時最小エントロピー過程間の（パレート最適な）コンセンサスツリーとして解釈できる。この特定の情報理論に基づく解釈は、系統学におけるあらゆる距離法で共有されていると推測される。

フランソワ・デニスとオリヴィエ・ガスキュエル[19]は、最小進化原理が重み付き最小二乗法と一般化最小二乗法では矛盾することを証明した。彼らは、すべての重みが等しいOLSモデルで使用できるEDGE_LENGTHSと呼ばれるアルゴリズムがあることを示した。このアルゴリズムでは、2つの辺1uと2uの長さを、距離δij(i,j≠1,2)を用いずに計算できる。この性質はWLSモデルでもGLSモデルでも成り立たない。この性質がなければ、ME原理はWLSモデルとGLSモデルで矛盾する。

アルゴリズムの側面

ME基準のもとで、配列の集合から最小和長系統を導く「最小進化問題」（MEP）はNP困難であると言われている。[20] [21]新しいBME基準を用いる「バランス型最小進化問題」（BMEP）はAPX困難である。[20]

BMEPを解く正確なアルゴリズムは数多く発表されている。[22] [23] [24] [25]最もよく知られている正確なアルゴリズム[26]は、マルチプロセス処理を行っても、12種類以上の分類群では実用的ではない。[20]誤差限界が証明された近似アルゴリズムは2012年に発表された1つだけである。

実用上、BMEPはヒューリスティック探索によって実装されることが圧倒的に多い。前述の基本的な近傍結合アルゴリズムは、BMEの貪欲版を実装している。[27]

「最先端」のFastME [20]は、大まかな木構造から始めて、Nearest Neighbor Interchanges（NNI）などの位相的移動を用いて木構造を改善します。NJと比べると、速度はほぼ同等で、精度はより優れています。[28]

FastMEは、すべてのペアワイズ距離の重み付き線形関数を用いてツリーの長さを計算するBalanced Minimum Evolution（BME）原理に基づいて動作します。特定のトポロジのBMEスコアは次のように表されます。

L = ∑ i < j w i j ⋅ d i j {\displaystyle L=\sum _{i<j}w_{ij}\cdot d_{ij}}

ここで、 は分類群との間の進化距離を表し、 は各ペアの寄与を均衡させる位相依存の重みです。このアプローチは、NJのような貪欲アルゴリズムよりも正確な再構築を可能にします。 d i j {\displaystyle d_{ij}} i {\displaystyle i} j {\displaystyle j} w i j {\displaystyle w_{ij}}

このアルゴリズムは、主にサブツリーの枝刈りと再移植（SPR）とNNI操作といった局所的な再配置によってツリートポロジーを改善します。各ステップで、再配置後のツリーのBMEスコアが低下していないか確認します。低下している場合は、変更が保持されます。この反復的な改良により、FastMEは大規模なデータセットであっても、ほぼ最適な解へと効率的に収束することができます。

FastME の簡略化された疑似コード: 

入力: n 個の分類群の距離行列 D
出力: BMEスコアを最小化するTツリー

1. 近傍結合法を用いて初期木Tを構築する
2. 改善が見られなくなるまで繰り返します。
    a. 可能なSPRまたはNNIの移動ごとに、
        i. この動きを適用して新しい木T'を生成する
        ii. T'のBMEスコアを計算する
        iii. スコア(T') < スコア(T)の場合、T = T'とする
3. 最終木Tを返す

DesperとGascuelが報告したシミュレーションでは、FastMEが位相精度においてNJを一貫して上回ることが示されており、特に進化速度が変化したり、距離が厳密な加法性から逸脱したりする場合に顕著である。また、1,000以上の分類群を含むデータセットでもFastMEは効果的に使用されている。[29]

ほとんどの距離ベースの手法と同様に、BMEは入力距離が加法的であると仮定します。この仮定が成り立たない場合（ノイズ、不均一なレート、その他の違反など）、結果として得られるツリーは最適解に近い可能性がありますが、精度に影響が出る可能性があります。FastMEに加えて、遺伝的アルゴリズムやシミュレーテッドアニーリングなどのメタヒューリスティック手法も、最小進化基準の下でツリートポロジーを探索するために使用されており、特に従来のヒューリスティックでは困難となる非常に大規模なデータセットにおいて有効です。[30]

参照

参考文献

  1. ^ Catanzaro, Daniele (2010).分子データからの系統樹推定, ポリマー配列解析および関連問題への数学的アプローチ. Springer, New York.
  2. ^ Catanzaro D (2009). 「最小進化問題：概要と分類」. Networks . 53 (2): 112– 125. doi :10.1002/net.20280. S2CID  6018514.
  3. ^ Kidd KK, Sgaramella-Zonta LA (1971). 「系統解析：概念と方法」. American Journal of Human Genetics . 23 (3): 235– 252. PMC 1706731. PMID  5089842 . 
  4. ^ abcd Rzhetsky A, Nei M (1993). 「系統学的推論における最小進化法の理論的基礎」.分子生物学と進化. 10 : 21073–1095 .
  5. ^ Day WH (1987). 「非類似度行列からの系統樹推定の計算複雑性」.数理生物学会報. 49 (4): 461–7 . doi :10.1007/BF02458863. PMID  3664032.
  6. ^ ゾウ、ユエ;張子軒。ゼン、ユジエ。胡、漢月。ハオ、ユジン。黄、盛。リー、ボー (2024 年 5 月 11 日)。 「系統樹構築の一般的な方法と R での実装」。バイオエンジニアリング。11 (5): 480.土井: 10.3390/bioengineering11050480。PMC 11117635。PMID  38790347。 
  7. ^ Catanzaro, Daniele; Frohn, Martin; Gascuel, Olivier; Pesenti, Raffaele (2022年7月). 「バランス最小進化問題に関するチュートリアル」. European Journal of Operational Research . 300 (1): 1– 19. doi : 10.1016/j.ejor.2021.08.004 . hdl : 10278/3742270 .
  8. ^ Gascuel O, Steel M (2006). 「近隣結合の解明」Mol Biol Evol . 23 (11): 1997– 2000. doi : 10.1093/molbev/msl072 . PMID  16877499.
  9. ^ Studier, JA; Keppler, KJ (1988年11月). 「斎藤と寧の近傍結合アルゴリズムに関する注記」. Molecular Biology and Evolution . 5 (6): 729–31 . doi : 10.1093/oxfordjournals.molbev.a040527 . ISSN  1537-1719. PMID  3221794.
  10. ^ 斎藤成也; 根井正俊 (1987年7月). 「近隣結合法：系統樹再構築のための新しい方法」.分子生物学と進化. 4 (4): 406– 425. doi :10.1093/oxfordjournals.molbev.a040454. PMID  3447015.
  11. ^ フェルゼンシュタイン、ジョセフ (1973). 「離散形質データから進化樹を推定するための最大尤度法と最小ステップ法」. Systematic Zoology . 22 (3): 240– 249. doi :10.2307/2412304. ISSN  0039-7989. JSTOR  2412304.
  12. ^ Moulton, Vincent; Spillner, Andreas; Wu, Taoyang (2018-04-18). 「UPGMAと正規化等距離最小進化問題」.理論計算機科学. 721 : 1–15 . arXiv : 1704.00497 . doi :10.1016/j.tcs.2018.01.022. ISSN  0304-3975.
  13. ^ Desper R, Gascuel O (2005).最小進化距離に基づく系統学的推論アプローチ, 『進化と系統発生の数学』 , オックスフォード大学出版局, ニューヨーク.
  14. ^ カタンツァーロ D、アリンギエリ R、ディ スンマ M、ペゼンティ R (2015)。 「最小進化問題のブランチプライスアンドカットアルゴリズム」。ヨーロッパのオペレーショナルリサーチジャーナル。244 (3): 753–765。土井:10.1016/j.ejor.2015.02.019。S2CID  1549028。
  15. ^ Pauplin Y (2000). 「距離行列を用いた樹木の長さの直接計算」. Journal of Molecular Evolution . 51 (1): 41– 47. Bibcode :2000JMolE..51...41P. doi :10.1007/s002390010065. PMID  10903371. S2CID  8619412.
  16. ^ Desper R, Gascuel O (2004年3月). 「系統分類推論におけるバランス型最小進化法の理論的基礎と重み付き最小二乗法による樹形図フィッティングとの関係」. Molecular Biology and Evolution . 21 (3): 587–98 . doi : 10.1093/molbev/msh049 . PMID  14694080.
  17. ^ Vihn LS, von Haeseler A (2005). 「最短トリプレットクラスタリング：代表セットを用いた大規模系統樹の再構築」BMC Bioinformatics . 6 : 92. doi : 10.1186/1471-2105-6-92 . PMC 1097715 . PMID  15819989. 
  18. ^ Catanzaro D, Frohn M, Pesenti R (2020). 「バランス最小進化問題における情報理論の視点」.オペレーションズ・リサーチ・レターズ. 48 (3): 362– 367. doi :10.1016/j.orl.2020.04.010. hdl : 2078.1/230414 . S2CID  218998400.
  19. ^ Denis F, Gascuel O (2003). 「系統学的推論における最小進化原理の一貫性について」 .離散応用数学. 127 : 63–77 . doi :10.1016/S0166-218X(02)00285-8. ISSN  0166-218X.
  20. ^ abcd Rzhetsky, A., Nei, M. (1993). 系統学的推論における最小進化法の理論的基礎. Molecular Biology and Evolution , 10(5), 1073–1095.
  21. ^ Semple, C., Steel, M. (2003).系統発生学. オックスフォード大学出版局.
  22. ^ Hickey, G., Dehne, F., Rau-Chaplin, A., & Blouin, C. (2008). 生物学的配列データから進化樹を構築するための並列かつメモリ効率の高いアルゴリズム. Journal of Parallel and Distributed Computing , 68(4), 505–515.
  23. ^ Kordi, M., & Bansal, MS (2015). 均衡最小進化問題の複雑性について.理論計算機科学, 596, 77–90.
  24. ^ Chor, B., Hendy, MD, & Snir, S. (2006). 最小エントロピー系統樹.計算生物学ジャーナル, 13(5), 1101–1116.
  25. ^ Gascuel, O., & Steel, M. (2006). 隣接結合の解明.分子生物学と進化, 23(11), 1997–2000.
  26. ^ Kordi, M., & Bansal, MS (2015). 均衡最小進化問題の複雑性について.理論計算機科学, 596, 77–90.
  27. ^ Gascuel, O. (1997). BIONJ: 配列データのシンプルなモデルに基づくNJアルゴリズムの改良版. Molecular Biology and Evolution , 14(7), 685–695.
  28. ^ Desper, R., & Gascuel, O. (2002). 最小進化原理に基づく高速かつ正確な系統樹再構築アルゴリズム. Journal of Computational Biology , 9(5), 687–705.
  29. ^ Desper, R., & Gascuel, O. (2005). 系統学的推論への最小進化距離に基づくアプローチ. Gascuel, O. (編),進化と系統発生の数学. オックスフォード大学出版局, pp. 1–28.
  30. ^ Ali, RA, Dehne, F., Rau-Chaplin, A., & Sack, JR (2009). 大規模系統樹構築のための新しいメタヒューリスティック. 2009 ACM Symposium on Applied Computing Proceedings , 1080–1084.

さらに読む

  • Catanzaro D, Pesenti R, Wolsey L (2020). 「均衡最小進化多面体について」.離散最適化. 36 100570. doi :10.1016/j.disopt.2020.100570. hdl : 2078.1/230413 . S2CID  213389485.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Minimum_evolution&oldid=1314471324"