近隣参加

Bottom-up clustering method for creating phylogenetic trees

バイオインフォマティクスにおいて、近傍結合法は、 1987年に斎藤成也と根井正俊によって考案された、系統樹を作成するためのボトムアップ（凝集型）クラスタリング手法です。 ^[1]通常、DNAまたはタンパク質配列データに基づいており、系統樹を作成するために、各分類群（種または配列など）のペア間の距離に関する知識が必要です。^[2]

アルゴリズム

スター ツリー (A) から開始し、Q 行列を計算して結合するノードのペア (この場合は f と g) を選択します。これらは、(B) に示すように、新しく作成されたノード u に結合されます。実線で示されているツリーの部分は固定され、後続の結合ステップでは変更されません。ノード u からノード ae までの距離は、式 ( 3 ) から計算されます。このプロセスは、ノード a、b、c、d、e、u 間の距離のみの行列と、そこから導出された Q 行列を使用して繰り返されます。この場合、u と e は、(C) に示すように、新しく作成された v に結合されます。さらに 2 回反復すると、まず (D) に進み、次に (E) に進み、ツリーが完全に解決された時点でアルゴリズムが終了します。

近傍結合は、各分類群のペア間の距離を指定する距離行列を入力として受け取ります。このアルゴリズムは、スターネットワークに対応するトポロジを持つ完全に未解決のツリーから開始し、ツリーが完全に解決され、すべての枝の長さが判明するまで、以下の手順を反復します。

1. 現在の距離行列に基づいて、行列（以下に定義）を計算します。 ${\displaystyle Q}$
2. 異なる分類群 i と j のペア（つまり）のうち、が最小となるものを見つけます。分類群 i と j を結ぶ新しいノードを作成し、そのノードを中央のノードに接続します。例えば、右図の(B)では、ノード u は f と g を結ぶために作成されます。 ${\displaystyle i\neq j}$ ${\displaystyle Q(i,j)}$
3. ペア内の各分類群からこの新しいノードまでの距離を計算します。
4. このペアの外側にある各分類群から新しいノードまでの距離を計算します。
5. 結合された近隣ノードのペアを新しいノードに置き換え、前の手順で計算された距離を使用して、アルゴリズムを再度開始します。

Q行列

分類群を関連付ける距離行列に基づいて、次のようにx行列を計算します。 ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle Q}$

${\displaystyle Q(i,j)=(n-2)d(i,j)-\sum _{k=1}^{n}d(i,k)-\sum _{k=1}^{n}d(j,k)}$

1

分類群との間の距離はどこですか。 ${\displaystyle d(i,j)}$ ${\displaystyle i}$ ${\displaystyle j}$

ペアメンバーから新しいノードまでの距離

結合されるペアの各分類群について、次の式を使用して新しいノードまでの距離を計算します。

${\displaystyle \delta (f,u)={\frac {1}{2}}d(f,g)+{\frac {1}{2(n-2)}}\left[\sum _{k=1}^{n}d(f,k)-\sum _{k=1}^{n}d(g,k)\right]\quad }$

2

そして：

${\displaystyle \delta (g,u)=d(f,g)-\delta (f,u)\quad }$

タクサとはペアになっているタクサであり、は新しく作成されたノードです。とととを結ぶ枝、およびそれらの長さ、と は、徐々に作成されるツリーの一部であり、後続の隣接ノード結合ステップに影響を与えず、また、後続の隣接ノード結合ステップによっても影響を受けません。 ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle u}$ ${\displaystyle f}$ ${\displaystyle u}$ ${\displaystyle g}$ ${\displaystyle u}$ ${\displaystyle \delta (f,u)}$ ${\displaystyle \delta (g,u)}$

新しいノードから他の分類群までの距離

前のステップで考慮されなかった各分類群について、新しいノードまでの距離を次のように計算します。

${\displaystyle d(u,k)={\frac {1}{2}}[d(f,k)+d(g,k)-d(f,g)]}$

