ロビンソン・ファウルズ計量

ロビンソン・ファウルズ距離または対称差測定法は、しばしばRF距離と略され、系統樹間の距離を計算する簡単な方法である。^[1]

これは ( A + B )として定義されます。ここで、 A は最初のツリーによって暗示されるが 2 番目のツリーには示されないデータのパーティションの数であり、Bは 2 番目のツリーによって暗示されるが最初のツリーには示されないデータのパーティションの数です (ただし、一部のソフトウェア実装では RF メトリックを 2 で割ります^[2]。また、RF 距離を最大値 1 にスケーリングするものもあります)。パーティションは、各ブランチを削除することによって各ツリーに対して計算されます。したがって、各ツリーの適格なパーティションの数は、そのツリーのブランチの数に等しくなります。

RF距離は偏りがあると批判されてきたが^[3]、系統樹間の距離を比較的直感的に測定できるため、広く使用され続けている（ロビンソン・ファウルズ距離を説明した1981年の元の論文^[1]は、 Google Scholarによると2023年までに2700回以上引用されている）。とはいえ、RF距離に内在する偏りを考えると、研究者は「一般化された」ロビンソン・ファウルズ指標^[4]の使用を検討すべきである。この指標は理論的にも実際的にもパフォーマンスが良く、元の指標の偏りや誤解を招く属性を回避できる可能性がある。

2つの根無し木と各ノードのラベルのセット（つまり、分類群）（空でもよいが、次数が3以上のノードのみが空セットでラベル付けできる）が与えられた場合、ロビンソン・ファウルズ計量は、一方を他方に変換するための操作の数と操作の数を見つける。操作の数によって距離が定義される。根付き木は、ルートノードにダミーの葉を取り付けることで調べることができる。^[5]${\displaystyle \alpha}$${\displaystyle \alpha^{-1}}$

著者は、2 つのツリーが同型であり、同型性がラベル付けを保存する場合、それらのツリーは同じであると定義しています。証明の構築は、 と呼ばれる関数に基づいています。この関数は、エッジを縮小します (ノードを結合して、それらのセットの和集合を作成します)。逆に、はエッジを展開します (デコントラクション)。この場合、セットは任意の方法で分割できます。 ${\displaystyle \alpha}$${\displaystyle \alpha^{-1}}$

関数は、 に含まれないからのすべてのエッジを削除してを作成し、その後 を使用して、 でのみ発見されたエッジをツリーに追加してを構築します 。これらの各手順で実行される操作の数は、 に含まれない のエッジの数と、に含まれないのエッジの数の合計に等しくなります。操作の合計は、から への変換、またはその逆の変換に等しくなります。 ${\displaystyle \alpha}$${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle T_{1}\wedge T_{2}}$${\displaystyle \alpha^{-1}}$${\displaystyle T_{2}}$${\displaystyle T_{1}\wedge T_{2}}$${\displaystyle T_{2}}$${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle T_{2}}$${\displaystyle T_{1}}$${\displaystyle T_{1}}$${\displaystyle T_{2}}$

RF距離は、2つのツリーの厳密なコンセンサスの解像度を反映する同等の類似性メトリックに対応し、1980年にツリーを比較するために初めて使用されました。^[6]

1981年の論文^[1]で、ロビンソンとファウルズは距離が実際には測定基準であることを証明した。

1985 年に Day は、ツリー内のノードの数に線形の複雑さのみを持つこの距離を計算する、完全ハッシュに基づくアルゴリズムを発表しました。必ずしも完全ではないハッシュ テーブルを使用するランダム化アルゴリズムは、線形以下の時間で、制限された誤差で Robinson-Foulds 距離を近似することが示されています。

系統学では、メトリックは 2 つのツリー間の距離を計算するためによく使用されます。PHYLIP スイートの treedist プログラムでは、RAxML_standard パッケージ、DendroPy Python ライブラリ (「対称差メトリック」という名前)、R パッケージ TreeDist (`RobinsonFoulds()` 関数) および phangorn (`treedist()` 関数) と同様に、この機能が提供されています。ツリーのグループを比較する場合、最も高速な実装には HashRF と MrsRF が含まれます。

ロビンソン・ファウルズ測定基準は、言語同士の関係を表すツリー間の距離を計算するために、 定量的比較言語学でも使用されてきました。

