Distance Matrices and Clustering Methods in Phylogenetics – UPGMA & Neighbor-Joining Explained

Distance-based methods form one of the major approaches used in molecular phylogenetics for reconstructing evolutionary trees. In this approach, the evolutionary distance between every pair of sequences is first calculated and arranged in the form of a distance matrix. This matrix is then used as the input for a clustering algorithm, which progressively joins the most closely related sequences together until a complete tree connecting all the species is obtained.

The two clustering methods of greatest importance in phylogenetics are the UPGMA (Unweighted Pair Group Method with Arithmetic Mean) and the Neighbor-Joining (NJ) method. Both methods use a distance matrix as their starting point, but they differ considerably in the assumptions they make and in the type of tree they produce.

Calculating Evolutionary Distances

Before any clustering can be performed, the evolutionary distance between each pair of sequences must be calculated from a multiple sequence alignment. This calculation requires the choice of an appropriate evolutionary model. Several such models exist, differing in their assumptions about the pattern of nucleotide substitution, but the Jukes–Cantor (JC) model is often used as a starting point because it is the simplest available model. Its simplicity makes it convenient for comparing results obtained from different phylogenetic methods.

The JC model assumes that all four nucleotide bases occur with equal frequency, an assumption that is often not strictly true in real biological sequences, such as ribosomal RNA genes. Consequently, more complex models that account for unequal base frequencies and different substitution rates generally provide a better fit to real data. Nevertheless, when a data set contains a strong underlying phylogenetic signal, even the simplest model such as JC can recover this signal reasonably well.

Once pairwise distances have been calculated using a chosen model, they are arranged into a distance matrix, whose elements, denoted d(i,j), represent the evolutionary distance between species i and species j. This matrix has two defining properties:

• It is symmetric, meaning that the distance from species i to species j is equal to the distance from species j to species i, i.e., d(i,j) = d(j,i).
• The diagonal elements are zero, since the distance of any sequence from itself must be zero.

In an illustrative example using primate mitochondrial sequences, the human-to-chimpanzee distance was found to be about 2.77%, the smallest pairwise distance was about 1.49% (between chimpanzee and pygmy chimpanzee), and the largest distance within the group was close to 20% (between orangutan and proboscis monkey). Distances between primates and more distantly related outgroup species such as mouse were considerably higher, in the range of 26–30%, reflecting the relatively rapid rate of evolution of mitochondrial sequences compared to nuclear genes. It is also important to note that highly variable, unreliably aligned regions of the sequence are typically removed before distance calculation; had these regions been retained, the calculated distances would have been somewhat higher.

General Principle of Clustering Algorithms

A distance matrix, once obtained, can be used as input to a clustering algorithm to build a phylogenetic tree. The general clustering procedure follows three repeated steps:

1. Join the closest two clusters to form a single larger cluster.
2. Recalculate the distances between this new cluster and all the remaining clusters.
3. Repeat the above two steps until all the species have been connected into a single, fully resolved tree.

At the start of this process, each individual species is treated as forming its own separate cluster. As the algorithm proceeds, clusters progressively merge and grow larger, until eventually all species are joined together into one complete tree. The two major clustering methods used in phylogenetics — UPGMA and Neighbor-Joining — both follow this general clustering logic, but they differ in how the distances between clusters are recalculated and in the type of tree topology they are capable of producing.

The UPGMA Method

Basic Concept

UPGMA stands for the Unweighted Pair Group Method with Arithmetic Mean. It belongs to a family of hierarchical clustering methods and is considered conceptually the simplest phylogenetic clustering method, although it is now rarely used in serious phylogenetic research owing to certain important limitations discussed below.

Procedure

• Step 1: The two closest species in the distance matrix are identified and connected first. For example, in a primate data set, the chimpanzee and pygmy chimpanzee, being the closest pair, would be joined first.
• Step 2: The distance between this newly formed cluster and all other remaining species or clusters is recalculated. In UPGMA, this distance is defined simply as the arithmetic mean of the distances between all species in the two clusters being compared. For instance, the distance from a species such as human to the chimpanzee/pygmy chimpanzee cluster would be calculated as the average of the human–chimpanzee and human–pygmy chimpanzee distances. If distances between a two-species cluster and a three-species cluster are required, the mean is taken over all six (2 × 3) pairwise distances between members of the two clusters.
• This process of joining the closest clusters and recalculating distances is repeated until all species are connected into a single rooted tree.

