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 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.
- 1 The algorithm
- 2 Example
- 3 Neighbor joining as minimum evolution
- 4 Advantages and disadvantages
- 5 Implementations and variants
- 6 See also
- 7 References
- 8 External links
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:
- Based on the current distance matrix calculate the matrix (defined below).
- Find the pair of distinct taxa i and j (i.e. with ) for which has its lowest value. These taxa are joined to a newly created node, which is connected to the central node. In the figure at right, f and g are joined to the new node u.
- Calculate the distance from each of the taxa in the pair to this new node.
- Calculate the distance from each of the taxa outside of this pair to the new node.
- Start the algorithm again, replacing the pair of joined neighbors with the new node and using the distances calculated in the previous step.
Based on a distance matrix relating the taxa, calculate as follows:
where is the distance between taxa and .
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:
Taxa and are the paired taxa and is the newly created node. The branches joining and and and , and their lengths, and are part of the tree which is gradually being created; they neither affect not 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 is the new node, is the node which we want to calculate the distance to and and are the members of the pair just joined.
Neighbor joining on a set of taxa requires iterations. At each step one has to build and search a matrix. Initially the matrix is size , then the next step it is , etc. Implementing this in a straightforward way leads to an algorithm with a time complexity of ; implementations exist which use heuristics to do much better than this on average.
Let us assume that we have five taxa and the following distance matrix:
We obtain the following values for the matrix (the diagonal elements of the matrix are not used and are omitted here):
In the example above, . This is the smallest value of , so we join nodes and . Let denote the new node; the branches joining and to then have lengths and , by equation (2), above.
We then proceed to update the distance matrix; using equation (3) above, we compute the distance from to each of the other nodes besides and . In this case, we obtain , , and . The resulting distance matrix is:
The corresponding Q matrix is:
We may choose either to join and , or to join and ; both pairs have the minimal value of , and either choice leads to the same result. For concreteness, let us join and and call the new node ; this gives branch lengths and as shown in the figure, and the distance matrix for the remaining 3 nodes, , , and , is:
The tree topology is fully resolved at this point, so we don't need to calculate 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 to 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.
Neighbor joining as minimum evolution
Neighbor joining may be viewed as a greedy algorithm for optimizing a tree according to 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 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, due in part to its being a polynomial-time algorithm. 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, 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.
- Saitou. Kyushu Museum. 2002. February 2, 2007
- Saitou N, Nei M. "The neighbor-joining method: a new method for reconstructing phylogenetic trees." Molecular Biology and Evolution, volume 4, issue 4, pp. 406-425, July 1987.
- Xavier Didelot (2010). "Sequence-Based Analysis of Bacterial Population Structures". In D. Ashley Robinson, Daniel Falush, Edward J. Feil. Bacterial Population Genetics in Infectious Disease. John Wiley and Sons. pp. 46–47. ISBN 978-0-470-42474-2.
- Gascuel O, Steel M (2006). "Neighbor-joining revealed". Mol Biol Evol 23 (11): 1997–2000. doi:10.1093/molbev/msl072. PMID 16877499.
- Atteson K (1997). "The performance of neighbor-joining algorithms of phylogeny reconstruction", pp. 101–110. In Jiang, T., and Lee, D., eds., Lecture Notes in Computer Science, 1276, Springer-Verlag, Berlin. COCOON '97.
- Mihaescu R, Levy D, Pachter L (2009). "Why neighbor-joining works". Algorithmica 54 (1): 1–24. doi:10.1007/s00453-007-9116-4.
- Other sources
- Studier JA, Keppler KJ (1988). "A note on the Neighbor-Joining algorithm of Saitou and Nei" (PDF). Mol Biol Evol 5 (6): 729–731. PMID 3221794.
- Martin Simonsen, Thomas Mailund, Christian N. S. Pedersen (2008). "Rapid Neighbour Joining" (PDF). Proceedings of WABI 5251: 113–122. doi:10.1007/978-3-540-87361-7_10.
- The Neighbor-Joining Method — a tutorial