The following recursive algorithm, called AdditivePhylogeny, finds the simple unrooted tree fitting an $$n \times n$$ additive distance matrix $$D$$. We assume that you have already implemented a method computes LimbLength($$j$$) for a leaf $$j$$ based on the distance matrix $$D$$. Rather than selecting an arbitrary leaf $$j$$ from $$\mathcal{T}_D$$ for trimming, AdditivePhylogeny selects leaf $$n$$ (corresponding to the last row and column of $$D$$). Note that the description of the algorithm uses 1-based indexing of the rows and columns of the distance matrix $$D$$.

AdditivePhylogeny(D, n)
    if n = 2
        return the tree consisting of a single edge of length D1,2
    limbLength ← LimbLength(D, n)
    for j ← 1 to n - 1
        Dj,n ← Dj,n - limbLength
        Dn,j ← Dj,n
    (i, n, k) ← three leaves such that Di,k = Di,n + Dn,k
    x ← Di,n
    remove row n and column n from D
    T ← AdditivePhylogeny(D, n - 1)
    v ← the (potentially new) node in tree T at distance x from i on the path between i and k
    add leaf n back to tree T by creating a limb (v, n) of length limbLength
    return tree T

Assignment

Add a method additive_phylogeny to the class DistanceMatrix that takes no arguments. The method must return the unrooted tree (an object of the class UnrootedTree) resulting from applying the AdditivePhylogeny on the distance matrix.

Example

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

>>> D = DistanceMatrix.loadtxt('distances.txt')
>>> D.additive_phylogeny()
UnrootedTree((0, 4, 11.0), (1, 4, 2.0), (2, 5, 6.0), (3, 5, 7.0), (4, 5, 4.0))