最小限の進化

最小進化法は系統モデル化に用いられる距離法である。最大節約法と同様に、枝の長さの合計が最短となる系統樹を探すという側面を持つ。 ^[1]^[2]

最小進化 (ME) 基準の理論的基礎は、Kidd と Sgaramella-Zonta (1971) ^[3]および Rzhetsky と Nei (1993) ^[4]の両氏の独創的な研究にあります。これらの枠組みでは、分類群の分子配列は、それらの相違点の一連の尺度 (いわゆる「進化距離」) に置き換えられ、基本的な結果では、そのような距離が分類群からの真の進化距離(つまり、分類群のすべての分子データが利用可能である場合に得られる距離) の偏りのない推定値である場合、分類群の真の系統樹は、それらの距離と互換性のある他の可能性のある系統樹 T よりも短いと予想されます。

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

最大限の節約

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

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

近隣への参加

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

統計的一貫性

ME基準は、枝の長さが最小二乗法（OLS）または線形計画法によって推定されるときはいつでも、統計的に一貫していることが知られています。^[4]^[7]^[8] しかし、RzhetskyとNeiの論文で観察されているように、OLS枝長推定モデルで最小の長さを持つ系統は、状況によっては、残念ながら生物学的な意味を持たない負の枝長によって特徴付けられる場合があります。^[4]

この欠点を解決するために、Pauplin ^{[9] は、} OLS をバランスのとれた基本進化(BME) と呼ばれる新しい特定の枝長推定モデルに置き換えることを提案しました。Richard Desper とOlivier Gascuel ^{[10] は}、分類群からの推定進化距離が三角不等式を満たす場合はいつでも、BME 枝長推定モデルが、最小長系統の一般的な統計的一貫性と、その枝長の非負性を保証することを示しました。

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

アルゴリズムの側面

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

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

実用上、BMEPはヒューリスティック検索によって実装されることが圧倒的に多い。前述の基本的な近傍結合アルゴリズムは、BMEPの貪欲バージョンを実装している。^[6]「最先端」のFastME ^[5]は、大まかな木から始めて、最近傍交換(NNI)などの一連の位相的移動を使用してそれを改善していく。NJと比較すると、速度は同等で、精度も高い。^[20] メタヒューリスティックも使用されている。^[21]

参照

参考文献

