Interactive demos of sequence algorithms

Single-page teaching demos of core algorithms in sequence analysis: pairwise alignment, read mapping and genome assembly. Each page runs entirely in the browser on toy inputs you can edit; step through the algorithm with the buttons or the arrow keys and watch every intermediate state.

1. 1Edit distance by dynamic programming
   Fill the DP matrix cell by cell or row by row. Every cell shows an arrow from each predecessor that attains the minimum, so ties are visible, and a toggle highlights all optimal traceback paths.
   Levenshtein distance · O(NM) · traceback
2. 2Ukkonen’s O(ND) algorithm, wavefront style
   Compute only the cells whose edit distance is small. Wave d expands from the ed = d−1 cells and then extends along matching diagonals; cells the algorithm never visits stay blank.
   diagonal transition · O(ND) · wavefront
3. 3BLAST-like alignment: seed and extend
   Index the reference into k-letter words, look up every query word, extend each seed end-to-end without gaps, and keep the placement with the most matches. Seeds and extensions are drawn as diagonals of the alignment matrix.
   k-mer dictionary · seed and extend · gap-free hits
4. 4bwa-aln: backtracking on the prefix trie
   Read a short query backwards through the prefix trie of the reference, where every node holds a suffix-array interval, and try mismatches from a priority stack. Turn on the bounded mode to see how a precomputed lower bound D prunes hopeless branches.
   FM-index · backward search · bounded backtracking
5. 5Assembly with an overlap graph
   From a handful of error-free reads: find exact dove-tail overlaps, remove transitive edges, compact non-branching paths into unitigs, then drop non-best overlaps and compact again. The graph is drawn live and can be rearranged by dragging.
   overlap graph · transitive reduction · unitigs