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.

[1] 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.

[2] 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: Based on a distance matrix relating the

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

Implementing this in a straightforward way leads to an algorithm with a time complexity of

then have lengths: We then proceed to update the initial distance matrix

(see below), reduced in size by one row and one column because of the joining of

In this case, we obtain: The resulting distance matrix

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.

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

, is now computed: The tree topology is fully resolved at this point.

The lengths of the three remaining branches can be calculated: The neighbor joining tree is now complete, 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.

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 may be viewed as a greedy heuristic for the balanced minimum evolution[5] (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.

NJ 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.

[5] The main virtue of NJ is that it is fast[6]: 466  as compared to least squares, maximum parsimony and maximum likelihood methods.

[6] 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.

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.

[7] In practice the distance matrix rarely satisfies this condition, but neighbor joining often constructs the correct tree topology anyway.

[8] 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.

[citation needed] Neighbor joining has the undesirable feature that it often assigns negative lengths to some of the branches.

Among implementations of canonical NJ (i.e. using the classical NJ optimisation criteria, therefore giving the same results), RapidNJ (started 2003, major update in 2011, still updated in 2023)[9] and NINJA (started 2009, last update 2013)[10] are considered state-of-the-art.

They have typical run times proportional to approximately the square of the number of taxa.

Starting with a star tree (A), the Q matrix is calculated and used to choose a pair of nodes for joining, in this case f and g. These are joined to a newly created node, u, as shown in (B). The part of the tree shown as solid lines is now fixed and will not be changed in subsequent joining steps. The distances from node u to the nodes a-e are computed from equation ( 3 ). This process is then repeated, using a matrix of just the distances between the nodes, a,b,c,d,e, and u, and a Q matrix derived from it. In this case u and e are joined to the newly created v, as shown in (C). Two more iterations lead first to (D), and then to (E), at which point the algorithm is done, as the tree is fully resolved.
Neighbor joining with 5 taxa. In this case 2 neighbor joining steps give a tree with fully resolved topology. The branches of the resulting tree are labeled with their lengths.