Minimizer Sketching

A modern sequencing machine does not read a genome from start to finish. Instead it produces hundreds of millions of short reads — snippets of 100–300 bases — and then a computer must figure out where each snippet came from. That mapping step would be impossibly slow if you compared every read to every position in the reference genome character by character.

The key insight is subsampling: instead of comparing full sequences, select a small, deterministic set of short substrings — called k-mers — from each read and from the reference. If two sequences overlap, their selected subsets will share at least one element, making overlap detection fast and memory-efficient.

Minimizer sketching, introduced by Roberts & Waterman in 2004, is the most widely used subsampling rule: slide a window of $w$ positions along the sequence and, within each window, keep only the lexicographically smallest k-mer. The result is a compact sketch that still captures enough structure to detect overlaps — and because the rule is deterministic, overlapping reads always pick the same minimizers in their shared region.

Below is a short DNA sequence. The algorithm slides a window of width $w$ one position at a time and highlights the minimizer — the lexicographically smallest k-mer — inside that window.

<!-- {{c_demo_title}} -->
<div class="controls">
  <label>{{lbl_seq}}<input id="seq-input" type="text" value="ACGTACGTGCATGCAATCGT" maxlength="30" spellcheck="false" autocomplete="off"></label>
  <label>k<input id="k-input" type="number" value="3" min="2" max="6"></label>
  <label>w<input id="w-input" type="number" value="5" min="2" max="10"></label>
  <button id="reset-btn" type="button">{{btn_reset}}</button>
</div>
<div id="seq-display" class="seq-display" aria-label="{{aria_seq}}"></div>
<div id="window-info" class="window-info"></div>
<div class="sketch-label">{{lbl_sketch}}</div>
<div id="sketch-display" class="sketch-display" aria-label="{{aria_sketch}}"></div>
<div id="stats" class="stats"></div>

/* {{c_css_root}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; flex-wrap: wrap; gap: .6rem; align-items: center; margin-bottom: .8rem; }
label { display: flex; align-items: center; gap: .3rem; font-size: .85rem; }
input[type=text] { font: 600 .85rem ui-monospace, monospace; padding: .3rem .5rem; border: 1px solid #aaa; border-radius: 6px; width: 14rem; }
input[type=number] { width: 3.4rem; padding: .3rem .4rem; border: 1px solid #aaa; border-radius: 6px; text-align: center; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
.seq-display { display: flex; flex-wrap: wrap; gap: 2px; margin: .4rem 0 .5rem; min-height: 2.8rem; }
.base { width: 28px; height: 28px; display: flex; align-items: center; justify-content: center; font: 700 14px ui-monospace, monospace; border-radius: 5px; border: 1.5px solid transparent; user-select: none; background: #e8eef3; color: #1d3557; }
.base.in-window { border-color: #457b9d; background: #d6e8f5; }
.base.minimizer { background: #e76f51; border-color: #c84b2c; color: #fff; }
.base.selected { background: #f4a261; border-color: #c84b2c; color: #fff; }
.window-info { font-size: .82rem; color: #555; min-height: 1.2em; margin-bottom: .4rem; }
.sketch-label { font-size: .78rem; font-weight: 700; color: #457b9d; letter-spacing: .04em; text-transform: uppercase; margin-bottom: .25rem; }
.sketch-display { display: flex; flex-wrap: wrap; gap: 3px; min-height: 2rem; margin-bottom: .5rem; }
.kmer-chip { font: 600 12px ui-monospace, monospace; padding: .2rem .45rem; border-radius: 5px; background: #f4a261; color: #7d2e0a; border: 1px solid #c84b2c; }
.stats { font-size: .82rem; color: #444; }
.stats b { color: #1d3557; }

// Code not found

Notice that adjacent windows often share the same minimizer: when the window slides by one position the minimum rarely changes, so the sketch covers the sequence with far fewer selected k-mers than a naive dense sampling. The selected minimizers (shown in orange) are the only ones an aligner needs to index — everything else is discarded.

How well does the minimizer trick actually work?

• Density guarantee. A minimizer scheme with window size $w$ and k-mer length $k$ selects at most $\frac{2}{w+1}$ of all k-mers in expectation (under a random ordering). In practice the reduction is roughly $w/2$, so a window of 10 cuts the index to about 20 % of its naive size.
• Overlap guarantee. If two sequences share a contiguous region of length at least $w + k - 1$, they are guaranteed to share at least one minimizer in that region. This means no true overlap is missed — minimizers are a lossless filter for overlap detection.
• Computing minimizers is linear. A sliding minimum over a sequence of length $n$ can be computed in $O(n)$ using a deque (double-ended queue) that evicts k-mers leaving the window from the back and pops dominated k-mers from the front. No window requires more than $O(w)$ work amortized.
• The ordering matters. Lexicographic order works but tends to over-select A-rich k-mers. Real tools like minimap2 use a random hash to make the implicit ordering uniform, which tightens the density guarantee.

The scheme is therefore both algorithmically efficient and statistically sound: it compresses the index by a factor proportional to $w$ while keeping all biologically meaningful overlaps discoverable.

Minimizers became the backbone of modern sequence analysis once genome datasets grew too large for exhaustive comparison:

• Read mapping. Tools such as minimap2 and BWA-MEM2 build a hash table of minimizers from the reference genome. Aligning a new read then requires only a hash lookup on its own minimizers — a massive speedup over sliding a full Smith-Waterman window across billions of bases.
• De-novo assembly. Assemblers like hifiasm use minimizer overlap graphs to join reads without a reference. Two reads with a shared minimizer are candidates for overlap; the assembler then verifies locally and extends contigs.
• Metagenomics. Classifying millions of microbial reads against a database of thousands of genomes would be intractable with full alignments. MinHash sketches built from minimizers compress each genome to a few hundred values, making database-scale comparison feasible.
• Approximate nearest-neighbor search. The same sliding-window minimum idea appears in locality-sensitive hashing for general string similarity, connecting bioinformatics to the broader world of sequence alignment and pattern matching.

Wherever you need to compare many long strings efficiently, a minimizer sketch is often the first tool to reach for.

Minimizer sketching is a beautiful example of a simple rule with deep consequences: slide a window, pick the minimum k-mer, discard the rest. The result is a sketch that shrinks an index by a factor proportional to the window size while guaranteeing that no true overlap is lost.

The idea — introduced in 2004 and now embedded in nearly every major read mapper and assembler — shows that the right algorithmic primitive can turn an apparently intractable data-engineering challenge into a routine lookup. The next time you hear that a genome was sequenced and assembled in hours, a sliding-window minimum is quietly doing a large part of the work.