It is this particular definition of inter-cluster distance, as a simple arithmetic mean, that distinguishes UPGMA from the other hierarchical clustering methods.

Nature of the Tree Produced

The UPGMA method produces a rooted tree, in which the lengths of the branches are proportional to the amount of evolutionary time inferred to separate the species. This means that UPGMA implicitly assumes a strict molecular clock, that is, it assumes that all lineages are evolving at the same constant rate. The height of any internal node above the baseline of the tree represents half the distance between the two groups being joined at that node, since it is assumed that the changes separating the two groups are divided equally between the two branches leading to them. The final node at which the last two remaining clusters are joined is taken to represent the root of the tree — a feature that distinguishes UPGMA from most other phylogenetic methods, which generally do not indicate the position of the root.

Concept of Ultrametricity

A key property associated with UPGMA trees is ultrametricity. A tree, or the distance matrix underlying it, is said to be ultrametric if, for any three species chosen from the tree, the two largest of the three pairwise distances between them are exactly equal. This arises because, in such a tree, two of the three species are always more closely related to each other than either is to the third, and both of their distances to the third species are determined by the same branching point.

• If we consider true evolutionary divergence times between species, these times are expected to be exactly ultrametric.
• If sequences evolve strictly according to a molecular clock, the observed sequence distances will be only approximately ultrametric, because nucleotide substitutions occur as random events; although two descendant lineages are expected to accumulate the same number of substitutions on average, one lineage may by chance accumulate slightly more substitutions than the other.
• If different species evolve at genuinely different rates, then there is no reason to expect that the two largest distances among any three species will be equal, and the true relationships will deviate substantially from ultrametricity.

The UPGMA algorithm works by finding the best-fitting ultrametric tree such that the distances measured along its branches approximate as closely as possible the distances present in the original distance matrix.

Limitations of UPGMA

• UPGMA forces all the species onto an ultrametric tree, regardless of whether the real underlying pattern of evolution follows a strict molecular clock or not.
• If different lineages are actually evolving at markedly different rates, the assumption of a molecular clock is violated, and the resulting UPGMA tree is likely to be incorrect.
• For this reason, although UPGMA can perform well for closely related groups showing a strong, clock-like phylogenetic signal (such as within the Catarrhini, where the tree obtained corresponds well with generally accepted relationships), it tends to give an incorrect topology when more distantly related species with unequal evolutionary rates are included.
• Because of this limitation, UPGMA is generally not recommended for serious modern phylogenetic studies, even though it remains valuable as an introductory method for understanding the basic logic of distance-based clustering.

The Neighbor-Joining (NJ) Method

Basic Concept

The Neighbor-Joining method, developed by Saitou and Nei (1987), is a clustering method that, unlike UPGMA, produces an unrooted tree. Rather than assuming a molecular clock, NJ relies on a less restrictive mathematical property called additivity.

Concept of Additivity

A tree is said to be additive if the distance between any two tip species on the tree is exactly equal to the sum of the lengths of all branches connecting them. A distance matrix is described as additive if there exists some tree, with specific branch lengths, such that every pairwise distance in the matrix is exactly reproduced by summing branch lengths along the corresponding path in the tree.

• Additivity is a less restrictive condition than ultrametricity.
• Every ultrametric matrix is also additive, but an additive matrix need not be ultrametric.
• The NJ method is designed to construct an additive tree whose branch-length distances closely approximate the distances present in the original matrix.
• If the original distance matrix is exactly additive, NJ is guaranteed to recover the correct tree, just as UPGMA is guaranteed to be correct if the matrix is exactly ultrametric.
• In real data, distances are rarely exactly additive, so in practice NJ produces only an approximation to the true tree.

Concept of Neighbors

Two species are described as neighbors on an unrooted tree if they are connected to each other through a single internal node, without any other tip species lying between them.

Procedure

• The method begins with a set of disconnected tip nodes, one for each sequence, with the pairwise distances between them already known from the input distance matrix.
• The algorithm identifies a pair of nodes, i and j, that qualify as neighbors and joins them by creating a new internal node, n.
• The original nodes i and j are then removed from further consideration, since they are already incorporated into the growing tree, leaving one fewer disconnected node than before.
• Distances from the new internal node to all remaining nodes are then calculated using the assumption of additivity.
• This entire process is repeated, progressively reducing the number of disconnected nodes, until all nodes have been connected into a single, fully resolved unrooted tree.

