The Algorithm
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 taxa for which 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.
- 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.
Read more about this topic: Neighbor Joining