Neighbor joining

Neighbor joining is a bioinformatics algorithm used in the creation of phylogenetic trees, which represent the evolutionary relationships among various biological species or other entities based on genetic or phenotypic similarities and differences. The neighbor-joining method is a distance-matrix method, requiring as input a matrix of distances reflecting the dissimilarity between pairs of taxa (e.g., species or sequences).

Overview

The neighbor-joining method was introduced by Naruya Saitou and Masatoshi Nei in 1987. It is a bottom-up clustering method for the creation of phylogenetic trees, usually based on molecular sequence data. The algorithm starts with a star-like tree and iteratively joins pairs of nodes that minimally increase the total branch length, aiming to find the tree with the shortest possible total branch length. This process continues until the tree is fully resolved and all internal nodes have been joined.

Algorithm

The neighbor-joining algorithm involves several key steps:

1. Calculate the Q-matrix from the distance matrix, where the Q-matrix is used to determine the pair of taxa that should be joined at each step.
2. Identify the pair of taxa (neighbors) with the smallest value in the Q-matrix. These taxa are considered to have the shortest evolutionary distance and are joined to form a new node.
3. Calculate the distance from each of the taxa in the pair to this new node.
4. Update the distance matrix to reflect the distances between this new node and all other taxa.
5. Repeat the process until all taxa have been joined into a single phylogenetic tree.

Applications

Neighbor joining is widely used in phylogenetics and molecular evolution for reconstructing the evolutionary histories of species based on genetic data. It is particularly favored for its simplicity and speed, making it suitable for analyzing large datasets. Despite its heuristic nature, neighbor joining often produces trees that are close to the true evolutionary tree, especially when the input distance matrix is accurate.

Advantages and Limitations

Advantages:

• Fast and efficient, capable of handling large datasets.
• Does not assume a constant rate of evolution (i.e., it is non-ultrametric), making it more flexible in dealing with real-world data.

Limitations:

• The accuracy of the resulting tree depends heavily on the accuracy of the input distance matrix.
• It is a heuristic method, so it does not guarantee to find the most accurate tree.
• May be less accurate than other methods, such as maximum likelihood estimation, for certain types of data.

Comparison with Other Methods

Neighbor joining is often compared to other phylogenetic tree construction methods such as UPGMA (Unweighted Pair Group Method with Arithmetic Mean) and maximum likelihood estimation. Unlike UPGMA, neighbor joining does not assume a constant rate of evolution across lineages, making it more flexible. However, maximum likelihood methods, while computationally more intensive, can often provide more accurate trees by explicitly modeling the evolutionary process.

See Also

• Phylogenetics
• Molecular evolution
• Distance matrix
• Cladistics

References

• Saitou, N.; Nei, M. (1987). "The neighbor-joining method: a new method for reconstructing phylogenetic trees." Molecular Biology and Evolution 4(4): 406–425.