Neighbor Joining - Example

Example

Let us assume that we have four taxa (A, B, C, D) and the following distance matrix:

We obtain the following values for the Q matrix:

In the example above, two pairs of taxa have the lowest value, namely −40. We can select either of them for the second step of the algorithm. We follow the example assuming that we joined taxa A and B together. If denotes the new node, then the branch lengths of edges and are respectively 6 and 1, by the above formula.

We then proceed to updating the distance matrix, by computing according to the above formula for every node . In this case, we obtain and . The resulting distance matrix is:

The tree topology is fully resolved at this point, so we don't need to calculate Q or do any more joining of neighbors. However, we can use these distances to get the remaining 3 branch-lengths, as shown in the figure.

This example represents an idealized case: note that if we move from any taxon to any other along the branches of the tree, and sum the lengths of the branches traversed, the result is equal to the distance between those taxa in the input distance matrix. For example, going from D to B we have . A distance matrix whose distances agree in this way with some tree is said to be 'additive', a property which is rare in practice. Nonetheless it is important to note that, given an additive distance matrix as input, neighbor joining is guaranteed to find the tree whose distances between taxa agree with it.