# 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.

## The algorithm Starting with a star tree (A), the Q matrix is calculated and used to choose a pair of nodes for joining, in this case f and g. These are joined to a newly created node, u, as shown in (B). The part of the tree shown as solid lines is now fixed and will not be changed in subsequent joining steps. The distances from node u to the nodes a-e are computed from equation (Template:EquationNote). This process is then repeated, using a matrix of just the distances between the nodes, a,b,c,d,e, and u, and a Q matrix derived from it. In this case u and e are joined to the newly created v, as shown in (C). Two more iterations lead first to (D), and then to (E), at which point the algorithm is done, as the tree is fully resolved.

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:

1. Based on the current distance matrix calculate the matrix $Q$ (defined below).
2. Find the pair of distinct taxa i and j (i.e. with $i\neq j$ ) for which $Q(i,j)$ has its lowest value. These taxa are joined to a newly created node, which is connected to the central node. In the figure at right, f and g are joined to the new node u.
3. Calculate the distance from each of the taxa in the pair to this new node.
4. Calculate the distance from each of the taxa outside of this pair to the new node.
5. Start the algorithm again, replacing the pair of joined neighbors with the new node and using the distances calculated in the previous step.

### Distance from the pair members to the new node

For each of the taxa in the pair being joined, use the following formula to calculate the distance to the new node:

Template:NumBlk and:

$\delta (g,u)=d(f,g)-\delta (f,u)\quad$ ### Distance of the other taxa from the new node

For each taxon not considered in the previous step, we calculate the distance to the new node as follows:

### Complexity

Neighbor joining on a set of $n$ taxa requires $n-3$ iterations. At each step one has to build and search a $Q$ matrix. Initially the $Q$ matrix is size $n\times n$ , then the next step it is $(n-1)\times (n-1)$ , etc. Implementing this in a straightforward way leads to an algorithm with a time complexity of $O(n^{3})$ ; implementations exist which use heuristics to do much better than this on average.

## Example Neighbor joining with 5 taxa. In this case 2 neighbor joining steps give a tree with fully resolved topology. The branches of the resulting tree are labeled with their lengths.

Let us assume that we have five taxa $(a,b,c,d,e)$ and the following distance matrix:

a b c d e
a 0 5 9 9 8
b 5 0 10 10 9
c 9 10 0 8 7
d 9 10 8 0 3
e 8 9 7 3 0

We obtain the following values for the $Q$ matrix (the diagonal elements of the matrix are not used and are omitted here):

a b c d e
a −50 −38 −34 −34
b −50 −38 −34 −34
c −38 −38 −40 −40
d −34 −34 −40 −48
e −34 −34 −40 −48
u c d e
u 0 7 7 6
c 7 0 8 7
d 7 8 0 3
e 6 7 3 0

The corresponding Q matrix is:

u c d e
u −28 −24 −24
c −28 −24 −24
d −24 −24 −28
e −24 −24 −28
v d e
v 0 4 3
d 4 0 3
e 3 3 0

The tree topology is fully resolved at this point, so we don't need to calculate $Q$ or do any more joining of neighbors. However, we can use these distances to get the remaining 3 branch-lengths, as shown in the figure.

This example represents an idealized case: note that if we move from any taxon to any other along the branches of the tree, and sum the lengths of the branches traversed, the result is equal to the distance between those taxa in the input distance matrix. For example, going from $d$ to $b$ we have $2+2+3+3=10$ . A distance matrix whose distances agree in this way with some tree is said to be 'additive', a property which is rare in practice. Nonetheless it is important to note that, given an additive distance matrix as input, neighbor joining is guaranteed to find the tree whose distances between taxa agree with it.

## Neighbor joining as minimum evolution

Neighbor joining may be viewed as a greedy algorithm for optimizing a tree according to the 'balanced minimum evolution' (BME) criterion. For each topology, BME defines the tree length (sum of branch lengths) to be a particular weighted sum of the distances in the distance matrix, with the weights depending on the topology. The BME optimal topology is the one which minimizes this tree length. Neighbor joining at each step greedily joins that pair of taxa which will give the greatest decrease in the estimated tree length. This procedure is not guaranteed to find the topology which is optimal by the BME criterion, although it often does and is usually quite close.