Rosalind — Bioinformatics Stronghold — Alignment

EDIT — Edit Distance

The crude version of sequence comparison, and the pack refines it twice: GLOB stops treating every substitution as equally costly, and GAFF stops treating a gap of k bases as k separate events. Useful mainly as the baseline those two improve on.

GLOB — Global Alignment with Scoring Matrix

solved Problem statement

BLOSUM62 is built from substitution frequencies actually observed in aligned protein blocks, so swapping a residue for a chemically similar one costs little and swapping it for an unrelated one costs a lot. That is the information EDIT throws away by charging one for every mismatch.

LOCA — Local Alignment with Scoring Matrix

solved Problem statement

Two proteins may share a single conserved domain inside otherwise unrelated sequence. A global alignment has to align the unrelated parts too and buries the signal; local alignment reports only the stretch that matches, which is what makes it the basis of database search.

GAFF — Global Alignment with Scoring Matrix and Affine Gap Penalty

solved Problem statement

One insertion of ten bases is a single mutational event, not ten. Charging per base makes an aligner scatter several short gaps where one long gap is right, so opening a gap costs more than extending it.

OAP — Overlap Alignment

solved Problem statement

Brute-force DP over lists; ~9 s. A flat-buffer implementation would be the natural follow-up.

SIMS — Finding a Motif with Modifications

solved Problem statement

Fitting alignment by dynamic programming over two rolling rows, written in place with indexed assignment. Rebuilding each row with push() took about 40 s; this takes about 18 s.

EDTA — Edit Distance Alignment

solved Problem statement

Any optimal alignment is valid, so the assertion checks the distance and that the two rows are equal length, recover the inputs once gaps are removed, and differ in exactly `distance` positions.

CTEA — Counting Optimal Alignments

solved Problem statement

Two passes: the edit-distance table, then a count of the paths achieving it. The distance agrees with EDIT on the same pair of strings.

GCON — Global Alignment with Constant Gap Penalty

solved Problem statement

The affine recurrence with a zero extension cost. Cross-checked against GLOB, which scores the same pair at 8 with a per-residue gap of 5.

LAFF — Local Alignment with Affine Gap Penalty

solved Problem statement

One call. Local mode and affine gaps were both already in align(); what was missing until recently was any way to reach a substitution matrix from it.

SMGB — Semiglobal Alignment

solved Problem statement

Semiglobal is one of the two alignment modes added for this pack; before that the problem could not be expressed at all.

MGAP — Maximizing the Gap Symbols of an Optimal Alignment

solved Problem statement

The scoring is deliberately unspecified, which is the hint: a maximum-score alignment matches as much as it can, so the answer falls out of the longest common subsequence.

MULT — Multiple Alignment

solved Problem statement

Four sequences need a hypercube and 2^k-1 moves out of every cell — fifteen here, against three for a pairwise alignment. Exact multiple alignment costs O(n^k), which is why every tool that aligns hundreds of sequences is approximating.

OSYM — Isolating Symbols in Alignments

solved Problem statement

The best alignment through a given pairing is the best way of reaching it plus the best way of leaving it, so one forward table and one backward table answer all 49 pairs at once — the same trick BA5K uses to find a middle edge.