Neighbor joining (NJ)
- Neighbor joining (NJ) search for term
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. Neighbor joining 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 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). 3) Calculate the distance of each of the taxa in the pair to this new node. 4) Calculate the distance of all taxa outside of this pair to the new node. 4) Start the algorithm again, considering the pair of joined neighbors as a single taxon and using the distances calculated in the previous step. Based on a distance matrix relating the r taxa, calculate Q as follows:where d(i,j) is the distance between taxa i and j. (wikipedia)