UPGMA computation

Question

The unweighted pair group method with arithmetic mean (UPGMA) is a hierarchical clustering method, for example used in phylogeny. In a phylogenetic tree it would result in a global molecular clock for taxa under consideration.

Two clusters $A$ and $B$ with the minimum distance are selected and merged to form a new cluster $C$, where the distance between $C$ = $A \cup B$. Assuming another $D$, we can compute: $$ d(C, D) = \frac{1}{|C| \cdot |D|} \sum_{x \in A \cup B,\, y \in D} d(x, y). $$

I think $d(x,y)$ is the distance between objects $x$ and $y$ in the input matrix.

Given the information, is there a way to prove/disprove the following statement?

$$ d(C, D) = \frac{1}{|A| + |B|} \Big( |A| d(A, D) + |B| d(B, D) \Big). $$

Answer 1

The key words in UPGMA are 'pairwise' and 'mean'.

In phylogeny the format is a bit unusual because $C$ here is the MRCA (most recent common ancestor) for $A$ and $B$. In other words this represents a three taxa tree. I agree in UPGMA this works, because of its use of the mean (which is also its criticism - below).

Under UPGMA - in your equation $d(C) = \frac{d(A,B)}{N}$ ...where $N=2$, i.e. mean.

Thus under UPGMA

$d(C,D) = d(A,D) - \frac{d(A,B)}{2}$

There is no need to include $d(B,D)$ because $d(B,D) = d(A,D)$, its the mean that was resolved in establishing $C$. If you want to assign $E = D U A$ that easy too.

Your equation doesn't work because |A| and |B| are both 0 under UPGMA, i.e. is pairwise so d(A,A) is always zero. Thus under your equation $d(C,D) = 0$ which simply means $D$, $A$, $B$ are identical and results in a matrix of 0.

---

UPGMA isn't really used in general in biological systems, because the use of the mean rarely makes it a good assumption. I 100% agree has been used in genomics in the modern era, absolutely true, its use is not encouraged because in results in artifactual clusters due its inability to accommodate unequal variation in the underlying genetic process. It could be used in for example in agricultural systems because these conform to uniform distributions, e.g. the distances between apple trees in an orchard. In the natural environment species clump and don't show uniform distributions. UPGMA was used in phylogenetic but the assumption of a global clock very rarely held, so it was discontinued.