Code along video
Learning objectives
This lesson walks through the UPGMA algorithm before we implement it. If you have already read about UPGMA in the main text of this chapter and feel comfortable applying it by hand, then you may skip ahead to the next code along.
Code along summary
UPGMA is a clustering heuristic
UPGMA takes a distance matrix as input, in which each value is a distance between two species (or taxa), and it produces a tree. Consider the following small matrix on four species, which we call i, j, k, and l. For example, the distance from i to k is 4, and the distance from i to j is 3.
i j k l i 0 3 4 3 j 3 0 4 5 k 4 4 0 2 l 3 5 2 0
Even though this matrix is small, there is no tree whose edge weights reproduce every distance in the matrix exactly. UPGMA is a heuristic: it does not solve a precisely stated problem, but it produces a reasonable tree. In the field of machine learning, the same idea is known as hierarchical clustering. Here are its steps.
UPGMA(D): 1. Form a cluster for each present-day species, each containing a single leaf. 2. Find the two closest clusters C1 and C2 according to the minimum value in the current matrix. 3. Merge C1 and C2 into a single cluster C. 4. Form a new node for C and connect to C1 and C2 by an edge. Set age of C as D(C1, C2)/2. 5. Update the distance matrix by computing the average distance between each pair of clusters. 6. Iterate steps 2-5 until a single cluster contains all species.
Running UPGMA on a small example
We begin by assigning each of i, j, k, and l to its own leaf with age 0. The minimum value in the matrix is 2, between k and l, so we join them into a parent node with age 2/2 = 1. The weight of each edge is the difference between the ages of the nodes it connects, so the edges from this parent to k and l each have weight 1. Note that the distance between k and l in the tree (1 + 1 = 2) matches the matrix.
Next, we replace the rows and columns of k and l with a single row and column for the cluster {k, l}, whose distance to every other cluster is the average of the distances to k and l. The distance from i to {k, l} is (4 + 3)/2 = 3.5, and the distance from j to {k, l} is (4 + 5)/2 = 4.5. Our matrix has shrunk from four rows to three.
i j {k,l}
i 0 3 3.5
j 3 0 4.5
{k,l} 3.5 4.5 0
We then repeat. The minimum value is now 3, between i and j, so we join them under a node with age 1.5, making each of its edges 1.5. The distance from {i, j} to {k, l} is the average of 3.5 and 4.5, which is 4. In the final step, we join {i, j} and {k, l} under a root with age 2, which gives edge weights of 2 – 1.5 = 0.5 and 2 – 1 = 1.
Some distances in the resulting tree match the matrix: k to l is 2, i to j is 3, and i to k is 1.5 + 0.5 + 1 + 1 = 4. But the distance from i to l in the matrix is 3, whereas in the tree it is 4. UPGMA will sometimes overestimate and sometimes underestimate a distance from the matrix, but it gives a reasonable tree for any matrix.
![The final tree formed by UPGMA with the path from i to l highlighted; this path has length 4, whereas the matrix value D[i, l] is 3](https://programmingforlovers.com/images/trees/upgma_toy_tree_4.png)
Exercise: apply UPGMA to a matrix
Exercise: Apply UPGMA by hand to the following matrix. As a hint, the first minimum value is 8.
i j k l i 0 20 9 11 j 20 0 17 11 k 9 17 0 8 l 11 11 8 0
STOP: Work through this exercise before reading the solution below. When you are finished, check your final step carefully: is the distance fromjto the cluster containingi,k, andlreally the average of the two remaining values?
Solution: averages must be weighted
We first join k and l under a node of age 4. The distance from i to {k, l} is (9 + 11)/2 = 10, and the distance from j to {k, l} is (17 + 11)/2 = 14. The minimum value in the updated matrix is 10, so we join i and {k, l} under a node of age 5; the edge to i has weight 5, and the edge to the node of age 4 has weight 1.
The only remaining distance is from j to {i, k, l}. If we simply average the two values in our current matrix, we obtain (20 + 14)/2 = 17. But this is a mistake! Going back to the original matrix, the average distance from j to i, k, and l is (20 + 17 + 11)/3 = 48/3 = 16.
The issue is that 14 was already an average over a cluster of two species, but we gave it the same weight as the distance 20 to the single species i. This is like the election simulator from earlier in the course, in which states with larger populations get more votes. The value 14 represents a cluster of size 2, so it should get two votes, and 20 should get one vote. Weighting each distance by the size of its cluster, we obtain (1 × 20 + 2 × 14)/(1 + 2) = 48/3 = 16, which matches the original matrix without our needing to look back at it.
In general, if we merge clusters C1 and C2, which have sizes s1 and s2, then the distance from the new cluster to any other cluster k is given by the following weighted average.
D(new, k) = (s1 * D(C1, k) + s2 * D(C2, k)) / (s1 + s2)
With the weighted average, the root has age 16/2 = 8, the edge to j has weight 8, and the edge to the node of age 5 has weight 8 – 5 = 3. This small example shows why it is so important to understand an algorithm on small test cases before implementing it, since an innocent-looking choice like an unweighted average can quietly introduce bias into our results.
Looking ahead
Now that we understand how UPGMA works, we are ready to plan an implementation of it. In the next code along, we will write the highest-level upgma() function and see how a few carefully chosen data structures make the algorithm manageable.
