UPGMA: a tree from a multiple sequence alignment

UPGMA (unweighted pair group method with arithmetic mean) turns pairwise distances into a rooted tree. It computes the distance between every two aligned sequences, then repeatedly joins the two closest clusters and replaces their rows in the distance matrix by a single row of averages, so the matrix loses one row and one column per merge. Every matrix stays on screen. Hover a distance to see where it comes from; click a tree node to jump to its merge. Keys: → step, ← back, f run all, r reset.

1 Multiple sequence alignment

2 Algorithm

  1. Compute the distance between every pair of sequences from the alignment; each sequence is a cluster of its own
  2. Find the two closest clusters A and B and join them under a new node at height d(A,B)/2
  3. Replace A and B in the matrix by their union A∪B, with d(A∪B, X) = (|A|·d(A,X) + |B|·d(B,X)) / (|A| + |B|) for every other cluster X; go back to step 2 until one cluster is left

|A| is the number of sequences in A. With these weights d(A∪B, X) is the plain average of d(a, x) over all sequences a in A∪B and x in X. Every sequence ends at height 0, so the tree is ultrametric: UPGMA assumes that all lineages evolve at the same rate (a molecular clock).

3 Alignment

4 UPGMA tree

5 Distance matrices

smallest distance: the pair joined rows of the two clusters distances of the new cluster pair joined earlier hover: entries it is computed from, sequence pairs it averages