An important methodological point is that the pair of nodes to be joined at each step cannot simply be chosen as the pair with the smallest raw distance, since the two species with the smallest observed distance are not always true neighbors on the tree. To overcome this problem, the NJ algorithm calculates a set of modified distances that correct for this effect before deciding which pair of nodes to join at each step.

Application to Primate Data and Interpretation

When applied to a primate mitochondrial sequence data set, the Neighbor-Joining method produced a tree topology that largely agreed with the taxonomic classification expected from prior knowledge. Notable features of the resulting tree included:

• The Catarrhini and Platyrrhini each formed well-defined, distinct clusters.
• The lemur and bushbaby clustered together, as did the two tarsier species, the two tree shrew species, and the two rodent species.
• Since the NJ method does not indicate the position of the root, prior biological knowledge was used to place the root on the branch leading to the rodents, making the resulting tree easier to interpret.
• Within the Platyrrhini, the marmoset and tamarin (members of the family Callitrichidae) clustered together, but the remaining four New World monkey species, classified taxonomically as Cebidae, did not form a monophyletic group. This result, supported by other phylogenetic methods as well as by independent studies using the same gene, suggests that grouping these species together as Cebidae may not accurately reflect their true evolutionary relationships.
• A more serious discrepancy was that the tree shrews appeared as the sister group to the tarsiers in the NJ tree, a result considered almost certainly incorrect, since it would imply that primates are not a monophyletic group. This conflicts with strong morphological evidence supporting the tree shrews (Order Scandentia) as a group separate from the primates, indicating that the NJ tree can sometimes be misleading in resolving certain relationships.

Advantages of the Neighbor-Joining Method

• NJ is a practical and rapid method capable of producing a fairly reliable phylogenetic tree, and for this reason it is very widely used in real phylogenetic studies.
• The algorithm has a time complexity of O(N), meaning that results can be obtained almost instantaneously even for very large numbers of sequences, in contrast to more computationally intensive methods.
• NJ is guaranteed to give the exact correct tree if the underlying distance matrix is precisely additive, and it generally performs well when the matrix is reasonably close to additive.

Limitations of the Neighbor-Joining Method

• If the input distances deviate substantially from additivity — for example, due to the use of an inappropriate distance-calculation model or as a result of poor sequence alignment — the NJ method is likely to produce an incorrect tree topology.
• The method does not indicate the position of the root, so external biological knowledge must be used to correctly root the resulting tree.

Comparison Between UPGMA and Neighbor-Joining

• UPGMA produces a rooted tree; NJ produces an unrooted tree.
• UPGMA assumes a strict molecular clock (equal rates of evolution across all lineages); NJ makes the less restrictive assumption of additivity and does not require a molecular clock.
• UPGMA is guaranteed correct only if the distance matrix is ultrametric; NJ is guaranteed correct if the matrix is additive, a condition that is less restrictive and more often approximately satisfied in real data.
• UPGMA directly indicates the position of the root; NJ does not, and the root must be inferred using prior biological knowledge, such as the inclusion of an appropriate outgroup.
• UPGMA is more likely to give incorrect results when species evolve at markedly different rates, whereas NJ generally performs more reliably under such conditions, though it is not free of errors, as seen in the misplacement of tree shrews relative to tarsiers.

Conclusion

Distance-based clustering methods provide a computationally efficient and conceptually accessible approach to phylogenetic tree reconstruction, beginning with the calculation of pairwise evolutionary distances and proceeding through iterative clustering of the most closely related sequences. The UPGMA method, though historically important and simple to understand, relies on the restrictive assumption of a molecular clock and produces reliable results only when the underlying distance matrix is close to ultrametric; it therefore performs poorly when evolutionary rates vary across lineages. The Neighbor-Joining method overcomes many of these limitations by relying on the less restrictive property of additivity, producing an unrooted tree that is generally more reliable, computationally efficient, and widely applicable, although it too can produce misleading results when the input distances deviate significantly from additivity or when sequence alignment is unreliable. The application of both methods to primate mitochondrial rRNA data illustrates how strong phylogenetic signal within closely related groups such as the Catarrhini can be recovered even with simple methods, while also highlighting the limitations of distance-based approaches when applied to more distantly related or rapidly evolving lineages.