Significance:
Neighbor-Joining (Saitou & Nei, 1987) is one of the most widely used algorithms for reconstructing evolutionary trees from pairwise genetic distances — it's the algorithm behind quick phylogenetic placement in tools like MEGA, and it directly informed COVID-19 variant-tracking phylogenies during the pandemic. Unlike simpler clustering (like UPGMA), Neighbor-Joining doesn't assume a constant molecular clock, making it more biologically realistic — but that realism comes from the Q-matrix correction term, which is the trickiest part of this problem to implement correctly.
Statement
Given `n` taxa (labeled sequences/species) and their pairwise evolutionary distance matrix `D`, reconstruct an unrooted phylogenetic tree using the Neighbor-Joining algorithm: 1. While more than 2 nodes remain active, compute the **Q-matrix**: `Q(i,j) = (n-2)·D(i,j) − ΣD(i,k) − ΣD(j,k)` (sums over all currently active nodes). 2. Select the pair `(i, j)` minimizing `Q(i,j)` and join them under a new internal node `u`. 3. Compute branch lengths from `i` and `j` to `u` using the standard NJ formula, and update distances from `u` to all remaining active nodes. 4. Repeat until 2 nodes remain, then join them with a final branch of length equal to their remaining distance.
Output the resulting tree in **Newick format** (e.g., `((A:2.0,B:3.0):1.5,(C:4.0,D:4.0):1.5);`), with branch lengths rounded to 2 decimal places.
Sample Input
Taxa: A, B, C, D
Distance Matrix:
A B C D
A 0 5 9 9
B 5 0 10 10
C 9 10 0 8
D 9 10 8 0
Sample Output
((A:2.0,B:3.0):1.5,(C:4.0,D:4.0):1.5);
Constraints
- `3 ≤ n ≤ 20` taxa - Distance matrix is symmetric with zero diagonal, and satisfies the triangle inequality (a valid distance metric)
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...