UPGMA Tree Reconstruction
UPGMA (Unweighted Pair Group Method with Arithmetic Mean) reconstructs a rooted phylogenetic tree from an existing distance matrix. Unlike the molecular clock simulators, it does not analyse DNA sequences directly. Instead, it works entirely from the estimated evolutionary distances between every pair of taxa.
The algorithm repeatedly joins the two closest groups of taxa until only a single tree remains. Because each new cluster is placed halfway along the evolutionary distance separating its child clusters, the resulting tree is always rooted and ultrametric.
This workflow uses the Strict Molecular Clock Simulator because UPGMA assumes equal evolutionary rates across all lineages. The same pipeline can be applied to relaxed-clock simulations, but the reconstructed tree may differ from the true tree because UPGMA always produces an ultrametric tree.
Imagine that every taxon initially forms its own cluster.
The algorithm repeatedly performs four simple operations:
- Find the two clusters separated by the smallest distance.
- Merge those clusters into a new common ancestor.
- Place the ancestor halfway between the two clusters.
- Recalculate the distances from the new cluster to every remaining cluster using the arithmetic mean.
This process continues until only a single cluster remains, which becomes the root of the reconstructed tree. Although simple, this procedure reconstructs remarkably accurate trees when its underlying assumptions are satisfied.
When two taxa become a cluster, the algorithm no longer has a direct distance from that cluster to the remaining taxa. Rather than choosing one representative sequence, UPGMA treats every member of the cluster equally.
For example, after joining taxa A and B, the distance from the new cluster to taxon C becomes:
distance(AB, C) = (distance(A, C) + distance(B, C)) / 2
Likewise,
distance(AB, CD) = ( distance(A,C) + distance(A,D) + distance(B,C) + distance(B,D) ) / 4
This arithmetic mean gives the algorithm its name.
Every original taxon begins with a height of zero. When two clusters are joined, the new cluster is placed at half the distance separating them.
For example, if two clusters are separated by a distance of 6:
new cluster height = 6 / 2 = 3
The branch leading to each child is then calculated as:
branch length = new cluster height − child cluster height
Repeating this calculation throughout the reconstruction ensures that every leaf ends up exactly the same distance from the root.
An ultrametric tree is therefore not merely a consequence of UPGMA—it is a property of the algorithm itself.
UPGMA assumes that every lineage evolves at approximately the same rate.
If two taxa differ by six substitutions, UPGMA assumes that each lineage accumulated approximately three substitutions since they diverged.
This is precisely the assumption made by a strict molecular clock.
When this assumption holds, evolutionary distance is proportional to time, allowing UPGMA to estimate ancestral relationships accurately.
UPGMA performs well when:
- Evolution follows a strict molecular clock
- Evolutionary distances have been estimated accurately
- Substitution rates remain broadly constant across lineages
Within this project, trees generated using the Strict Molecular Clock Simulator satisfy these assumptions.
The reconstructed trees closely match the original simulated trees, even though only the distance matrix is supplied to the algorithm.
UPGMA's greatest strength is also its greatest weakness. Because it always assumes equal evolutionary rates, it always reconstructs an ultrametric tree but real evolution is often more complicated.
If one lineage evolves more rapidly than another, two unrelated taxa may appear more similar (or more different) simply because they accumulated substitutions at different rates.
From the observed sequence distances alone, UPGMA cannot distinguish between:
- Lineages that diverged earlier
- Lineages that accumulated substitutions more rapidly
It therefore forces relaxed-clock data into a strict-clock explanation and the resulting topology may differ from the true evolutionary history.
Branch lengths may also become misleading.
The images below illustrate this limitation. The left-hand tree is the true simulated tree generated using the Relaxed Molecular Clock Simulator. The right-hand tree is reconstructed by UPGMA using only the distance matrix.
Although many local relationships remain correct, some taxa are grouped differently because the algorithm assumes equal evolutionary rates throughout the tree.
This is expected behaviour and illustrates why more sophisticated reconstruction algorithms, such as Neighbour Joining and maximum-likelihood methods, are used when evolutionary rates vary.
To run the tree reconstruction algorithm, first create a virtual environment. From the root of the project:
python -m venv venv
. venv/bin/activate
pip install --upgrade pip
pip install -e .These commands are correct for MacOS/Linux but may need modification for Windows.
Once the environment has been created and activated, run the tree reconstruction as follows:
python -m phylogeny --input "/path/to/distance_matrix_hky85.json" --method upgmaWhen --output is omitted, UPGMA writes the tree beside the input matrix and uses its distance_metric value. The example creates upgma_hky85.newick. Use --output /path/to/custom_tree.newick to override the destination.
The output uses Newick format with six decimal places for every branch length:
((A:1.000000,B:1.000000):2.500000,(C:2.000000,D:2.000000):1.500000);
The outermost group is the root. Because the result is ultrametric, summing branch lengths from that root to any leaf gives the same value.