In polynomial hashing of DNA k-mers, why does the base choice decide whether distinct k-mers collide?
answer
- the key read as a numeral
- what makes position matter at all
- try base one and see what survives
- digits must not overflow the alphabet
- base and modulus must not share factors
basics
~20 sA polynomial hash treats the key as a numeral written in the chosen base, so the base is what makes position matter. A base of 1 collapses to a character sum where reorderings collide; a base at least the alphabet size keeps distinct fixed-length k-mers distinct until the modulus folds them.
solid answer
~50 sPolynomial hashing computes `h = ((h * b) + code(c)) mod M` across the key, which is exactly reading the key as a numeral in base `b`. That is where positional sensitivity comes from. With `b = 1` every power is 1 and the hash degenerates to a sum of symbol codes, so every reordering of a k-mer collides — fatal for DNA, where reorderings are everywhere. With `b` below the alphabet size, symbol codes overflow a digit and alias systematically onto other combinations. With `b` at least the alphabet size — 4 for A/C/G/T, or a small prime such as 5 or 31 — the encoding is a genuine positional numeral, and for k-mers of a fixed length k short enough that `b^k` fits the modulus, distinct k-mers map to distinct values before any folding. Beyond that, collisions come only from the modulus, so `M` should be large and, for even bases, must not be a power of two.
code
pseudocode · 12 lines// code(A) = 0, code(C) = 1, code(G) = 2, code(T) = 3
h = 0
for i in 0..k-1
h = (h * b + code(kmer[i])) % M
return h
// b = 1 -> every power is 1, so h is a plain symbol sum
// b = 4 -> two bits per symbol; distinct length-k k-mers
// map to distinct values while 4^k <= M
// b even and M a power of two -> symbols older than
// log_b(M) positions contribute nothinggo deeper
Recall the shape of the formula — multiply the running value by the base, add the next symbol's code, take the modulus — and know that base 1 turns it into a sum where reorderings collide.
Explain the base as place value: it is what makes position count, it must be at least the alphabet size, and it must not share factors with the modulus. Be able to show why an even base with a power-of-two modulus drops early symbols.
Show you size the modulus against the key count using the birthday estimate, and that your pipeline verifies a hash match with a real comparison rather than trusting it. Explain what changes when k or the data volume grows tenfold.
Own the parameter choice as a documented decision with its assumptions written down — alphabet, fixed k, modulus width, expected key count — so a later change in read length or throughput triggers a re-check rather than a silent increase in collisions.
## The construction Polynomial hashing assigns each symbol a small integer code and evaluates the key as a polynomial: `h(s) = code(s[0])*b^(k-1) + code(s[1])*b^(k-2) + ... + code(s[k-1]) (mod M)` evaluated in Horner form so that each step is one multiply and one add. For DNA k-mers over the alphabet {A, C, G, T} the natural codes are 0, 1, 2, 3. Read that formula again and notice what it is: the key, written as a numeral in base `b`. Everything about the base's role follows from that reading. ## Why the base is what makes position matter The coefficient `b^i` is the only thing distinguishing position `i` from position `j`. Choose `b = 1` and every coefficient becomes 1, so the hash is a plain sum of symbol codes — order vanishes. In genomics that is catastrophic: `ACGT`, `TGCA` and `GTCA` all hash to 6, and a table keyed by k-mer would fold huge families of biologically distinct sequences into single buckets. Choose `b` smaller than the alphabet size — say `b = 3` for a four-symbol alphabet — and the digits overflow: the symbol code 3 in one position is worth exactly the same as a code 1 carried one position up, so `...3` and `...1,0` collide by construction, systematically rather than by bad luck. Choose `b >= 4` and each position occupies its own digit range. With `b = 4` the encoding is exactly two bits per symbol, and it is *bijective* for fixed-length k-mers: two distinct length-k sequences cannot produce the same integer as long as `4^k` fits within the modulus. That is the ideal case, and it is why fixed-k pipelines often use base 4 with a wide modulus and get zero pre-modulus collisions for k up to 32 in 64 bits. A subtlety worth carrying into the interview: this injectivity holds for **fixed-length** k-mers only. Because A codes to 0, a leading A contributes nothing, so `AC` and `C` produce the same integer. Variable-length keys need codes starting at 1, or the length mixed in. ## Why a prime base, and why the modulus interacts with it When the alphabet is not a convenient size, or when the modulus is not much larger than the key space, practitioners pick a small prime base — 31, 53, 131 are common — rather than a round number. The reason is interaction with the modulus. What you want is that the powers `b^0, b^1, b^2, ...` taken mod `M` run through a long, irregular cycle. If `b` and `M` share a factor, they do not. The sharpest instance: take an **even** base and a modulus that is a power of two. With `b = 4` and `M = 2^64`, we have `4^32 = 2^64 ≡ 0`, so every symbol from position 32 back contributes exactly nothing. Hash a 100-symbol sequence and only its last 32 symbols matter — every read sharing a suffix collides, and no amount of table growth helps. For fixed 32-mers that is harmless (it is the bijection above); for longer keys it is a silent truncation. An odd base has no such annihilation against a power-of-two modulus, which is one reason odd primes are the safe default. A large prime modulus avoids the problem for any base that is not a multiple of it, and additionally makes the map behave like arithmetic in a field, which is what the usual collision-probability estimates assume. ## Collisions after the fold Once `b^k` exceeds `M`, distinct k-mers necessarily share values — the key space is bigger than the output space. The useful model is that a well-chosen base and prime modulus make those collisions look random, so the chance that two specific distinct keys collide is roughly `1/M`, and across `n` keys the expected collision count follows the birthday estimate `n^2 / (2M)`. That is a design input: for a billion k-mers, a 32-bit modulus guarantees mass collisions, while a 61-bit prime makes them rare. It is also why pipelines that treat a hash match as proof of equality — instead of confirming with a comparison of the actual k-mers — are wrong at scale, not merely risky. ## The same choice, made differently in the wild The base is a design parameter, not a law, and mainstream ecosystems have settled it differently: Java's and Kotlin's built-in string hashing is a polynomial hash with base 31 and an implicit power-of-two modulus from fixed-width overflow, while Go's runtime hashes strings with a seeded, hardware-accelerated mixing function that is not polynomial at all. Both are defensible; they simply trade positional structure, speed, and mixing quality differently.
- With base 4 and a 64-bit modulus, when are two distinct DNA k-mers guaranteed to hash differently?When both have the same length k and k is at most 32. Then the hash is the exact base-4 numeral of the sequence, which fits in 64 bits and is injective. Across different lengths the guarantee fails, because A codes to 0 and leading A symbols contribute nothing, so a shorter sequence can equal a longer one.
- Why is a large prime modulus preferred over a power of two here?A prime shares no factor with any reasonable base, so the powers of the base cycle through a long irregular sequence and every position keeps influencing the result. With a power-of-two modulus and an even base, high powers become zero, so symbols beyond a fixed distance from the end are silently ignored.
- Two k-mers hash to the same value. Can the pipeline treat them as equal?No. The hash compresses a key space larger than the output range, so equal hashes only mean a candidate match, and across a billion keys the birthday estimate says such matches will occur. Confirm with a direct comparison of the k-mers; skipping that turns a rare collision into silent data corruption.
The base is the place-value system. Base 1 is tally marks, where rearranging the marks changes nothing; base 4 is proper positional notation, where moving a symbol changes the number.
saying these in an interview costs you the question
- Says any multiplier works as long as it is large
- Uses a character sum and calls it a string hash
- Thinks equal hash values prove the keys are equal
- Ignores that an even base with a power-of-two modulus truncates the key
- Assumes fixed-length injectivity also holds for variable-length keys