3

ここで、 は新しいノード、は距離を計算するノード、は結合したばかりのペアのメンバーです。 ${\displaystyle u}$ ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle g}$

複雑

分類群の集合に対する近傍結合には 反復処理が必要です。各ステップで行列を構築し、探索する必要があります。行列の初期サイズはで、次のステップでは、などとなります。これを直接的に実装すると、時間計算量が のアルゴリズムが得られます。^[3]ヒューリスティックを用いて平均的にこれよりもはるかに優れた性能を実現する実装も存在します。^[4] ${\displaystyle n}$ ${\displaystyle n-3}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle n\times n}$ ${\displaystyle (n-1)\times (n-1)}$ ${\displaystyle O(n^{3})}$

例

5つの分類群による近傍結合。この場合、2回の近傍結合ステップで、完全に解決されたトポロジを持つ木が得られます。結果として得られる木の枝には、長さがラベル付けされています。

5 つの分類群と次の距離行列があると仮定します。 ${\displaystyle (a,b,c,d,e)}$ ${\displaystyle D}$

	1つの	b	c	d	e
1つの	0	5	9	9	8
b	5	0	10	10	9
c	9	10	0	8	7
d	9	10	8	0	3
e	8	9	7	3	0

最初のステップ

最初の参加

値は式（1 ）で計算します。例えば、 ${\displaystyle Q_{1}}$

${\displaystyle Q_{1}(a,b)=(n-2)d(a,b)-\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)}$

${\displaystyle =(5-2)\times 5-(5+9+9+8)-(5+10+10+9)=15-31-34=-50}$

行列については次の値が得られます（行列の対角要素は使用されないため、ここでは省略されています）。 ${\displaystyle Q_{1}}$

	1つの	b	c	d	e
1つの		−50	−38	−34	−34
b	−50		−38	−34	−34
c	−38	−38		−40	−40
d	−34	−34	−40		−48
e	−34	−34	−40	−48

上記の例では、 です。これは の最小値なので、要素とを結合します。 ${\displaystyle Q_{1}(a,b)=-50}$ ${\displaystyle Q_{1}}$ ${\displaystyle a}$ ${\displaystyle b}$

最初の枝の長さの推定

新しいノードをと表記する。上記の式( 2 )により、 と を結ぶ枝の 長さは次のようになる。 ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$

${\displaystyle \delta (a,u)={\frac {1}{2}}d(a,b)+{\frac {1}{2(5-2)}}\left[\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)\right]\quad ={\frac {5}{2}}+{\frac {31-34}{6}}=2}$

${\displaystyle \delta (b,u)=d(a,b)-\delta (a,u)\quad =5-2=3}$

最初の距離行列の更新

次に、初期距離行列を新しい距離行列（下記参照）に更新します。この行列は、をその近傍 に結合したため、1行1列分サイズが縮小されます。上記の式（ 3 ）を用いて、 からおよび以外の各ノードまでの距離を計算します。この場合、以下の式が得られます。 ${\displaystyle D}$ ${\displaystyle D_{1}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle d(u,c)={\frac {1}{2}}[d(a,c)+d(b,c)-d(a,b)]={\frac {9+10-5}{2}}=7}$

${\displaystyle d(u,d)={\frac {1}{2}}[d(a,d)+d(b,d)-d(a,b)]={\frac {9+10-5}{2}}=7}$

${\displaystyle d(u,e)={\frac {1}{2}}[d(a,e)+d(b,e)-d(a,b)]={\frac {8+9-5}{2}}=6}$

結果の距離行列は次のようになります。 ${\displaystyle D_{1}}$

	あなた	c	d	e
あなた	0	7	7	6
c	7	0	8	7
d	7	8	0	3
e	6	7	3	0

太字の値は新しく計算された距離に対応しますが、斜体の値は分類群の最初の結合に関係しない要素間の距離に対応するため、マトリックスの更新による影響を受けません。 ${\displaystyle D_{1}}$

