Alignment

BA5G — Compute the Edit Distance Between Two Strings

solved Problem statement

BA5E — Find a Highest-Scoring Alignment of Two Strings

solved Problem statement

One call: global, BLOSUM62, linear gap of 5.

BA5F — Find a Highest-Scoring Local Alignment of Two Strings

solved Problem statement

PAM250, not BLOSUM62 — the two disagree enough to change the answer, and the problem says which it wants.

BA5H — Find a Highest-Scoring Fitting Alignment of Two Strings

solved Problem statement

All of w against any window of v. Semiglobal returns the same number on this input for a different reason — it would clip w's ends too — so a fitting mode was added rather than asserting the coincidence.

BA5I — Find a Highest-Scoring Overlap Alignment of Two Strings

solved Problem statement

The shape read assembly asks for: where the end of one read agrees with the start of the next.

BA5J — Align Two Strings Using Affine Gap Penalties

solved Problem statement

Charging for opening a gap and less per symbol after is what stops one long insertion being priced as a run of unrelated ones.

BA5K — Find a Middle Edge in an Alignment Graph in Linear Space

solved Problem statement

A full alignment table costs O(nm) memory; one column costs O(n). Two linear-space sweeps meeting in the middle locate where the best alignment crosses it. Asserted against the full aligner: the middle node's total equals the alignment's own score.

BA5L — Align Two Strings Using Linear Space

solved Problem statement

Hirschberg's algorithm on BA5K's middle edge. Each half is re-swept, but the halves shrink geometrically so the total stays O(nm) while memory drops from a table to a column — the trade that makes whole-genome alignment possible. Reproduces the published alignment exactly.

BA5M — Find a Highest-Scoring Multiple Sequence Alignment

solved Problem statement

Three sequences need a cube, and each cell has seven predecessors rather than three. The cost is O(n^k), which is why exact multiple alignment stops being possible at a handful of sequences and real tools use heuristics. Returns a different optimal alignment from the published one; the assertion recounts the agreeing columns.