Neighbor joining

Based on a distance matrix relating the ${\displaystyle n}$ taxa, calculate the ${\displaystyle n}$ x ${\displaystyle n}$ matrix ${\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)}$

(1)

where ${\displaystyle d(i,j)}$ is the distance between taxa ${\displaystyle i}$ and ${\displaystyle j}$.

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

${\displaystyle \delta (f,u)={\frac {1}{2}}d(f,g)+{\frac {1}{2(n-2)}}\left[\sum _{k=1}^{n}d(f,k)-\sum _{k=1}^{n}d(g,k)\right]\quad }$

(2)

and:

${\displaystyle \delta (g,u)=d(f,g)-\delta (f,u)\quad }$

Taxa ${\displaystyle f}$ and ${\displaystyle g}$ are the paired taxa and ${\displaystyle u}$ is the newly created node. The branches joining ${\displaystyle f}$ and ${\displaystyle u}$ and ${\displaystyle g}$ and ${\displaystyle u}$, and their lengths, ${\displaystyle \delta (f,u)}$ and ${\displaystyle \delta (g,u)}$ are part of the tree which is gradually being created; they neither affect nor are affected by later neighbor-joining steps.

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

${\displaystyle d(u,k)={\frac {1}{2}}[d(f,k)+d(g,k)-d(f,g)]}$

(3)

where ${\displaystyle u}$ is the new node, ${\displaystyle k}$ is the node which we want to calculate the distance to and ${\displaystyle f}$ and ${\displaystyle g}$ are the members of the pair just joined.

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

We calculate the ${\displaystyle Q_{1}}$ values by equation (1). For example:

${\displaystyle Q_{1}(a,b)=(n-2)d(a,b)-\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)}$

${\displaystyle =(5-2)\times 5-(5+9+9+8)-(5+10+10+9)=15-31-34=-50}$

We obtain the following values for the ${\displaystyle Q_{1}}$ matrix (the diagonal elements of the matrix are not used and are omitted here):

In the example above, ${\displaystyle Q_{1}(a,b)=-50}$. This is the smallest value of ${\displaystyle Q_{1}}$, so we join elements ${\displaystyle a}$ and ${\displaystyle b}$.

Let ${\displaystyle u}$ denote the new node. By equation (2), above, the branches joining ${\displaystyle a}$ and ${\displaystyle b}$ to ${\displaystyle u}$ then have lengths:

${\displaystyle \delta (a,u)={\frac {1}{2}}d(a,b)+{\frac {1}{2(5-2)}}\left[\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)\right]\quad ={\frac {5}{2}}+{\frac {31-34}{6}}=2}$

${\displaystyle \delta (b,u)=d(a,b)-\delta (a,u)\quad =5-2=3}$

We then proceed to update the initial distance matrix ${\displaystyle D}$ into a new distance matrix ${\displaystyle D_{1}}$ (see below), reduced in size by one row and one column because of the joining of ${\displaystyle a}$ with ${\displaystyle b}$ into their neighbor ${\displaystyle u}$. Using equation (3) above, we compute the distance from ${\displaystyle u}$ to each of the other nodes besides ${\displaystyle a}$ and ${\displaystyle b}$. In this case, we obtain:

${\displaystyle d(u,c)={\frac {1}{2}}[d(a,c)+d(b,c)-d(a,b)]={\frac {9+10-5}{2}}=7}$

${\displaystyle d(u,d)={\frac {1}{2}}[d(a,d)+d(b,d)-d(a,b)]={\frac {9+10-5}{2}}=7}$

${\displaystyle d(u,e)={\frac {1}{2}}[d(a,e)+d(b,e)-d(a,b)]={\frac {8+9-5}{2}}=6}$

The resulting distance matrix ${\displaystyle D_{1}}$ is:

Bold values in ${\displaystyle D_{1}}$ correspond to the newly calculated distances, whereas italicized values are not affected by the matrix update as they correspond to distances between elements not involved in the first joining of taxa.

The corresponding ${\displaystyle Q_{2}}$ matrix is:

We may choose either to join ${\displaystyle u}$ and ${\displaystyle c}$, or to join ${\displaystyle d}$ and ${\displaystyle e}$; both pairs have the minimal ${\displaystyle Q_{2}}$ value of ${\displaystyle -28}$, and either choice leads to the same result. For concreteness, let us join ${\displaystyle u}$ and ${\displaystyle c}$ and call the new node ${\displaystyle v}$.

The lengths of the branches joining ${\displaystyle u}$ and ${\displaystyle c}$ to ${\displaystyle v}$ can be calculated:

${\displaystyle \delta (u,v)={\frac {1}{2}}d(u,c)+{\frac {1}{2(4-2)}}\left[\sum _{k=1}^{4}d(u,k)-\sum _{k=1}^{4}d(c,k)\right]\quad ={\frac {7}{2}}+{\frac {20-22}{4}}=3}$

${\displaystyle \delta (c,v)=d(u,c)-\delta (u,v)\quad =7-3=4}$

The joining of the elements and the branch length calculation help drawing the neighbor joining tree as shown in the figure.

The updated distance matrix ${\displaystyle D_{2}}$ for the remaining 3 nodes, ${\displaystyle v}$, ${\displaystyle d}$, and ${\displaystyle e}$, is now computed:

${\displaystyle d(v,d)={\frac {1}{2}}[d(u,d)+d(c,d)-d(u,c)]={\frac {7+8-7}{2}}=4}$

${\displaystyle d(v,e)={\frac {1}{2}}[d(u,e)+d(c,e)-d(u,c)]={\frac {6+7-7}{2}}=3}$

The tree topology is fully resolved at this point. However, for clarity, we can calculate the ${\displaystyle Q_{3}}$ matrix. For example:

${\displaystyle Q_{3}(v,e)=(3-2)d(v,e)-\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(e,k)=3-7-6=-10}$

For concreteness, let us join ${\displaystyle v}$ and ${\displaystyle d}$ and call the last node ${\displaystyle w}$. The lengths of the three remaining branches can be calculated:

${\displaystyle \delta (v,w)={\frac {1}{2}}d(v,d)+{\frac {1}{2(3-2)}}\left[\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(d,k)\right]\quad ={\frac {4}{2}}+{\frac {7-7}{2}}=2}$

${\displaystyle \delta (w,d)=d(v,d)-\delta (v,w)=4-2=2}$

${\displaystyle \delta (w,e)=d(v,e)-\delta (v,w)=3-2=1}$

The neighbor joining tree is now complete, 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 ${\displaystyle d}$ to ${\displaystyle b}$ we have ${\displaystyle 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.