第二段階

2回目の参加

対応する行列は次のようになります。 ${\displaystyle Q_{2}}$

	あなた	c	d	e
あなた		−28	−24	−24
c	−28		−24	−24
d	−24	−24		−28
e	−24	−24	−28

とを結合するか、 と を結合するかを選択できます。どちらのペアも の最小値を持ち、どちらを選択しても同じ結果になります。具体的には、 と を結合し、新しいノードを と呼びます。 ${\displaystyle u}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle Q_{2}}$ ${\displaystyle -28}$ ${\displaystyle u}$ ${\displaystyle c}$ ${\displaystyle v}$

2番目の枝の長さの推定

と を接続する枝の長さは 次のように計算できます。 ${\displaystyle u}$ ${\displaystyle c}$ ${\displaystyle v}$

${\displaystyle \delta (u,v)={\frac {1}{2}}d(u,c)+{\frac {1}{2(4-2)}}\left[\sum _{k=1}^{4}d(u,k)-\sum _{k=1}^{4}d(c,k)\right]\quad ={\frac {7}{2}}+{\frac {20-22}{4}}=3}$

${\displaystyle \delta (c,v)=d(u,c)-\delta (u,v)\quad =7-3=4}$

要素の結合と枝の長さの計算により、図に示すように隣接結合ツリーを描画できます。

2回目の距離行列更新

残りの 3 つのノード、、、の更新された距離行列が計算されます。 ${\displaystyle D_{2}}$ ${\displaystyle v}$ ${\displaystyle d}$ ${\displaystyle e}$

${\displaystyle d(v,d)={\frac {1}{2}}[d(u,d)+d(c,d)-d(u,c)]={\frac {7+8-7}{2}}=4}$

${\displaystyle d(v,e)={\frac {1}{2}}[d(u,e)+d(c,e)-d(u,c)]={\frac {6+7-7}{2}}=3}$

	v	d	e
v	0	4	3
d	4	0	3
e	3	3	0

最終ステップ

この時点でツリートポロジは完全に解決されています。ただし、わかりやすくするために、行列を計算してみましょう。例えば、 ${\displaystyle Q_{3}}$

${\displaystyle Q_{3}(v,e)=(3-2)d(v,e)-\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(e,k)=3-7-6=-10}$

	v	d	e
v		−10	−10
d	−10		−10
e	−10	−10

具体的には、 と を結合して最後のノードを とします。残りの3つの枝の長さは次のように計算できます。 ${\displaystyle v}$ ${\displaystyle d}$ ${\displaystyle w}$

${\displaystyle \delta (v,w)={\frac {1}{2}}d(v,d)+{\frac {1}{2(3-2)}}\left[\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(d,k)\right]\quad ={\frac {4}{2}}+{\frac {7-7}{2}}=2}$

${\displaystyle \delta (w,d)=d(v,d)-\delta (v,w)=4-2=2}$

${\displaystyle \delta (w,e)=d(v,e)-\delta (v,w)=3-2=1}$

図に示すように、隣接結合ツリーが完成しました。

結論：加法距離

この例は理想的なケースを表しています。ツリーの枝に沿って任意の分類群から他の分類群に移動し、移動した枝の長さを合計すると、結果は入力距離行列におけるそれらの分類群間の距離に等しくなります。例えば、からに移動すると、となります。このように距離が何らかのツリーと一致する距離行列は「加法的」であると言われますが、これは実際にはまれな特性です。それでもなお、加法的な距離行列を入力として与えられた場合、近傍結合によって、分類群間の距離がそれに一致するツリーが確実に見つかるということに注意することが重要です。 ${\displaystyle d}$ ${\displaystyle b}$ ${\displaystyle 2+2+3+3=10}$

最小進化としての近隣参加

