The following recursive algorithm, called AdditivePhylogeny,
finds the simple tree fitting an n x n additive distance matrix D. We assume that you have already implemented a program Limb(D, j) that computes LimbLength(j) for a leaf j based on the distance matrix D. Rather than selecting an arbitrary leaf j from Tree(D) for trimming, AdditivePhylogeny selects leaf n (corresponding to the last row and column of D).

AdditivePhylogeny(D, n) ifn = 2 return the tree consisting of a single edge of length D1,2 limbLength ← Limb(D, n) forj ← 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 T at distance x from i on the path between i and k add leaf n back to T by creating a limb (v, n) of length limbLength return T

Additive Phylogeny Problem

Construct the simple tree fitting an additive matrix.

Given:n and a tab-delimited n x n additive matrix.

Return: A weighted adjacency list for the simple tree fitting this matrix.

Note on formatting: The adjacency list must have consecutive integer node labels starting from 0. The n leaves must be labeled 0, 1, ..., n-1 in order of their appearance in the distance matrix. Labels for internal nodes may be labeled in any order but must start from n and increase consecutively.