Introduction

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 ww 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.

Try It

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

<!-- Minimizer Sketching interactive demo -->
<div class="controls">
  <label>Sequence<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">Reset</button>
</div>
<div id="seq-display" class="seq-display" aria-label="DNA sequence with window and minimizer highlighted"></div>
<div id="window-info" class="window-info"></div>
<div class="sketch-label">Sketch (selected minimizers)</div>
<div id="sketch-display" class="sketch-display" aria-label="Minimizer sketch — selected k-mers"></div>
<div id="stats" class="stats"></div>

/* Minimizer sketching demo styles */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A minimizer is the lexicographically smallest k-mer within a sliding window of width w.
// We slide the window one base at a time and mark the minimum k-mer; the sketch is the deduplicated set of all marked k-mers.

const seqInput = document.getElementById('seq-input');
const kInput   = document.getElementById('k-input');
const wInput   = document.getElementById('w-input');
const seqDisp  = document.getElementById('seq-display');
const winInfo  = document.getElementById('window-info');
const sketchDisp = document.getElementById('sketch-display');
const statsEl  = document.getElementById('stats');

// Compute minimizers for the full sequence
function computeMinimizers(seq, k, w) {
  const n = seq.length;
  if (k > n || w > n - k + 1) return { minimizers: new Set(), positions: [], windowMins: [] };
  const kmers = [];
  for (let i = 0; i <= n - k; i++) kmers.push(seq.slice(i, i + k));
  const windowMins = [];
  for (let i = 0; i <= n - k - w + 1; i++) {
    // find the lex-smallest k-mer starting in this window
    let minKmer = null, minPos = -1;
    for (let j = i; j < i + w; j++) {
      if (minKmer === null || kmers[j] < minKmer) { minKmer = kmers[j]; minPos = j; }
    }
    windowMins.push({ pos: minPos, kmer: minKmer, windowStart: i });
  }
  // deduplicate by (kmer, position) to get the sketch
  const seen = new Set();
  const positions = new Set();
  const selected = [];
  for (const wm of windowMins) {
    const key = wm.kmer + '@' + wm.pos;
    if (!seen.has(key)) { seen.add(key); positions.add(wm.pos); selected.push({ pos: wm.pos, kmer: wm.kmer }); }
  }
  return { minimizers: positions, selected, windowMins };
}

let currentWindow = 0;
let state = null;

function render() {
  const seq = seqInput.value.toUpperCase().replace(/[^ACGT]/g, 'N');
  const k = Math.max(2, Math.min(6, parseInt(kInput.value) || 3));
  const w = Math.max(2, Math.min(10, parseInt(wInput.value) || 5));
  state = computeMinimizers(seq, k, w);
  const n = seq.length;
  const numWindows = state.windowMins.length;
  if (currentWindow >= numWindows) currentWindow = 0;

  const win = numWindows > 0 ? state.windowMins[currentWindow] : null;
  const winStart = win ? win.windowStart : -1;
  const winEnd   = win ? win.windowStart + w + k - 2 : -1;
  const winMinPos = win ? win.pos : -1;

  // render individual bases with window and minimizer highlights
  seqDisp.innerHTML = '';
  for (let i = 0; i < n; i++) {
    const d = document.createElement('div');
    const kmerStart = i;
    const inWindow = i >= winStart && i <= winEnd;
    const isMinimizer = state.minimizers.has(i);
    const isCurMin = i === winMinPos;
    d.className = 'base' + (isCurMin ? ' minimizer' : isMinimizer ? ' selected' : inWindow ? ' in-window' : '');
    d.textContent = seq[i];
    d.title = i >= winStart && i <= winEnd - k + 1 ? seq.slice(i, i + k) : '';
    seqDisp.appendChild(d);
  }

  if (win) {
    winInfo.textContent = i18nFmt('Window [%from%–%to%]: minimizer = %kmer% (pos %pos%)', { from: winStart + 1, to: winEnd + 1, kmer: win.kmer, pos: win.pos + 1 });
  } else {
    winInfo.textContent = 'Sequence too short for the chosen k and w.';
  }

  // render the sketch (unique minimizer k-mers)
  sketchDisp.innerHTML = '';
  const unique = new Map();
  for (const s of state.selected) { if (!unique.has(s.kmer)) { unique.set(s.kmer, s.pos); } }
  for (const [kmer] of unique) {
    const chip = document.createElement('span');
    chip.className = 'kmer-chip'; chip.textContent = kmer;
    sketchDisp.appendChild(chip);
  }

  const total = Math.max(1, n - k + 1);
  const pct = Math.round((unique.size / total) * 100);
  statsEl.innerHTML = i18nFmt('<b>%sel%</b> minimizers selected out of %total% k-mers (<b>%pct%%</b>) — k=%k%, w=%w%', { sel: unique.size, total: total, pct: pct, k: k, w: w });
}

// auto-advance the window every 700 ms; click sequence to step manually
let timer = null;
function advance() {
  const numWindows = state ? state.windowMins.length : 0;
  if (numWindows === 0) return;
  currentWindow = (currentWindow + 1) % numWindows;
  render();
}
function startAuto() { if (!timer) timer = setInterval(advance, 700); }
function stopAuto()  { clearInterval(timer); timer = null; }

seqDisp.addEventListener('click', () => { advance(); });
document.getElementById('reset-btn').addEventListener('click', () => {
  stopAuto();
  currentWindow = 0;
  seqInput.value = 'ACGTACGTGCATGCAATCGT';
  kInput.value = 3; wInput.value = 5;
  render();
});
[seqInput, kInput, wInput].forEach(el => el.addEventListener('input', () => { currentWindow = 0; render(); }));

render();
startAuto();
Result
Console

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.

The Real Complexity

How well does the minimizer trick actually work?

  • Density guarantee. A minimizer scheme with window size ww and k-mer length kk selects at most 2w+1\frac{2}{w+1} of all k-mers in expectation (under a random ordering). In practice the reduction is roughly w/2w/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−1w + 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 nn can be computed in O(n)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)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 ww while keeping all biologically meaningful overlaps discoverable.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/minimizer-sketching/Content licensed under CC BY-NC 4.0.