Neighbour joining
Neighbour joining is a method that infers relationships between witnesses (or organisms if using biological sequence data) by sequentially grouping those that show fewest differences into an unrooted tree. The illustration below shows this process in an example. A distance matrix is used as input, from this matrix another matrix, called the Q matrix, is obtained which is used to find the pair of witnesses that have the lowest distance from one another.
Neighbour joining is implemented in software packages like PHYLIP or PAUP*. The method was developed by Saitou and Nei in 1987 at Texas University. It is based on earlier work, e.g. by Fitch (1981). An important early paper using least squares to approximate the optimal tree was published by Fitch and Margoliash (1967).
Illustration
Fig. 1: A fictitious example how neighbour joining works (by Wikipedia user Tomfy).
Reference
– Fitch, Walter M., and Emanuel Margoliash. 1967. “Construction of phylogenetic trees.” Science 155 (3760): 279–284. doi:10.1126/science.155.3760.279. PMID 5334057.
– Fitch, Walter M. 1981. “A non sequential method for constructing trees and hierarchical classifications.” Journal of Molecular Evolution 18: 30–37.
– Saitou, Naruya, and Masatoshi Nei. 1987. “The neighbor-joining method: A new method for reconstructing phylogenetic trees.” Molecular Biology and Evolution 4 (4): 406–425.