RF メトリックは、多くの系統学者にとって、一対のツリー間で異なる分岐の数を使用するという考え方の方がツリー間の違いを評価する比較的直感的な方法であるため、広く使用されています。これが RF 距離の主な強みであり、系統学で引き続き使用されている理由です。もちろん、一対のツリー間で異なる分岐の数はツリー内の分類群の数に依存するため、この単位は意味がないと主張する人もいるかもしれません。ただし、RF 距離を 0 から 1 の範囲に正規化するのは簡単です。

しかし、RFメトリックには理論的にも実践的にもいくつかの欠点がある。^{[7] [5]}

• 他の指標と比較すると感度が低く、不正確です。ツリー内の分類群の数よりも2つ少ない異なる値を取ることができます。^{[7] [5]}
• 急速に飽和し、非常に類似した木に最大距離値が割り当てられる可能性がある。^[7]
• その値は直感に反することもあります。一例として、木の先端とその隣の先端を特定の点に移動すると、2つの先端のうちの1つだけを同じ場所に移動した場合よりも差の値が低くなります。 ^[7]
• その値の範囲は木の形状に依存する。不均等な分割を多く含む木は、均等な分割を多く含む木よりも平均して比較的低い距離を要求する。^[7]
• シミュレーションされた木に基づく実際の設定では、他の多くの測定方法よりもパフォーマンスが低い。^[5]

RF 距離を使用する際に考慮すべきもう 1 つの問題は、1 つの系統群の違いが些細な場合 (系統群が属内の 3 つの種を別々に分解する場合など) や根本的な場合 (系統群がツリーの奥深くにあり、哺乳類や鳥類などの 2 つの基本的なサブグループを定義する場合など) があるということです。ただし、この問題は RF 距離自体の問題ではなく、ツリー距離に対するより一般的な批判です。特定のツリー距離の動作に関係なく、実践的な進化生物学者は、一部のツリーの再配置を「重要」と見なし、他の再配置を「些細」と見なす場合があります。ツリー距離はツールであり、ツリー内の生物に関するその他の情報のコンテキストで最も役立ちます。

これらの問題は、あまり保守的ではないメトリックを使用することで対処できます。「一般化 RF 距離」は、類似しているが同一ではない分割間の類似性を認識します。元の Robinson Foulds 距離では、2 つのグループがどれだけ類似しているかは考慮されず、同一でない場合は破棄されます。^[4]

最も優れた一般化ロビンソン・ファウルズ距離は情報理論に基づいており、ツリーの分岐が共通して保持する情報量（ビット単位で測定）に基づいてツリー間の距離を測定します。^[5] クラスタリング情報距離（RパッケージTreeDistで実装）は、ロビンソン・ファウルズ距離の最も適切な代替として推奨されています。^[5]

ツリー距離計算の別のアプローチは、ツリー比較の基礎として、分割ではなく四重距離を使用することです。 ^[7]

• M. Bourque、Arbres de Steiner et reseaux は、局在化変数を特定するものを特定しません。博士論文、モントリオール大学、モントリオール、ケベック州、1978 http://www.worldcat.org/title/arbres-de-steiner-et-reseaux-dont-certains-sommets-sont-a-localisation-variable/oclc/ 053538946
• Robinson, DR; Foulds, LR (1981). 「系統樹の比較」.数理生物科学. 53 (1–2): 131–147. doi :10.1016/0025-5564(81)90043-2.
• William HE Day、「ラベル付き葉を持つツリーを比較するための最適アルゴリズム」、Journal of Classification、第 1 号、1985 年 12 月。doi : 10.1007/BF01908061
• Makarenkov, V および Leclerc, B. 循環順序を使用した加法ツリーの比較、Journal of Computational Biology、7、5、731-744、2000、「Mary Ann Liebert、Inc.」
• Pattengale, Nicholas D.; Gottlieb, Eric J.; Moret, Bernard ME (2007). 「Robinson–Foulds Metric の効率的な計算」. Journal of Computational Biology . 14 (6): 724–735. CiteSeerX  10.1.1.75.3338 . doi :10.1089/cmb.2007.R012. PMID  17691890.
• Sukumaran, J.; Holder, Mark T. (2010). 「DendroPy: 系統発生計算のための Python ライブラリ」.バイオインフォマティクス. 26 (12): 1569–1571. doi : 10.1093/bioinformatics/btq228 . PMID  20421198.