Neighbor joining

This genetic distance map made in 2002 is an estimate of 18 world human groups by a neighbour-joining method based on 23 kinds of genetic information. It was made by Saitou Naruya (斎藤成也) professor at the (Japanese) National Institute for Genetics.

In bioinformatics, neighbor joining is a bottom-up clustering method for the creation of phenetic trees (phenograms), created by Naruya Saitou and Masatoshi Nei. Usually used for trees 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 form the tree.

The algorithm

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 dotted 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 the formula given in the text. 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 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:

1. Based on the current distance matrix calculate the matrix $Q$ (defined below).
2. Find the pair of taxa for which $Q(i,j)$ has its lowest value. Add a new node to the tree, joining these taxa to the rest of the tree. In the figure at right, f and g are joined to the tree by the new node u.
3. Calculate the distance from each of the taxa in the pair to this new node.
4. Calculate the distance from each of the taxa outside of this pair to the new node.
5. Start the algorithm again, replacing the pair of joined neighbors with the new node and using the distances calculated in the previous step.

The Q-matrix

Based on a distance matrix relating the $r$ taxa, calculate $Q$ as follows:

$Q(i,j)=(r-2)d(i,j)-\sum_{k=1}^r d(i,k) - \sum_{k=1}^r d(j,k)$

where $d(i,j)$ is the distance between taxa $i$ and $j$.

Distance of the pair members to the new node

For each neighbor in the pair just joined, use the following formula to calculate the distance to the new node. (Taxa $f$ and $g$ are the paired taxa and $u$ is the newly generated node.):

$d(f,u)=\frac{1}{2}d(f,g)+\frac{1}{2(r-2)} \left [ \sum_{k=1}^r d(f,k) - \sum_{k=1}^r d(g,k) \right ] \quad$

and, by reflection:

$d(g,u)=d(f,g)-d(f,u) \quad$

Distance of the other taxa to the new node

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

$d(u,k)=\frac{1}{2} [d(f,k)+d(g,k)-d(f,g)]$

where $u$ is the new node, $k$ is the node for which we want to calculate the distance and $f$ and $g$ are the members of the pair just joined.

Complexity

Since neighbor joining on a set of $r$ taxa requires $r-3$ iterations, and since at each step one has to build and search a $Q$ matrix of size $r\times r$, the algorithm can be implemented so as to obtain a time complexity of $O(r^3)$.

Example

Neighbor joining with 4 taxa. In this case just one neighbor joining step gives a tree with fully resolved topology. The branches of the resulting tree are labeled with their lengths.

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

	A	B	C	D
A	0	7	11	14
B	7	0	6	9
C	11	6	0	7
D	14	9	7	0

We obtain the following values for the Q matrix:

	A	B	C	D
A	0	−40	−34	−34
B	−40	0	−34	−34
C	−34	−34	0	−40
D	−34	−34	−40	0

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 $u$ denotes the new node, then the branch lengths of edges $\{A, u\}$ and $\{B, u\}$ are respectively 6 and 1, by the above formula.

We then proceed to updating the distance matrix, by computing $d(u,k)$ according to the above formula for every node $k$. In this case, we obtain $d(u,C)=5$ and $d(u,D)=8$. The resulting distance matrix is:

	u	C	D
u	0	5	8
C	5	0	7
D	8	7	0

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 $5 + 3 + 1 = 9$. 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.

Advantages and disadvantages

Neighbor joining is based on a minimum-evolution criterion known as 'balanced minimum evolution' (BME) . In BME the tree length (sum of branch lengths) is estimated as a particular weighted mean of the distances in the distance matrix, with the weights depending on the topology, and this tree length estimate is to be minimized. Neighbor joining is a greedy algorithm; at each step it joins that pair of taxa which will give the greatest decrease in the estimated tree length. Neighbor joining is not guaranteed to find the topology which is optimal by the BME criterion. However, Atteson proved that if each entry in the distance matrix differs from the true distance by less than half of the shortest branch length in the tree, then neighbor joining will construct the correct tree. In practice the distance matrix rarely satisfies this condition, but neighbor joining often constructs the correct tree topology anyway . Nevertheless, it has been largely superseded by phylogenetic methods that do not rely on distance measures and offer superior accuracy under most conditions.

The main virtue of neighbor joining relative to these other methods is its computational efficiency. That is, neighbor joining is a polynomial-time algorithm. It can be used on very large data sets for which other means of analysis (e.g. minimum evolution, maximum parsimony, maximum likelihood) are computationally prohibitive. Unlike the UPGMA algorithm for tree reconstruction, neighbor joining does not assume that all lineages evolve at the same rate (molecular clock hypothesis) and produces an unrooted tree. Rooted trees can be created by using an outgroup and the root can then effectively be placed on the point in the tree where the edge from the outgroup connects.

Furthermore, neighbor joining is statistically consistent under many models of evolution. Hence, given data of sufficient length, neighbor joining will reconstruct the true tree with high probability.

Implementations and variants

There are many programs available implementing neighbor joining. RapidNJ , QuickJoin and NINJA are fast implementations which run in $O(r^3)$ time in the worst case, but do better on average. 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 know than the longer distances. FastME is an implementation of the closely related balanced minimum evolution method.

See also

• UPGMA
• Human genetic clustering

References

Other sources

• Studier JA, Keppler KJ (1988). "A note on the Neighbor-Joining algorithm of Saitou and Nei". Mol Biol Evol 5 (6): 729–731. PMID 3221794. http://mbe.oxfordjournals.org/cgi/reprint/5/6/729.pdf. 
• Martin Simonsen, Thomas Mailund, Christian N. S. Pedersen (2008). "Rapid Neighbour Joining". Proceedings of WABI 5251: 113–122. doi:10.1007/978-3-540-87361-7_10. http://birc.au.dk/fileadmin/uploaded/rapidNJ.pdf. 

External links

• The Neighbor-Joining Method — a tutorial