FracMinHash & scale

A genome has far too many k-mers to keep them all. snipe keeps a representative fraction of them using FracMinHash — a scaled MinHash scheme that samples the hash space by a fixed rule rather than by a fixed count. The rule is simple, and it’s what makes two independently built signatures directly comparable.

Keep the hashes below a threshold

Every k-mer is turned into a 64-bit hash (canonical murmur3 — see Edgemers for how the pair is formed). FracMinHash keeps a k-mer only when its hash lands below a threshold. That threshold is derived entirely from one knob, --scale:

hash_threshold = u64::MAX / scale

With the default scale = 10000, roughly one hash in every 10000 falls under the threshold, so snipe retains about 0.01% of distinct k-mers. Because u64::MAX is a fixed constant, the threshold is a deterministic function of scale alone — the same k-mer sampled from two different files makes the same keep-or-drop decision every time.

• Higher scale → lower threshold → sparser sample → smaller signature.
• Lower scale → higher threshold → denser sample → larger, more detailed signature.
• scale = 1 sets the threshold to u64::MAX, so every k-mer is kept (useful only for tiny inputs).

snipe records how the sample turned out: it tallies K1 hashes below vs. above the threshold, and reports the fraction below as hash efficiency in the logs.

Why this makes signatures comparable

A classic MinHash keeps a fixed number of hashes (say, the 1000 smallest). That number doesn’t scale with genome size, so a small sample and a large one end up describing very different fractions of their inputs — and you can’t cleanly intersect them.

FracMinHash instead keeps a fixed fraction. Two signatures built at the same scale sampled the hash space by the same rule, so their retained hashes are drawn from the same sub-space. That means:

• A k-mer shared by two samples is either kept in both or dropped in both — never kept in one and silently missing from the other.
• Set operations (intersect, union, difference) act on comparable samples, so containment and similarity estimates are unbiased.
• The signature grows sub-linearly with the input: doubling a genome roughly doubles the retained hashes, but a signature is always ~1/scale of the whole, keeping memory and comparison cost bounded.

This is exactly why snipe requires matching scale (and k1) before it will combine two signatures — mismatched scales sampled different fractions and cannot be compared. Attempting it raises an incompatible-signatures error rather than returning a wrong answer.

Tip

Choosing scale: the default 10000 is a good balance for genome- and read-scale work. Drop to a smaller scale when you need finer resolution on small references (amplicons, single chromosomes, plasmids), where a sparse sample would leave too few hashes to compare. Raise it when signatures are large and you want them leaner. Whatever you pick, use the same scale across every sample you intend to compare — and remember you can only ever downscale an existing signature (increase its scale), never recover hashes a higher scale dropped.

The hash function

The hash under the threshold is a canonical murmur3 hash with seed 42, computed on the lexicographically smaller of a k-mer and its reverse complement. The edgemer (K2) structure is snipe’s own layer on top of the K1 hashes.

Next

• Edgemers → — the k-mer pair that the kept hashes carry.
• The .snipesig format → — how the sampled hashes are stored, reproducibly.
• QC metrics explained → — what snipe measures once the sample is built.