The algorithm

Neighbor joining takes as input a distance matrix specifying the distance between each pair of taxa. The algorithm starts with a completely unresolved tree, whose topology corresponds to that of a star network, and iterates over the following steps until the tree is completely resolved and all branch lengths are known:

For each of the taxa in the pair being joined, use the following formula to calculate the distance to the new node:

and:

For each taxon not considered in the previous step, we calculate the distance to the new node as follows:

Example

First joining

First branch length estimation

First distance matrix update

Second joining

Second branch length estimation

The joining of the elements and the branch length calculation help drawing the neighbor joining tree as shown in the figure.

Second distance matrix update

The neighbor joining tree is now complete, as shown in the figure.

Neighbor joining as minimum evolution

Neighbor joining may be viewed as a greedy algorithm for optimizing a tree according to the 'balanced minimum evolution'^[3] (BME) criterion. For each topology, BME defines the tree length (sum of branch lengths) to be a particular weighted sum of the distances in the distance matrix, with the weights depending on the topology. The BME optimal topology is the one which minimizes this tree length. Neighbor joining at each step greedily joins that pair of taxa which will give the greatest decrease in the estimated tree length. This procedure is not guaranteed to find the topology which is optimal by the BME criterion, although it often does and is usually quite close.

Advantages and disadvantages

The main virtue of NJ is that it is fast^[4] ^[] as compared to least squares, maximum parsimony and maximum likelihood methods.^[4] This makes it practical for analyzing large data sets (hundreds or thousands of taxa) and for bootstrapping, for which purposes other means of analysis (e.g. maximum parsimony, maximum likelihood) may be computationally prohibitive.

Neighbor joining has the property that if the input distance matrix is correct, then the output tree will be correct. Furthermore, the correctness of the output tree topology is guaranteed as long as the distance matrix is 'nearly additive', specifically if each entry in the distance matrix differs from the true distance by less than half of the shortest branch length in the tree.^[5] In practice the distance matrix rarely satisfies this condition, but neighbor joining often constructs the correct tree topology anyway.^[6] The correctness of neighbor joining for nearly additive distance matrices implies that it is statistically consistent under many models of evolution; given data of sufficient length, neighbor joining will reconstruct the true tree with high probability. Compared with UPGMA and WPGMA, neighbor joining has the advantage that it does not assume all lineages evolve at the same rate (molecular clock hypothesis).

Nevertheless, neighbor joining has been largely superseded by phylogenetic methods that do not rely on distance measures and offer superior accuracy under most conditions. Neighbor joining has the undesirable feature that it often assigns negative lengths to some of the branches.

Implementations and variants

There are many programs available implementing neighbor joining. RapidNJ ^[14] and NINJA ^[15] are fast implementations with typical run times proportional to approximately the square of the number of taxa. BIONJ ^[16] and Weighbor ^[17] are variants of neighbor joining which improve on its accuracy by making use of the fact that the shorter distances in the distance matrix are generally better known than the longer distances. FastME ^[18] is an implementation of the closely related balanced minimum evolution method.

The algorithm

Example

Neighbor joining as minimum evolution

Advantages and disadvantages

Implementations and variants

See also