Neighbor joining-Cedar Herald Index

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 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 create the phylogenetic tree.

The algorithm

Neighbor joining takes a distance matrix, which specifies the distance between each pair of taxa, as input. 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:

Neighbor joining

Based on the current distance matrix, calculate a matrix (defined below). Find the pair of distinct taxa i and j (i.e. with ) for which is smallest. Make a new node that joins the taxa i and j, and connect the new node to the central node. For example, in part (B) of the figure at right, node u is created to join f and g. Calculate the distance from each of the taxa in the pair to this new node. Calculate the distance from each of the taxa outside of this pair to the new node. Start the algorithm again, replacing the pair of joined neighbors with the new node and using the distances calculated in the previous step.

Neighbor joining

The Q-matrix

Based on a distance matrix relating the taxa, calculate the x matrix as follows:

Neighbor joining

where is the distance between taxa and .

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:

and:

Taxa and are the paired taxa and is the newly created node. The branches joining and and and , and their lengths, and are part of the tree which is gradually being created; they neither affect nor are affected by later neighbor-joining steps.

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:

where is the new node, is the node which we want to calculate the distance to and and are the members of the pair just joined.

Complexity

Neighbor joining on a set of taxa requires iterations. At each step one has to build and search a matrix. Initially the matrix is size , then the next step it is , etc. Implementing this in a straightforward way leads to an algorithm with a time complexity of ; implementations exist which use heuristics to do much better than this on average.

Example

Let us assume that we have five taxa and the following distance matrix :

First step

First joining

We calculate the values by equation (). For example:

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

In the example above, . This is the smallest value of , so we join elements and .

First branch length estimation

Let denote the new node. By equation (), above, the branches joining and to then have lengths:

First distance matrix update

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

The resulting distance matrix is:

Bold values in 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.

Second step

Second joining

The corresponding matrix is:

We may choose either to join and , or to join and ; both pairs have the minimal value of , and either choice leads to the same result. For concreteness, let us join and and call the new node .