近隣結合法

近隣結合法(NJ 法)は、進化速度が一定であるという仮定がなくても、系統樹を構成することができる。

近隣結合法における、クラスター間の距離は次のように定義されている。(dij はクラスター i とクラスター j の距離を表す。)

\[ d_{km} = \frac{1}{2}\left( d_{im} + d_{jm} - d_{ij} \right) \]

近隣結合法で系統樹を構成する手順。

  1. 距離 Dij が最小となるペア i、j を探す。Dij は、距離行列中の距離 dij を用いて次のように計算する。

    \[ D_{ij} = d_{ij} - (r_{i} + r_{j}) \] \[ r_{i} = \frac{1}{|L| - 2}\sum_{k \in L} d_{ik} \]

    ここで、L は葉の集合を表す。|L| はその集合のサイズ(葉の枚数)を表す。

  2. 最小のペア i、j を見つけたら、i と j から新しい節点 k を作る。k を集合 L に追加し、i と j を集合 L から削除する。

    i、j、k からなる系統樹を作成する。ik 間とjk 間の距離は次のように計算する。

    \[ d_{ik} = \frac{1}{2}\left ( d_{ij} + r_{i} - r_{j} \right) \] \[ d_{ik} = \frac{1}{2}\left ( d_{ij} - r_{i} + r_{j} \right) \]
  3. k と集合 L の各要素間の距離を再計算する。

    \[ d_{km} = \frac{1}{2}\left( d_{im} + d_{jm} - d_{ij} \right) \]
  4. 集合 L の要素数が 2 になるまで、上記を繰り返す。
  5. 集合 L の要素が残り i と j のみとなった時、i と j の間に枝を描き、ij 間の距離を dij とする。