ROSALIND | Implement the Neighbor Joining Algorithm

The pseudocode below summarizes the neighbor-joining algorithm.

NeighborJoining(D,n)
if n = 2
T ← tree consisting of a single edge of length D_1,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'
Δ ← (TotalDistance_D(i) - TotalDistance_D(j)) /(n - 2)
limbLength_i ← (1/2)(D_i,j + Δ)
limbLength_j ← (1/2)(D_i,j - Δ)
add a new row/column m to D so that D_k,m = D_m,k = (1/2)(D_k,i + D_k,j - D_i,j) for any k
remove rows i and j from D
remove columns i and j from D
T ← NeighborJoining(D, n - 1)
add two new limbs (connecting node m with leaves i and j) to the tree T
assign length limbLength_i to Limb(i)
assign length limbLength_j 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

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

Sample Output

0->4:8.000
1->5:13.500
2->5:16.500
3->4:12.000
4->5:2.000
4->0:8.000
4->3:12.000
5->1:13.500
5->2:16.500
5->4:2.000

Implement the Neighbor Joining Algorithm solved by 216

Neighbor Joining Problem

Sample Dataset

Sample Output

Extra Dataset

Implement the Neighbor Joining Algorithm solved by 216

Neighbor Joining Problem

Sample Dataset

Sample Output

Extra Dataset

Report a typo