Minimap2 Algorithm Visualizer
Minimizer Sampling & Collinear Chaining
Interactive exploration of high-throughput sequence alignment indexing using (w, k)-minimizers and 2D dynamic programming collinear chaining — the algorithmic core powering Minimap2.
For anchor a_i = (x_i, y_i), the DP recurrence finds the predecessor anchor a_j maximizing:
where gap = |Δx - Δy|, penalizing insertions/deletions while rewarding contiguous collinear diagonals.
Why Minimizers Matter for Long Reads
Instead of indexing every single k-mer, (w, k)-minimizers sample roughly ≈ 2 / (w + 1) fraction of positions. This reduces memory and computation by 10–30× while retaining robust coverage across error-prone long reads.
Collinear DP Chaining
Unlike heuristic seed-and-extend approaches, 2D dynamic programming evaluates global spatial consistency across all anchor pairs $(x_i, y_i)$, finding the optimal alignment path in polynomial time.
Base-Level Alignment Extension
Once the optimal chain of anchors is identified, Minimap2 performs piecewise Suzuki-Kasahara dynamic programming (SSE/AVX accelerated) only between adjacent anchors in the chain.