UPGMA: A Short Introduction to Average-Linkage Clustering

What is UPGMA?

UPGMA stands for Unweighted Pair Group Method with Arithmetic Mean. It is a hierarchical clustering method that iteratively builds a tree by joining clusters according to their average distance.

Unweighted refers to each original taxon contributing equally to the average distance, rather than each cluster being given equal weight, regardless of its size.

Initially, each taxon is it’s own cluster.

At each step, UPGMA joins the two closest clusters and recalculates the average distances between the new cluster and all the remaining clusters. This continues until all taxa are grouped in a single cluster.

The UPGMA algorithm:

  1. Calculate the pairwise distance matrix between all taxa.
  2. Find the two closest clusters and join them together.
  3. Calculate the average distance between the new cluster and every other cluster.
  4. Update the distance matrix.
  5. Repeat until everything belongs to one cluster.

The equation for average linkage is:

D(A,B)=1|A||B|∑i∈A∑j∈Bd(i,j)D(A,B)=\frac{1}{|A||B|} \sum_{i\in A}\sum_{j\in B}d(i,j)

Where:

D(A,B): D(A,B): average distance between clusters A and B.

|A|and|B|: |A| and |B|:number of taxa in each cluster.

d(i,j): d(i,j): distance between individual taxa i and j.

A visual example

In phylogenetics, distances would come from genetic data.

Here we’ll use x,y coordinates to illustrate distance between some imaginary taxa, just to demonstrate the algorithm.

Say we have 5 taxa and we want to see where E is grouped.

Try the following R code (install ape first with install.packages("ape") if you don’t have it!):

# create df for points
points <- data.frame(
  x = c(1, 1.8, 5, 6, 7),
  y = c(1, 1, 4, 4, 5),
  row.names = LETTERS[1:5]
)

# calculate Euclidean distances
dist_matrix <- dist(points)

# run UPGMA - average-linkage hierarchical clustering
upgma <- hclust(dist_matrix, method = "average")

# convert to phylogenetic tree
library(ape)
tree <- as.phylo(upgma)

# plot side by side
par(mfrow = c(1, 2))

plot(
  points$x, points$y,
  pch = 19,
  xlim = c(0, 9),
  ylim = c(0, 7),
  xlab = "X",
  ylab = "Y",
  main = "Distances between taxa"
)

text(points$x, points$y, labels = rownames(points), pos = 3)

plot(tree, main = "UPGMA tree", direction = "rightwards")

par(mfrow = c(1, 1))

The code produces the following plots:

Here we can see that E joins the C and D cluster. This makes sense intuitively when looking at the coordinates, as E is much closer to C and D than to A and B.

Looking closer at the distance matrix, we can also see that E has the smallest distance to D, and D is in the same cluster as C.

> round(as.matrix(dist_matrix), 2)
     A    B    C    D    E
A 0.00 0.80 5.00 5.83 7.21
B 0.80 0.00 4.39 5.16 6.56
C 5.00 4.39 0.00 1.00 2.24
D 5.83 5.16 1.00 0.00 1.41
E 7.21 6.56 2.24 1.41 0.00

When the relationship is less obvious

But what if the relationship is less clear? Next, try the R code below:

# create df for points
points2 <- data.frame(
  x = c(1.6, 3.1, -2, -1.29, 0),
  y = c(0, 0, 0, -1.66, 0),
  row.names = LETTERS[1:5]
)

# calculate Euclidean distances
dist_matrix2 <- dist(points2)

# run UPGMA - average-linkage hierarchical clustering
upgma2 <- hclust(dist_matrix2, method = "average")

# convert to phylogenetic tree
tree2 <- as.phylo(upgma2)

# plot side by side
par(mfrow = c(1, 2))

plot(points2$x, points2$y,
     pch = 19, xlim = c(-3, 4), ylim = c(-3, 2),
     xlab = "X", ylab = "Y",
     main = "Distances between taxa")

text(points2$x, points2$y, labels = rownames(points2), pos = 3)

plot(tree2, main = "UPGMA tree", direction = "rightwards")

par(mfrow = c(1, 1))

# inspect pairwise distances
round(as.matrix(dist_matrix2), 2)

You’ll get plots similar to the previous example, but this time the placement of E looks less intuitive. In this example, E joins the C and D cluster.

However, looking at the individual distances, the smallest distance for E is to A.

> round(as.matrix(dist_matrix2), 2)
     A    B    C    D   E
A 0.00 1.50 3.60 3.33 1.6
B 1.50 0.00 5.10 4.69 3.1
C 3.60 5.10 0.00 1.81 2.0
D 3.33 4.69 1.81 0.00 2.1
E 1.60 3.10 2.00 2.10 0.0

So why didn’t E join with A and B?

This is because UPGMA considers the average distance between clusters, rather than only joining the closest individual taxa. We can check this by calculating the average distances for E to each cluster:

D(E,CD)=d(E,C)+d(E,D)2=2.05D(E,CD)=\frac{d(E,C)+d(E,D)}{2} = 2.05
D(E,AB)=d(E,A)+d(E,B)2=2.35D(E,AB)=\frac{d(E,A)+d(E,B)}{2} = 2.35

We can also reproduce these values in R:

dm <- as.matrix(dist_matrix2)
mean(dm["E", c("C", "D")])  
mean(dm["E", c("A", "B")])  

As E is closer on average to CD, it joins the C and D cluster, even though its closest individual taxon is A.

Choosing a method

Different methods make different assumptions and use different criteria to construct trees. If we applied another method, such as Neighbour-Joining (NJ), we might get a different tree from the same distance matrix.

One key difference is that UPGMA produces a rooted, ultrametric tree and assumes a constant rate of evolution (the molecular clock) where all tips are equally distant from the root. NJ doesn’t make this assumption.

This is another reason to think carefully about the question we’re trying to answer before choosing a clustering method.