UPGMA

UPGMA (Unweighted Pair Group Method with Arithmetic mean) は、距離行列から系統樹を作成する方法。UPGMA 法は系統樹を作成するときに進化速度が一定であると仮定する必要がある。このため、枝の長さは分子時計と見なすことができる。

UPGMA 法による系統樹の構成では、クラスター間の距離を次のようにして計算する。ここで、dij をクラスター Ci とクラスター Cj の距離とする。

\[ d_{ij} = \frac{1}{|C_{i}||C_{j}|} \sum_{p\in C_{i}, q\in C_{j}} d_{pq} \]

また、クラスター Ci とクラスター Cj の親がクラスタ Ck であるとき、Ck と他のクラスター Cl の距離は、次のように計算できる。

\[ \begin{eqnarray} d_{kl} &=& \frac{1}{|C_{k}||C_{l}|}\sum_{p\in C_{k}, q\in C_{l}}d_{pq}\\ &=& \frac{1}{(C_{i} + C_{j})|C_{l}|}\sum_{p\in C_{k}, q\in C_{l}}d_{pq}\\ &=& \frac{1}{(C_{i} + C_{j})|C_{l}|}\sum_{p\in C_{i},C_{j}, q\in C_{l}}d_{pq}\\ &=& \frac{1}{|C_{i} + C_{j}|}\frac{\sum_{p\in C_{i},C_{j}, q\in C_{l}}d_{pq}}{|C_{l}|}\\ &=& \frac{1}{|C_{i} + C_{j}|} \left( \frac{\sum_{p\in C_{i}, q\in C_{l}}d_{pq}}{|C_{i}||C_{l}|}|C_{i}| + \frac{\sum_{p\in C_{j}, q\in C_{l}}d_{pq}}{|C_{j}||C_{l}|}|C_{j}| \right)\\ &=& \frac{d_{il}|C_{i}| + d_{jl}|C_{j}|}{|C_{i}||C_{j}|} \end{eqnarray} \]

上の証明では「|Ci|+|Cj|=|Ck|」を利用した。