UPGMAと隣接結合木の主な違いは、UPGMAが平均連結法に基づく凝集型階層的クラスタリング法であるのに対し、隣接結合木は最小進化規準に基づく反復型クラスタリング法である点です。
また、UPGMA法は根付きの系統樹を作成するのに対し、neighbor-joining tree法は根のない系統樹を作成する。
UPGMA法は進化の速度が等しいと仮定しているので、枝の先端が等しくなる。
一方、近傍結合木法は進化の速度が不均等なので、枝の長さは変化量に比例する。
距離行列から系統樹を作るアルゴリズムには、UPGMA（unweighted pair group method with arithmetic mean）とNJ（neighbor-joining）樹があります。
一般にUPGMA法は単純で高速だが信頼性が低く、NJ法は比較的高速でUPGMA法より良い結果を得ることができる。
主な対象分野
- UPGMAとは
– 定義、方法、意義 - Neighbor Joining Treeとは？
– 定義、方法、意義 - UPGMAと隣接結合木との類似点
– 共通点の概要 - UPGMAと隣接結合木の違いとは？
– 主な違いの比較
この記事の重要な単語
UPGMAとは
UPGMA (unweighted pair group method with arithmetic mean) は、Sokal と Michener が提唱した単純な凝集型階層的クラスタリング法です。
これは、根付き超分子系統樹を構築するための最も単純かつ迅速な方法です。
しかし、この方法の大きな欠点は、すべての系統で同じ進化速度であると仮定していることである。
これは、これらの系統における突然変異の速度が時間的に一定であることを意味する。
これは「分子時計仮説」とも呼ばれる。
さらに、樹木のすべての枝が同じような距離で生成される。
しかし、すべての系統の変異率を同じにすることは難しいので、現実にはUPGMA法は信頼性の低い樹形図を生成することが多くなっています。
図1：UPGMA法
さらに、UPGMA法はペアワイズ距離の行列から始める。
最初に、それぞれの種がそれ自体で1つのクラスタであると仮定する。
そして、距離行列の中で最も小さい距離値を持つ最も近い2つのクラスターを結合する。
さらに、平均をとることによって、結合したペアの距離を再計算する。
そして、このアルゴリズムは、全ての種が一つのクラスタに接続されるまで、このプロセスを繰り返す。
Neighbor Joining Tree（ネイバー・ジョイニング・ツリー）とは
Neighbor-joining (NJ) tree 法は、系統樹の構築に用いられる最新の凝集型クラスタリング法です。
1987年に斉藤成也と根井正敏によって開発された。
しかし、根を張らない系統樹を構築する。
また、超対称距離を必要とせず、スター分解法を用いている。
さらに、近傍結合木アルゴリズムでは、系統の進化速度のばらつきを調整する。
そのため、未解決のスター型ツリーからスタートする。
図2: 近隣結合木の構成
さらに、近傍結合木法では、現在の距離に基づいて行列Qを計算する。
そして、距離が最も小さい系統のペアを選択し、新たに作成したノードに結合させる。
ただし、このノードは中心ノードと接続状態にある。
その後、アルゴリズムは各系統から新ノードまでの距離を計算する。
次に、各系統から新しいノードまでの距離を外側から計算する。
最後に、計算された距離に基づいて、結合した近傍ノードを新しいノードに置き換える。
UPGMAと近傍結合木の類似性
- UPGMAと隣接結合木は、距離行列を入力として系統樹を構築する2つのアルゴリズムです。一般に距離行列は2次元行列であり、点の集合のペアワイズ距離を格納する配列です。
- 距離行列の構築には、関連するタンパク質やDNA配列のアラインメントスコアを指標とすることができる。
- どちらも凝集型（ボトムアップ）クラスタリング手法です。
- どちらも凝集型（ボトムアップ型）のクラスタリング手法であり、計算コストが低く、高速な手法です。
- そのため、大規模なデータセットに適用できる。
- また、両手法とも、他のタイプの入力による手法と比較すると、より良い結果を得ることができる。
- 両手法は単一の木を生成するように設計されているが、時には複数のトポロジーを生成し、データ入力の順番に応じた「カオス」な振る舞いをすることがあります。
- ブートストラップ値は、ノード/クレードの形成確率を確認するための簡単な統計テストです。
UPGMAと近傍結合木の違い
定義
UPGMAとは距離行列から根付きの系統樹を作る素直な手法であり、neighbor-joining treeとはスターツリーを介して根のない系統樹を作る新しい手法のことである。
開発元
UPGMA法は1958年にSokalとMichenerによって開発され、近傍結合木は1987年に斉藤成也と根井正敏によって開発された。
意義
また、UPGMAは平均連結法に基づく凝集型階層的クラスタリング法であり、neighbor-joining treeは最小進化規準に基づく反復型クラスタリング法です。
系統樹の種類
UPGMA法が根付きの系統樹を作るのに対して、neighbor-joining tree法は根のない系統樹を作る。
距離の種類
また、UPGMAアルゴリズムでは距離が超メトリックであることが要求されるが、neighbor-joining treeアルゴリズムでは距離が習慣的であることが要求される。
系統樹の枝の性質
UPGMA法は進化の速度が等しいと仮定しているので、枝の先端は等しくなる（根から先端まで同じ枝の長さ）。
近傍結合木法では進化の速度が等しくないため、枝の長さは変化量に比例する。
速度
UPGMAはシンプルで高速な手法であり、隣接結合木は比較的高速な手法です。
信頼性
さらに、UPGMAは信頼性の低い方法であり、近傍結合木はより良い結果をもたらす。
結論
UPGMAは、進化距離データに基づいて系統樹を構築する2つのアルゴリズムのうちの1つです。
また、枝の長さが近い根付きの系統樹を構築することができる。
また、距離行列から系統樹を構築するアルゴリズムとしては、シンプルで高速、かつ最も信頼性の高いものです。
一方、近傍結合木は距離行列から系統樹を構築するために用いられる第二の方法です。
しかし、これは進化の過程で変化した量を枝の長さに反映した根のない系統樹を作成する。
また、このアルゴリズムは比較的速度が劣るものの、最も信頼性の高い系統樹を構築する。
したがって、UPGMAと近傍結合木の主な違いは、系統樹の特徴とアルゴリズムの特徴です。
