The pseudocode below summarizes the neighbour-joining algorithm.

NeighbourJoining(D, n)
    if n = 2
        T ← tree consisting of a single edge of length D1,2
        return T
    D' ← neighbour-joining matrix constructed from the distance matrix D
    find elements i and j such that D'i,j is a minimum non-diagonal element of D'
    Δ ← (TotalDistanceD(i) - TotalDistanceD(j)) / (n - 2)
    limbLengthi ← (1/2)(Di,j + Δ)
    limbLengthj ← (1/2)(Di,j - Δ)
    add a new row/column m to D so that Dk,m = Dm,k = (1/2)(Dk,i + Dk,j - Di,j) for any k
    remove rows i and j from D
    remove columns i and j from D
    T ← NeighbourJoining(D, n - 1)
    add two new limbs (connecting node m with leaves i and j) to the tree T
    assign length limbLengthi to Limb(i)
    assign length limbLengthj to Limb(j)
    return T

Assignment

Add a method neighbour_joining to the class DistanceMatrix that takes no arguments and returns the unrooted tree (an object of the class UnrootedTree) that results from applying the neighbour-joining algorithm to the distance matrix.

Note on formatting

The n leaves must be labeled 0, 1, …, n - 1 in order of their appearance in the distance matrix. Internal nodes must be uniquely labeled, but the actual labeling can be freely chosen (integers, strings, …).

Example

In the following example we assume the text file distances.txt1 to be located in the current directory.

>>> D = DistanceMatrix.loadtxt('distances.txt2')
>>> D.neighbour_joining()
UnrootedTree((0, 4, 8.0), (1, 5, 13.5), (2, 5, 16.5), (3, 4, 12.0), (4, 5, 2.0))