[Verse 1] Two strands drift apart, I build a grid to bring 'em close, Every cell's a choice—match, mismatch, gap, or ghost. Needleman-Wunsch runs corner to corner, stretched out global, Smith-Waterman digs a pocket, keeps the local node so noble. Semi-global splits the difference, no penalty on loose ends, Traceback arrows crawl uphill to where the story bends. [Chorus] N-W goes end to end, S-W finds the hidden gem, Gap open, gap extend, Gotoh's curve bends the stem, BWT flips the text, FM-index skips the mess, Seed it, chain it, score it—alphabet of yes. [Verse 2] Scoring matrix whispers what a swap is really worth, BLOSUM counts survivable swaps since protein birth, DNA keeps it simple, match plus, mismatch minus, Affine gaps say opening costs more than staying, Gotoh finds us. Three matrices in motion—insertion, deletion, match, Karlin-Altschul tells you if your score's a lucky catch. E-value counts the hits by chance across the raw, BLAST seeds an eleven-mer, extends it, bends the law. [Chorus] [Verse 3] Clustal builds a tree then aligns branch by branch, greedy and progressive, MAFFT and MUSCLE loop back till the columns turn impressive, T-Coffee blends libraries of pairs for consistency's sake, Trim the ragged edges out before the model starts to shake. Suffix array sorts every rotation, orderly and slow, Burrows-Wheeler scrambles letters, clusters where the last chars go, FM-index rides that transform, backward search walks right to left, Count and locate, ranked in blocks—memory's a lighter heft. [Verse 4] Minimizers skim the k-mers, keep the smallest in the frame, Sparse but sturdy seeds for chaining, minimap2's whole game. Chain the anchors into arcs, colinear and lean, BWA-MEM and Bowtie2 run that seed-and-extend machine. Introns split the RNA read, spliced alignment bends the arc, Multi-mapping muddies MAPQ, repeats leave a foggy mark. Bismark turns the C to T, bisulfite rewrites the code, Sort the BAM, mark duplicates, recalibrate the load. [Verse 5] Hidden Markov models hum through profile states unseen, Match, insert, delete transitions weave the hidden scene. Viterbi walks the likeliest path, forward-backward sums the rest, Pfam builds its domains from the model that scores best. De Bruijn graphs assemble reads where k-mers overlap and merge, Contigs rise from tangled paths where branching edges converge. [Bridge] Every gap's a decision, every seed's a bet, Score it, chain it, prove it—statistics is the net. From matrix cell to BWT rank, the logic never bends, Alignment's the language where a genome's story ends. [Chorus] N-W goes end to end, S-W finds the hidden gem, Gap open, gap extend, Gotoh's curve bends the stem, BWT flips the text, FM-index skips the mess, Seed it, chain it, score it—alphabet of yes. [Outro] Close the traceback, close the trap, That's the whole cerebral map.
← Module 5 — Sequence Data Formats & Tooling (Week 9) | Module 7 — Sequence Algorithms II: Assembly, k-mers & Sketching (Weeks 12–13) →