^ Catanzaro, Daniele (2010).分子データからの系統樹の推定、ポリマー配列分析および関連問題への数学的アプローチ。Springer、ニューヨーク。
^ Catanzaro D (2009). 「最小進化問題: 概要と分類」.ネットワーク. 53 (2): 112–125. doi :10.1002/net.20280. S2CID 6018514.
^ Kidd KK, Sgaramella-Zonta LA (1971). 「系統解析：概念と方法」.アメリカ人類遺伝学ジャーナル. 23 (3): 235–252. PMC 1706731. PMID 5089842 .
^ abcd Rzhetsky A, Nei M (1993). 「系統学的推論における最小進化法の理論的基礎」.分子生物学と進化. 10 : 21073–1095.
^ abcde 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 .
^ ab Gascuel O, Steel M (2006). 「近隣結合の解明」Mol Biol Evol . 23 (11): 1997–2000. doi : 10.1093/molbev/msl072 . PMID 16877499.
^ Desper R、Gascuel O (2005)。「進化と系統発生の数学」における系統推定への最小進化距離ベースのアプローチ。オックスフォード大学出版局、ニューヨーク。
^ カタンツァーロ D、アリンギエリ R、ディスンマ M、ペゼンティ R (2015)。「最小進化問題のブランチプライスアンドカットアルゴリズム」。ヨーロッパのオペレーショナルリサーチジャーナル。244 (3): 753–765。土井：10.1016/j.ejor.2015.02.019。S2CID 1549028。
^ Pauplin Y (2000). 「距離行列を使用したツリーの長さの直接計算」. Journal of Molecular Evolution . 51 (1): 41–47. Bibcode :2000JMolE..51...41P. doi :10.1007/s002390010065. PMID 10903371. S2CID 8619412.
^ Desper R 、 Gascuel O (2004 年 3 月)。「系統学的推論におけるバランス最小進化法の理論的基礎と重み付き最小二乗法によるツリーフィッティングとの関係」。分子生物学と進化。21 ( 3): 587–98。doi : 10.1093/molbev/msh049。PMID 14694080。
^ Vihn LS 、 von Haeseler A (2005)。「最短トリプレットクラスタリング：代表セットを使用した大規模系統樹の再構築」。BMCバイオインフォマティクス。6：1–14。doi ：10.1186/ 1471-2105-6-92。PMC 1097715。PMID 15819989。
^ Catanzaro D、Frohn M、Pesenti R (2020)。「バランス最小進化問題に関する情報理論の観点」。オペレーションズ・リサーチ・レターズ。48 (3): 362–367。doi :10.1016/ j.orl.2020.04.010。S2CID 218998400 。
^ Catanzaro D, Labbé M, Pesenti R, Salazar-González JJ (2009). 「最小進化基準の下で系統樹を再構築するための数学モデル」.ネットワーク. 53 (2): 126–140. doi :10.1002/net.20281. S2CID 17792339.
^ カタンツァーロ D、アリンギエリ R、ディスンマ M、ペゼンティ R (2015)。「最小進化問題のブランチプライスアンドカットアルゴリズム」。ヨーロッパのオペレーショナルリサーチジャーナル。244 (3): 753–765。土井：10.1016/j.ejor.2015.02.019。S2CID 1549028。
^ Aringhieri R、Catanzaro D、Di Summa M (2011)。「 バランスのとれた最小進化問題の最適解」。Computers and Operations Research。38 ( 12): 1845–1854。doi :10.1016/j.cor.2011.02.020。hdl : 2318 / 86826。S2CID 9514013 。
^ カタンザーロ D、ラベ M、ペセンティ R、サラザール＝ゴンサレス JJ (2012)。「均衡最小進化問題」。INFORMS ジャーナル・オン・コンピューティング。24 (2): 276–294。土井：10.1287/ijoc.1110.0455。
^ Catanzaro D、Labbé M、Pesenti R (2013)。「不確実なデータの下でのバランスのとれ た最小進化問題」。離散応用数学。161 (13–14): 1789–1804。doi : 10.1016/ j.dam.2013.03.012。
^ Catanzaro D 、 Pesenti R (2019)。「バランスのとれた最小進化多面体の頂点の列挙」。コンピューターとオペレーションズリサーチ。109 :209–217。doi :10.1016/ j.cor.2019.05.001。S2CID 164835227 。
^ Catanzaro D、Pesenti R、 Wolsey L (2020)。「バランスのとれた最小進化多面体について」。離散最適化。36 :100570。doi : 10.1016/j.disopt.2020.100570。S2CID 213389485 。
^ 「ATGC: FastME」. www.atgc-montpellier.fr。
^ Catanzaro D、Pesenti R 、 Milinkovitch MC (2007) 。「最小進化原理に基づく系統発生推定のためのアリコロニー最適化アルゴリズム」。BMC Evolutionary Biology。7 : 228。doi : 10.1186 /1471-2148-7-228。PMC 2211314。PMID 18005416。

さらに読む

Catanzaro D、Pesenti R、 Wolsey L (2020)。「バランスのとれた最小進化多面体について」。離散最適化。36 :100570。doi : 10.1016/j.disopt.2020.100570。S2CID 213389485。

[1] Catanzaro, Daniele (2010).分子データからの系統樹の推定、ポリマー配列分析および関連問題への数学的アプローチ。Springer、ニューヨーク。

[2] Catanzaro D (2009). 「最小進化問題: 概要と分類」.ネットワーク. 53 (2): 112–125. doi :10.1002/net.20280. S2CID 6018514.

[Kidd71-3] Kidd KK, Sgaramella-Zonta LA (1971). 「系統解析：概念と方法」.アメリカ人類遺伝学ジャーナル. 23 (3): 235–252. PMC 1706731. PMID 5089842 .

[Rz93-4] Rzhetsky A, Nei M (1993). 「系統学的推論における最小進化法の理論的基礎」.分子生物学と進化. 10 : 21073–1095.

[Catanzaro2022-5] 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 .