近傍結合は、均衡最小進化^[5] （BME）基準のための貪欲なヒューリスティックと見なすことができます。BMEは、各トポロジーについて、ツリー長（枝長の合計）を距離行列における距離の特定の重み付き和として定義します。重みはトポロジーによって異なります。BMEの最適トポロジーとは、このツリー長を最小化するトポロジーです。NJは各ステップにおいて、推定ツリー長の減少が最大となる分類群のペアを貪欲に結合します。この手順はBME基準の最適解を見つけることを保証するものではありませんが、多くの場合最適解が得られ、通常は非常に近い結果が得られます。^[5]

メリットとデメリット

NJ法の主な利点は、最小二乗法、最大節約法、最大尤度法に比べて高速であることです^{[6] : 466  [6]} 。 これにより、NJ法は、大規模なデータセット（数百または数千の分類群）の解析やブートストラッピングに実用的になります。これらの目的では、最大節約法や最大尤度法などの他の解析手段では計算上法外な場合があります。

近傍結合では、入力距離行列が正しければ、出力ツリーも正しいという性質がある。さらに、距離行列が「ほぼ加法的」である限り、具体的には距離行列の各エントリが真の距離とツリーの最短枝長の半分未満しか違わない限り、出力ツリー トポロジの正しさが保証される。^[7]実際には距離行列がこの条件を満たすことはめったにないが、近傍結合によってとにかく正しいツリー トポロジが構築されることが多い。^[8]ほぼ加法的距離行列に対する近傍結合の正しさは、多くの進化モデルにおいて統計的に一貫していることを意味する。つまり、十分な長さのデータが与えられると、近傍結合によって真のツリーが高確率で再構築される。UPGMAやWPGMAと比較して、近傍結合には、すべての系統が同じ速度で進化すると仮定しないという利点がある (分子時計仮説)。

しかしながら、近隣結合法は、距離の尺度に依存せず、ほとんどの状況で優れた精度を提供する系統学的手法に大部分取って代わられました。^[要出典]近隣結合法には、枝の一部に負の長さが割り当てられることが多いという望ましくない特徴があります。

実装とバリエーション

近傍結合を実装したプログラムは数多く存在します。標準的なNJ（つまり、古典的なNJ最適化基準を用いており、同じ結果が得られる）の実装の中では、RapidNJ（2003年開始、2011年にメジャーアップデート、2023年現在もアップデート中）^[9]とNINJA（2009年開始、最終アップデート2013年）^[10]が最先端と考えられています。これらのプログラムの実行時間は、分類群の数の2乗にほぼ比例します。

標準から逸脱するバリアントには次のものがあります:

• BIONJ (1997) ^[11]とWeighbor (2000) ^[12]は、距離行列における短い距離は長い距離よりも一般的によく知られているという事実を利用して精度を向上させました。これら2つの手法は、不完全な距離行列にも適用できるように拡張されています。^[13]
• 「高速NJ」は最適なノードを記憶し、常にO(n^2)の計算量です。「リラックスNJ」は山登り探索を行い、最悪のケースでもO(n^3)の計算量を維持します。高速NJは、単純なリラックスNJよりも高速です。^[14]
• FastMEは、密接に関連する均衡最小進化法（BME）の実装です（§ 最小進化としての近傍結合を参照）。これはNJ法とほぼ同等の速度で、より正確です。まず大まかな木構造から始め、次に最近傍交換（NNI）などの位相的移動を用いて木構造を改善します。^[15] FastTreeは関連する手法です。これは行列ではなく、配列の「プロファイル」を扱います。まず近似的にNJ法の木構造から始め、それをBME法に再配置し、さらに近似的に最大尤度法に再配置します。^[16]

参照

• 最近傍探索
• UPGMAとWPGMA
• 最小限の進化

参考文献

