近隣への参加

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

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

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

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

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

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

そして：

${\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 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 つの分類群と次の距離行列があると仮定します。 ${\displaystyle (a,b,c,d,e)}$${\displaystyle D}$

値は式（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}}$

上記の例では、です。これは の最小値なので、要素と を結合します。 ${\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}}$

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

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

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

とを接続する枝の長さは 次のように計算できます。 ${\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}$

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

残りの 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}$

この時点でツリー トポロジは完全に解決されています。ただし、わかりやすくするために、マトリックスを計算することもできます。例: ${\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}$

具体的には、 と を結合して最後のノードを と呼びます。残りの 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]これ により、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 法とほぼ同程度に高速で、より正確です。まず大まかなツリーから始めて、Nearest Neighbor Interchanges (NNI) などの一連のトポロジカルな動きを使用してツリーを改善します。 ^[15] FastTree は関連する方法です。これは、マトリックスではなくシーケンス「プロファイル」で動作します。まず、ほぼ NJ ツリーから始めて、それを BME に再配置し、次にそれをほぼ最大尤度に再配置します。^[16]

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

• 近隣結合法 - チュートリアル