Interactive demos of sequence algorithms

Single-page teaching demos of core algorithms in sequence analysis: pairwise and multiple alignment, read mapping, genome assembly, RNA-seq quantification, hidden Markov models and haplotype phasing. 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
6. 6RNA-seq quantification with EM
   Simulate transcripts built from shared blocks and reads that map to several of them, then step through the EM iterations: split each multi-mapped read by per-base abundance, average, and watch the estimated transcript fractions converge to the simulated truth. Edit the read counts to run EM on your own data.
   latent variables · nucleotide vs transcript fraction · convergence
7. 7Hidden Markov model: fair and cheat coins
   Simulate which coin Jack throws and what he reports, then step the forward pass left to right and the backward pass right to left, rescaling at every position so nothing underflows, and watch the posterior of the cheat coin fill in against the hidden truth. Tick “estimate this parameter” to treat the cheat coin’s head probability as unknown and step through the EM iterations that recover it from the posteriors.
   forward–backward · rescaling · posterior decoding · EM
8. 8Progressive multiple sequence alignment
   Align every pair of sequences to get distances, build a UPGMA guide tree, then align up the tree: sequence to sequence, sequence to profile and profile to profile. Each step shows its DP matrix, with stacked profile columns as headers and a hover breakdown of the sum-of-pairs column scores.
   pairwise distances · UPGMA · profile alignment · sum-of-pairs
9. 9Phasing and imputation with the Li–Stephens HMM
   Explain an unphased diploid genotype as two mosaics of reference haplotypes, with a pair of panel haplotypes as the hidden state. Step the forward and Viterbi recursions left to right and the backward pass right to left, then compare the Viterbi path with posterior decoding, see which allele goes to which copy, and fill in missing genotypes from the copied haplotypes.
   diploid HMM · n² states · Viterbi · posterior decoding · imputation
10. 10Read-based phasing: minimum error correction
    Phase heterozygous SNPs from reads by minimising the number of read bases that disagree with the two haplotypes. Alternate between the best phase for each read and the best phase for each SNP, watch errors disappear, and see why random restarts are needed: even error-free reads can leave the search stuck at a local optimum.
    MEC · alternating optimisation · local optima · random restarts
11. 11Hi-C phasing: flipping SNPs across a minimum cut
    Each Hi-C read links two distant SNPs and is either consistent with the phasing or not. Build the SNP graph whose edge weights count consistent minus inconsistent reads, find a greedy cut through the most negative weight, flip one side and repeat, and compare the result with the brute-force optimum.
    SNP graph · min-cut / max-cut · greedy cut · local optima