Rosalind — Bioinformatics Textbook Track — Phylogeny

BA7A — Compute Distances Between Leaves

In a tree there is exactly one path between any two nodes, so there is nothing to optimise — no Dijkstra, no relaxation. That uniqueness is also what lets BA7C invert the distances to recover the tree.

BA7B — Compute Limb Length

solved Problem statement

The minimum over pairs picks the two leaves whose paths diverge immediately, leaving the limb alone. This is what makes BA7C possible: knowing the limb, it can be subtracted off and the leaf removed.

BA7C — Implement AdditivePhylogeny

solved Problem statement

The exact inverse of BA7A. Exact only because the matrix is additive. Asserted by rebuilding every pairwise distance from the tree rather than by matching one printed layout, since internal node numbering is not unique.

BA7D — Implement UPGMA

solved Problem statement

Hierarchical clustering with heights, so every leaf ends the same distance from the root — a molecular clock made concrete. The assertion checks that ultrametric property directly. Often wrong in practice, which is what BA7E exists to avoid.

BA7E — Implement the Neighbor Joining Algorithm

solved Problem statement

Corrects each distance by how far each leaf sits from everything else, so a fast-evolving lineage is no longer mistaken for a distant one. This sample matrix is not additive — its three four-point pairings are 53, 55 and 50 — so no tree fits it exactly and the assertion checks that rather than expecting the distances back unchanged.

BA7F — Implement SmallParsimony

solved Problem statement

Sankoff's algorithm. Every column is independent, so each is solved separately and the scores added. Greedy choice from the leaves fails: a locally cheap base can force two changes higher up. Returns a different labelling of equal score, and the assertion recounts the changes it actually shows.

BA7G — Adapt SmallParsimony to Unrooted Trees

solved Problem statement

An edge costs the same read in either direction, so the score does not depend on where a root is placed — hang one in the middle of any edge, run BA7F unchanged, then remove it. The labelling can differ; the score cannot, which the assertion checks by comparing the rooted and unrooted totals.