[gascuel-6] Gascuel O, Steel M (2006). 「近隣結合の解明」Mol Biol Evol . 23 (11): 1997–2000. doi : 10.1093/molbev/msl072 . PMID 16877499.

[7] Desper R、Gascuel O (2005)。「進化と系統発生の数学」における系統推定への最小進化距離ベースのアプローチ。オックスフォード大学出版局、ニューヨーク。

[8] カタンツァーロ D、アリンギエリ R、ディスンマ M、ペゼンティ R (2015)。「最小進化問題のブランチプライスアンドカットアルゴリズム」。ヨーロッパのオペレーショナルリサーチジャーナル。244 (3): 753–765。土井：10.1016/j.ejor.2015.02.019。S2CID 1549028。

[9] Pauplin Y (2000). 「距離行列を使用したツリーの長さの直接計算」. Journal of Molecular Evolution . 51 (1): 41–47. Bibcode :2000JMolE..51...41P. doi :10.1007/s002390010065. PMID 10903371. S2CID 8619412.

[10] ^ Desper R 、 Gascuel O (2004 年 3 月)。「系統学的推論におけるバランス最小進化法の理論的基礎と重み付き最小二乗法によるツリーフィッティングとの関係」。分子生物学と進化。21 ( 3): 587–98。doi : 10.1093/molbev/msh049。PMID 14694080。

[11] ^ Vihn LS 、 von Haeseler A (2005)。「最短トリプレットクラスタリング：代表セットを使用した大規模系統樹の再構築」。BMCバイオインフォマティクス。6：1–14。doi ：10.1186/ 1471-2105-6-92。PMC 1097715。PMID 15819989。

[12] Catanzaro D、Frohn M、Pesenti R (2020)。「バランス最小進化問題に関する情報理論の観点」。オペレーションズ・リサーチ・レターズ。48 (3): 362–367。doi :10.1016/ j.orl.2020.04.010。S2CID 218998400 。

[13] Catanzaro D, Labbé M, Pesenti R, Salazar-González JJ (2009). 「最小進化基準の下で系統樹を再構築するための数学モデル」.ネットワーク. 53 (2): 126–140. doi :10.1002/net.20281. S2CID 17792339.

[14] カタンツァーロ D、アリンギエリ R、ディスンマ M、ペゼンティ R (2015)。「最小進化問題のブランチプライスアンドカットアルゴリズム」。ヨーロッパのオペレーショナルリサーチジャーナル。244 (3): 753–765。土井：10.1016/j.ejor.2015.02.019。S2CID 1549028。

[15] ^ Aringhieri R、Catanzaro D、Di Summa M (2011)。「 バランスのとれた最小進化問題の最適解」。Computers and Operations Research。38 ( 12): 1845–1854。doi :10.1016/j.cor.2011.02.020。hdl : 2318 / 86826。S2CID 9514013 。

[16] カタンザーロ D、ラベ M、ペセンティ R、サラザール＝ゴンサレス JJ (2012)。「均衡最小進化問題」。INFORMS ジャーナル・オン・コンピューティング。24 (2): 276–294。土井：10.1287/ijoc.1110.0455。

[17] ^ Catanzaro D、Labbé M、Pesenti R (2013)。「不確実なデータの下でのバランスのとれ た最小進化問題」。離散応用数学。161 (13–14): 1789–1804。doi : 10.1016/ j.dam.2013.03.012。

[18] ^ Catanzaro D 、 Pesenti R (2019)。「バランスのとれた最小進化多面体の頂点の列挙」。コンピューターとオペレーションズリサーチ。109 :209–217。doi :10.1016/ j.cor.2019.05.001。S2CID 164835227 。

[19] ^ Catanzaro D、Pesenti R、 Wolsey L (2020)。「バランスのとれた最小進化多面体について」。離散最適化。36 :100570。doi : 10.1016/j.disopt.2020.100570。S2CID 213389485 。

[20] 「ATGC: FastME」. www.atgc-montpellier.fr。

[21] ^ Catanzaro D、Pesenti R 、 Milinkovitch MC (2007) 。「最小進化原理に基づく系統発生推定のためのアリコロニー最適化アルゴリズム」。BMC Evolutionary Biology。7 : 228。doi : 10.1186 /1471-2148-7-228。PMC 2211314。PMID 18005416。