Rosalind — Bioinformatics Stronghold — Phylogeny

TREE — Completing a Tree

A tree on n nodes has exactly n-1 edges, so the answer is that count minus the edges already present, with no search involved. The point is recognising the invariant rather than exploring the graph.

INOD — Counting Phylogenetic Ancestors

solved Problem statement

An unrooted binary tree with n leaves always has n-2 internal nodes, whatever its shape. That fixed relationship is what lets EUBT count trees by insertion and CNTQ count quartets without ever examining a topology.

PDST — Creating a Distance Matrix

solved Problem statement

Pairwise p-distance: the fraction of positions at which two sequences differ. It is the crude measure HAMM warns about, applied to every pair, and it feeds the tree-building problems that follow.

ROOT — Counting Rooted Binary Trees

solved Problem statement

Rooted binary trees on n leaves number (2n-3)!!, which passes a billion by n=11. That growth is why phylogenetics searches tree space rather than enumerating it.

CUNR — Counting Unrooted Binary Trees

solved Problem statement

The unrooted count, (2n-5)!!, which is the rooted count one step back — a rooted tree is an unrooted one with a root placed on some edge. EUBT constructs these rather than counting them.

NWCK — Distances in Trees

solved Problem statement

Carries a small Newick parser written in BioLang — phylo_tree() renders SVG and nw_to_distance_matrix() takes a table, so neither parses Newick.

NKEW — Newick Format with Edge Weights

solved Problem statement

The NWCK parser extended to read ':length' suffixes, walking to the lowest common ancestor rather than breadth-first.

CTBL — Creating a Character Table

solved Problem statement

A character table records the splits a set of taxa admits. CHBP inverts it back into a tree, which works only because the splits of a consistent table are nested or disjoint and never crossing.

SPTD — Phylogeny Comparison with Split Distance

solved Problem statement

The two trees here share no nontrivial split, so the distance is 2(n-3) = 6; the splits of each are printed so that is checkable by eye. The assertion also requires a tree compared with itself to give 0, which tests the canonical split orientation rather than just the arithmetic.

MEND — Inferring Genotype from a Pedigree

solved Problem statement

The distribution was worked out by hand up the pedigree before being asserted, and the example prints that derivation. The assertion also requires the three probabilities to sum to one.

CSET — Fixing an Inconsistent Character Set

solved Problem statement

Any character whose removal restores consistency is a valid answer, so the assertion checks the four-gamete condition on the result and that the input really was inconsistent, rather than naming one row.

CSTR — Creating a Character Table from Genetic Strings

solved Problem statement

A split is nontrivial only when both sides hold at least two strings; a position where one string differs from all the others separates nothing. Which state is written as 1 is arbitrary, so the assertion accepts a row or its complement.

ALPH — Alignment-Based Phylogeny

solved Problem statement

Small parsimony with the gap as a fifth symbol rather than a missing value — in an alignment a gap is evidence that an indel happened, and treating it as unknown would make every column containing one free. Finds a different labelling of equal score, so the assertion recounts the changes.

CNTQ — Counting Quartets

solved Problem statement

The answer is C(n,4), and the reason matters more than the number: in a fully resolved tree any four taxa are separated into two pairs by some edge, so the shape never enters into it. The assertion enumerates all 15 subsets and confirms it rather than trusting the formula.

QRT — Quartets

solved Problem statement

An 'x' means not scored, not a third state — so a partial character still separates the taxa it did see, and missing data does not make it useless. Quartets are recorded canonically because neither side nor the order within a side carries meaning, and two characters often support the same one.

CHBP — Character-Based Phylogeny

solved Problem statement

The inverse of CTBL. It works because a consistent table's splits are laminar — any two nested or disjoint, never crossing — and a laminar family is exactly a tree. Returns a differently-rooted Newick, so the assertion compares induced splits rather than a formatting choice.

EUBT — Enumerating Unrooted Binary Trees

solved Problem statement

Built by insertion: every unrooted binary tree arises exactly once by splitting an edge and hanging the next taxon off it, which is why the count is (2n-5)!! — fifteen trees at n=5, over two million at n=10. That growth is why nobody enumerates trees to find the best one.

QRTD — Quartet Distance

solved Problem statement

Quartets degrade gracefully where splits do not: moving one taxon changes a handful of quartets but can destroy every split at once. Asserted to be zero between a tree and itself, which is the identity any distance must satisfy.

RSUB — Identifying Reversing Substitutions

solved Problem statement

A site that mutates and mutates back looks, from the tips alone, as though nothing happened — which is exactly what makes distant relationships hard to recover. Only the internal labels reveal it, which is why the problem supplies them.