K-mers & sketching in 2 minutes

New to sequencing data? Start here. In two minutes you’ll have the three ideas every later page builds on: k-mers, canonical form, and sketching. Once those click, snipe’s edgemers follow naturally.

A k-mer is just a window

A sequencing run gives you millions of short DNA reads — strings over the alphabet A, C, G, T. A k-mer is every substring of a fixed length k you get by sliding a window across a read one base at a time.

Take the read ACGTGACC with k = 5. Slide a 5-base window and you read off four k-mers:

ACGTGACC   read
ACGTG      k-mer 1
 CGTGA     k-mer 2
  GTGAC    k-mer 3
   TGACC   k-mer 4

A whole genome or sample becomes a giant multiset of these windows. Two samples that share biology share k-mers, so comparing k-mer sets is a fast way to ask “how similar are these?” — without aligning reads to a reference. This is the basis for how snipe reports coverage, depth, and error rates: it measures the sample from its k-mers, not from a BAM. snipe’s default is k1 = 51 — long enough that a 51-mer is almost always unique to one place in a genome.

Canonical form: one k-mer per strand pair

DNA is double-stranded, and the two strands run in opposite directions. The window ACGTG on one strand is the same physical stretch of DNA as its reverse complement CACGT on the other. If we counted both separately we’d double-count the same biology, and two tools reading opposite strands would disagree.

The fix is to pick a single canonical representative for each k-mer and its reverse complement. snipe builds the reverse complement (A↔T, C↔G, read back to front) and keeps whichever of the two is lexicographically smaller:

forward:   ACGTG
revcomp:    CACGT
canonical:  ACGTG   (ACGTG < CACGT)

That comparison is exactly what snipe’s core does — compare forward against its reverse complement and keep the smaller — so the k-mer becomes strand-independent. Whichever strand a read came from, you get the same answer.

Hashing: turn each k-mer into a number

Comparing strings is slow, and storing millions of 51-character windows is wasteful. So each canonical k-mer is passed through a hash function — a deterministic recipe that turns the sequence into a fixed-size integer. snipe uses murmur3 with seed 42: a fixed choice, so the same k-mer always maps to the same number.

Hashing does two jobs at once. It compacts each k-mer to a single number, and — because a good hash spreads inputs evenly across the number line — it lets us sample k-mers fairly, which is the whole trick behind sketching.

Sketching: keep a fraction, not everything

A human sample can contain billions of distinct k-mers. Storing them all is expensive and, for comparison, unnecessary. A sketch keeps only a small, representative subset — and because the same k-mer always hashes to the same number in every sample, the subsets stay comparable.

snipe uses FracMinHash: keep a k-mer only if its hash falls below a threshold set by scale. With the default scale = 10000, roughly one in every 10000 k-mers survives — an even 1/scale sample of the hash space. Two samples sketched at the same scale keep the same fraction, so their sketches can be intersected and compared directly, and a larger scale means a smaller, faster sketch.

all k-mers ──hash──▶ integers ──keep if hash below max/scale──▶ sketch

That sketch is what snipe writes, compares, and runs QC over — a compact stand-in for the full sample. Because hashing and sampling are deterministic, the same input produces the same sketch every time.

Where this is heading

snipe adds one detail to this picture. Instead of a lone k-mer, it stores a pair — a base k-mer (K1) together with a longer k-mer (K2) that has K1 centred in it, extended by a few bases on each side. This pair is called an edgemer, and it is what lets snipe distinguish a sequencing error from a real mutation.

Edgemers → — the k-mer pair at the heart of snipe.
FracMinHash & scale → — how the 1/scale sample works in detail.