Neighbor joining

In bioinformatics, neighbor joining is a bottom-up (agglomerative) clustering method for the creation of phylogenetic trees, created by Naruya Saitou and Masatoshi Nei in 1987. Usually based on DNA or protein sequence data, the algorithm requires knowledge of the distance between each pair of taxa (e.g., species or sequences) to create the phylogenetic tree.
The algorithm.
Neighbor joining takes a distance matrix, which specifies the distance between each pair of taxa, as input.
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:
The Q-matrix.
Based on a distance matrix relating the formula_4 taxa, calculate the formula_4 x formula_4 matrix formula_1 as follows:
where formula_8 is the distance between taxa formula_9 and formula_10.
Distance from the pair members to the new node.
For each of the taxa in the pair being joined, use the following formula to calculate the distance to the new node:
and:
Taxa formula_12 and formula_13 are the paired taxa and formula_14 is the newly created node. The branches joining formula_12 and formula_14 and formula_13 and formula_14, and their lengths, formula_19 and formula_20 are part of the tree which is gradually being created; they neither affect nor are affected by later neighbor-joining steps.
Distance of the other taxa from the new node.
For each taxon not considered in the previous step, we calculate the distance to the new node as follows:
where formula_14 is the new node, formula_22 is the node which we want to calculate the distance to and formula_12 and formula_13 are the members of the pair just joined.
Complexity.
Neighbor joining on a set of formula_4 taxa requires formula_26 iterations. At each step one has to build and search a formula_1 matrix. Initially the formula_1 matrix is size formula_29, then the next step it is formula_30, etc. Implementing this in a straightforward way leads to an algorithm with a time complexity of formula_31; implementations exist which use heuristics to do much better than this on average.
Example.
Let us assume that we have five taxa formula_32 and the following distance matrix formula_33:
First step.
First joining.
We calculate the formula_34 values by equation (). For example:
We obtain the following values for the formula_34 matrix (the diagonal elements of the matrix are not used and are
omitted here):
In the example above, formula_38. This is the smallest value of formula_34, so we join elements formula_40 and formula_41.
First branch length estimation.
Let formula_14 denote the new node. By equation (), above, the branches joining formula_40 and formula_41 to formula_14 then have lengths:
First distance matrix update.
We then proceed to update the initial distance matrix formula_33 into a new distance matrix formula_49 (see below), reduced in size by one row and one column because of the joining of formula_40 with formula_41 into their neighbor formula_14. Using equation () above, we compute the distance from formula_14 to each of the other nodes besides formula_40 and formula_41. In this case, we obtain:
The resulting distance matrix formula_49 is:
Bold values in formula_49 correspond to the newly calculated distances, whereas italicized values are not affected by the matrix update as they correspond to distances between elements not involved in the first joining of taxa.
Second step.
Second joining.
The corresponding formula_61 matrix is:
We may choose either to join formula_14 and formula_63, or to join formula_64 and formula_65; both pairs have the minimal formula_61 value of formula_67, and either choice leads to the same result. For concreteness, let us join formula_14 and formula_63 and call the new node formula_70.
Second branch length estimation.
The lengths of the branches joining formula_14 and formula_63 to formula_70 can be calculated:
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 updated distance matrix formula_76 for the remaining 3 nodes, formula_70, formula_64, and formula_65, is now computed:
Final step.
The tree topology is fully resolved at this point. However, for clarity, we can calculate the formula_82 matrix. For example:
For concreteness, let us join formula_70 and formula_64 and call the last node formula_86. The lengths of the three remaining branches can be calculated:
The neighbor joining tree is now complete, as shown in the figure.
Conclusion: additive distances.
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 formula_64 to formula_41 we have formula_92. 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.
Neighbor joining as minimum evolution.
Neighbor joining may be viewed as a greedy heuristic for the Balanced Minimum Evolution (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 does not guarantee to find the optimum for 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 as compared to least squares, maximum parsimony and maximum likelihood methods.
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.
In practice the distance matrix rarely satisfies this condition, but neighbor joining often constructs the correct tree topology anyway. 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 and
NINJA 
are fast implementations with typical run times proportional to approximately the square of the number of taxa.
BIONJ and Weighbor 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 is an implementation of the closely related balanced minimum evolution method.