Implement AdditivePhylogeny solved by 346

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).

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.

Sample Dataset

4
0   13  21  22
13  0   12  13
21  12  0   13
22  13  13  0

Sample Output

0->4:11
1->4:2
2->5:6
3->5:7
4->0:11
4->1:2
4->5:4
5->4:4
5->3:7
5->2:6

Extra Dataset

Click for an extra dataset