Hashing & canonical k-mers

snipe is an alignment-free QC tool: it computes quality-control metrics from a k-mer sketch instead of a read alignment. That sketch is built on hashing — every k-mer snipe touches is eventually reduced to a single 64-bit number. How that number is computed decides which sequences count as “the same” and whether the DNA strand you happened to read from changes the answer. snipe’s rule is short and fixed — canonical murmur3 with seed 42.

One k-mer, one number

snipe hashes each k-mer with the murmur3 function, using the fixed seed 42. The same k-mer always maps to the same 64-bit number, regardless of machine, run, or snipe version.

The seed is a compile-time constant (MURMUR3_HASH_SEED = 42); nothing at the CLI or API can change it. The same input therefore produces the same hashes: two runs, two machines, two versions of snipe all agree on the hash of ACGT…, because the seed never moves.

Canonical: the strand should not matter

DNA is double-stranded, and a sequencer can read either strand. The same physical locus can arrive as a forward k-mer in one read and as its reverse complement in another. If snipe hashed them as written, those two reads would land on different numbers and the same locus would look like two different features.

snipe removes that ambiguity by hashing the canonical form of every k-mer — a single representative chosen for the k-mer and its reverse complement together:

1. Compute the reverse complement of the k-mer (an A↔T, C↔G swap read back to front, via a 256-entry complement lookup table).
2. Compare the forward k-mer against its reverse complement lexicographically.
3. Keep whichever is smaller — that is the canonical k-mer.
4. Hash that one with murmur3, seed 42.

Because both orientations of a locus reduce to the same lexicographically-smaller string before hashing, they produce the same hash. Strand becomes irrelevant by construction — snipe never has to know, or care, which strand a read came from.

Note

“Lexicographically smaller” means the ordinary string comparison: at the first position where the two differ, the smaller base wins. snipe compares the raw bytes of the k-mer and its reverse complement and takes the one that sorts first — no allocation, just a byte-slice comparison.

Concretely, the core does exactly this:

// forward: the k-mer as read; rc: its reverse complement (same length)
let is_naturally_canonical = forward <= rc;         // lexicographic
let canonical = if is_naturally_canonical { forward } else { rc };
let hash = _hash_murmur(canonical, 42);             // murmur3, seed 42

The comparison also tells snipe which orientation won — whether the forward window was already the canonical one. K1 and K2 are each canonicalized independently this way: every window keeps the lexicographically smaller of its own forward and reverse-complement form before hashing. See Edgemers → for how the pair is built on top of this hash.

Why murmur3, and why canonicalize before hashing

The hash feeds directly into snipe’s sampling: FracMinHash keeps a k-mer only when its hash falls in the retained fraction of the hash space, so the hash needs to scatter k-mers uniformly across the 64-bit range. murmur3 does that well and cheaply, which is exactly what a high-throughput sketching loop wants. How that retained fraction is chosen is the subject of FracMinHash & scale →.

Canonicalizing before hashing also halves the effective feature space in a principled way: forward and reverse-complement observations collapse onto one number instead of two, so a genome and its reverse-complement read set produce the same sketch. Comparisons — intersection, union, containment — then compare like with like.

Fast tables for a hot loop

Hashing runs billions of times over a large FASTX file, and the hashes have to be counted, deduplicated, and looked up just as often. For those collections snipe reaches for rustc_hash’s FxHashMap and FxHashSet rather than the standard-library defaults.

The trade is deliberate. The standard HashMap uses a DoS-resistant hasher — valuable for untrusted network input, unnecessary overhead for hashing your own sequencing reads. FxHash is a simpler, faster integer hash, and since snipe’s keys are already well-mixed murmur3 values, it’s a good fit: the expensive mixing happened once, in murmur3, and the hash table just needs to place already-random numbers into buckets quickly.

Tip

Two different hashes are doing two different jobs here. murmur3 (seed 42) turns a k-mer’s bases into its canonical feature value — the number snipe’s sketches are built from, and the same value another seed-42 tool would compute for interop. FxHash is an internal implementation detail that makes the in-memory tables holding those values fast. Only the first one is part of snipe’s data model.

Next

• Edgemers → — the k-mer pair built on top of the canonical hash.
• FracMinHash & scale → — how the hash decides what snipe keeps.
• The .snipesig format → — where the hashed features are stored.