1. 斎藤 暢; 根井 正之 (1987年7月1日). 「近隣結合法：系統樹再構築のための新しい手法」.分子生物学と進化. 4 (4): 406– 425. doi : 10.1093/oxfordjournals.molbev.a040454 . PMID  3447015.
2. Xavier Didelot (2010). 「細菌集団構造の配列ベース解析」. D. Ashley Robinson、Daniel Falush、Edward J. Feil (編) 『感染症における細菌集団遺伝学』 . John Wiley and Sons. pp.  46– 47. ISBN 978-0-470-42474-2。
3. 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.
4. Mailund, Thomas; Brodal, GerthS; Fagerberg, Rolf; Pedersen, Christian NS; Phillips, Derek (2006). 「近隣結合法の再構築」BMC Bioinformatics . 7 (1): 29. doi : 10.1186/1471-2105-7-29 . PMC 3271233 . PMID  16423304. 
5. Gascuel O, Steel M (2006). 「隣接結合の解明」Mol Biol Evol . 23 (11): 1997– 2000. doi : 10.1093/molbev/msl072 . PMID  16877499.
6. Kuhner, MK; Felsenstein, J. (1994-05-01). 「等進化速度および不等進化速度下における系統発生アルゴリズムのシミュレーション比較」. Molecular Biology and Evolution . 11 (3): 459– 468. doi : 10.1093/oxfordjournals.molbev.a040126 . ISSN  0737-4038. PMID  8015439.
7. Atteson K (1997). 「系統樹再構築における近傍結合アルゴリズムの性能」pp. 101–110. Jiang, T., Lee, D.編, Lecture Notes in Computer Science, 1276 , Springer-Verlag, Berlin. COCOON '97.
8. Mihaescu R, Levy D, Pachter L (2009). 「なぜ近隣結合が機能するのか」. Algorithmica . 54 (1): 1– 24. arXiv : cs/0602041 . doi :10.1007/s00453-007-9116-4. S2CID  2462145.{{cite journal}}: CS1 maint: multiple names: authors list (link)
9. "RapidNJ" . birc.au.dk.
10. 「NINJA: 大規模近傍結合系統学推論ツール - ホーム」wheelerlab.org。
11. “ATGC: BioNJ”. www.atgc-montpellier.fr。
12. “WEIGHBOR Homepage”. 2015年3月5日. オリジナルより2015年3月5日時点のアーカイブ。
13. Criscuolo, Alexis; Gascuel, Olivier (2008年12月). 「不完全距離行列を扱うためのNJ型高速アルゴリズム」. BMC Bioinformatics . 9 (1): 166. doi : 10.1186/1471-2105-9-166 . PMC 2335114 . PMID  18366787. 
14. Simonsen, Martin; Mailund, Thomas; Pedersen, Christian NS (2008). 「高速隣接結合」(PDF) .バイオインフォマティクスにおけるアルゴリズム. コンピュータサイエンス講義ノート. 第5251巻. pp.  113– 122. doi :10.1007/978-3-540-87361-7_10. ISBN 978-3-540-87360-0。
15. 「ATGC: FastME」. www.atgc-montpellier.fr。
16. 「FastTree 2.1: 大規模アライメントの近似最大尤度ツリー」www.microbesonline.org。

その他の情報源

• Studier JA, Keppler KJ (1988). 「SaitouとNeiの近傍結合アルゴリズムに関する注記」. Mol Biol Evol . 5 (6): 729– 731. doi : 10.1093/oxfordjournals.molbev.a040527 . PMID  3221794.
• Martin Simonsen、Thomas Mailund、Christian NS Pedersen (2008). 「高速隣接結合」.バイオインフォマティクスにおけるアルゴリズム. コンピュータサイエンス講義ノート. 第5251巻. pp.  113– 122. CiteSeerX  10.1.1.218.2078 . doi :10.1007/978-3-540-87361-7_10. ISBN 978-3-540-87360-0。

外部リンク

• 近隣結合法 2021年7月9日アーカイブWayback Machine — チュートリアル

Retrieved from "https://en.wikipedia.org/w/index.php?title=Neighbor_joining&oldid=1307129874"