This MedLibrary.org supplementary page on Neighbor-joining is provided directly from the open source Wikipedia as a service to our readers. Please see the note below on authorship of this content, as well as the Wikipedia usage guidelines. To search for other content from our encyclopedia supplement, please use the form below:
Related Sponsors
In bioinformatics, neighbor-joining is a bottom-up clustering method used for the construction of phylogenetic trees. 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) in the tree.
Contents |
The algorithm
Neighbor-joining is an iterative algorithm. Each iteration consists of the following steps:
- Based on the current distance matrix calculate the matrix Q (explained below).
- Find the pair of taxa in Q with the lowest value. Create a node on the tree that joins these two taxa (i.e. join the closest neighbors, as the algorithm name implies).
- Calculate the distance of each of the taxa in the pair to this new node.
- Calculate the distance of all taxa outside of this pair to the new node.
- Start the algorithm again, considering the pair of joined neighbors as a single taxon and using the distances calculated in the previous step.
The Q-matrix
Based on a distance matrix relating r taxa, calculate Q as follows:
d(i,j) is the distance between taxa i and j.
For example, if we have four taxa (A, B, C, D) and the following distance matrix:
| A | B | C | D | |
|---|---|---|---|---|
| A | — | — | — | — |
| B | 7 | — | — | — |
| C | 11 | 6 | — | — |
| D | 14 | 9 | 7 | — |
We obtain the following values for the Q matrix:
| A | B | C | D | |
|---|---|---|---|---|
| A | — | — | — | — |
| B | −40 | — | — | — |
| C | −34 | −34 | — | — |
| D | −34 | −34 | −40 | — |
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.
Distance of the pair members to the new node
For each neighbor in the pair just joined, use the following formula to calculate 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](http://upload.wikimedia.org/math/a/7/8/a781c3d7e537fb3856ddc1f36d74bd3b.png)
In the example above, this formula would give a distance of 6 between A and the new node and a distance of 1 between B and the new node.
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(f,u)] + \frac{1}{2} [d(g,k)-d(g,u)]](http://upload.wikimedia.org/math/e/1/9/e19bdd219d80d2351260c80a8f3df60a.png)
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.
Following the example, the distance between C and the new node is 5. Also, the distance between the new node and D is 8.
The next recursion step
From the steps above, the following matrix will result (AB acting as a new taxon):
| AB | C | D | |
|---|---|---|---|
| AB | — | — | — |
| C | 5 | — | — |
| D | 8 | 7 | — |
We can start the procedure anew taking this matrix as the original distance matrix. In our example, it suffices to do one more step of the recursion to obtain the complete tree.
Pros and cons of the NJ method
Neighbor-joining is based on the minimum-evolution criterion for phylogenetic trees, i.e. the topology that gives the least total branch length is preferred at each step of the algorithm. However, neighbor-joining may not find the true tree topology with least total branch length because it is a greedy algorithm that constructs the tree in a step-wise fashion. Even though it is sub-optimal in this sense, it has been extensively tested and usually finds a tree that is quite close to the optimal tree. Nevertheless, it has been largely superseded in phylogenetics by 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 phylogenetic analysis (e.g. minimum evolution, maximum parsimony, maximum likelihood) are computationally prohibitive. Unlike the UPGMA algorithm for phylogenetic 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.
See also
References
- 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.
- Gascuel O, Steel M (2006). "Neighbor-joining revealed". Mol Biol Evol 23 (11): 1997-2000. doi:.
- Mihaescu R, Levy D, Pachter L (2006). "Why neighbor-joining works".
- Saitou N, Nei M (1987). "The neighbor-joining method: a new method for reconstructing phylogenetic trees". Mol Biol Evol 4 (4): 406-425. PMID 3447015, http://mbe.oxfordjournals.org/cgi/reprint/4/4/406.
- 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.
External links
- The Neighbor-Joining Method — a tutorial
|
|||||||||||||||||
Wikipedia content modification information:
- This page was last modified on 6 November 2008, at 22:43.
Wikipedia Authorship and Review
Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.
Wikipedia Usage Guidelines
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Neighbor-joining".
The URL for this specific entry is:
All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.