Neighbor-joining

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.

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 a distance matrix relating the ${\displaystyle n}$ taxa, calculate ${\displaystyle Q}$ as follows:

${\displaystyle Q(i,j)=(n-2)d(i,j)-\sum _{k=1}^{n}d(i,k)-\sum _{k=1}^{n}d(j,k)}$

...
Wikipedia