Algorithmic Thinking in Bioinformatics Quiz 2: 4 August 2024 (May 2024 term)

1NEIGHBORJOINING(D, n)
2  if n = 2
3    T ← the tree consisting of a single edge of length D_{1,2}
4    return T
5  D* ← the neighbor-joining matrix constructed from the distance matrix D
6  find elements i and j such that D*_{i,j} is a minimum non-diagonal element of D*
7  Δ ← (TOTALDISTANCE_D(i) − TOTALDISTANCE_D(j)) / (n − 2)
8  limbLength_i ← [    I    ]
9  limbLength_j ← [    II    ]
10  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})
11    for any k
12  remove rows i and j from D
13  remove columns i and j from D
14  T ← NEIGHBORJOINING(D, n − 1)
15  add two new limbs (connecting node m with leaves i and j) to the tree T
16  assign length limbLength_i to LIMB(i)
17  assign length limbLength_j to LIMB(j)
18  return T