Neighborjoining

Neighbor-joining is a distance-based algorithm for reconstructing phylogenetic trees. It was introduced by Naruya Saitou and Masami Nei in 1987 as a fast method to infer an unrooted tree from a matrix of pairwise evolutionary distances. The approach requires only a distance matrix, not sequence data, and is widely used for initial tree construction.

The method starts with a star-like tree containing all taxa. At each step it identifies a pair of taxa i and j that minimizes a neighbor-joining criterion based on the current distance matrix, then joins them to form a new internal node. The distances from this new node to the remaining taxa are computed from the distances among i, j and the other taxa, the two joined taxa are collapsed, and the process is repeated until only two nodes remain. The final result is an unrooted tree, and rooting can be performed later using an outgroup or midpoint rooting.

In terms of complexity, neighbor-joining runs in roughly O(n^3) time with O(n^2) space, where n is the number of taxa. It is robust to some rate variation and does not assume a molecular clock, which makes it more flexible than methods enforcing equal rates. However, its accuracy depends on the quality of the distance estimates and it can be misled by such issues as unequal evolutionary rates or long-branch attraction. Extensions include variants with different distance corrections, bootstrapping for support, and integration with alternative distance metrics or optimization strategies.