Implement the Neighbor Joining Algorithm solved by 50

Sept. 8, 2015, 2:38 a.m. by Rosalind Team

The pseudocode below summarizes the neighbor-joining algorithm.

if n = 2
  T ← tree consisting of a single edge of length D1,2
  return T
D' ← neighbor-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
TNeighborJoining(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

Neighbor Joining Problem

Construct the tree resulting from applying the neighbor-joining algorithm to a distance matrix.

Given: An integer n, followed by a space-separated n x n distance matrix.

Return: An adjacency list for the tree resulting from applying the neighbor-joining algorithm. Edge-weights should be accurate to two decimal places (they are provided to three decimal places in the sample output below).

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

0   23  27  20
23  0   30  28
27  30  0   30
20  28  30  0

Sample Output


Extra Dataset

Please login to solve this problem.