64 bit and even 128 bit hash

[jianshu93]

Dear team,

I noticed that 32 bit was the default hash output. However, in many cases, 32 bit is not random enough, especially for genomics. In minimap2, 32 bit was enough because all needed is the position of minimizers and then do chaining and extend step, but in other applications, the hash needs be reused for sequence identity estimation et.al., just concatenate 2 32 bit hash for a 64 bit output?

Best,
Jianshu

[RagnarGrootKoerkamp]

Hey,

So for minimizer computations, we actually only use 16 bits if the hash. In practice that should be fine, because the window size is rarely more than 100 or 1000 at most, so 16k hash values should be sufficient.

If you want to hash the minimizer kmers, you can simply extract the kmers with the (just renamed) as_u64 or iter_minimizer_values functions, and then hash them however you like.

The internal 32bit nthash is intentionally not really exposed in the public api. (It's accessible and I do use it in simd-sketch also, but in the context of minimizers, you'll have to hash the knees yourself.)

[jianshu93]

But I do not want to rehash because it can be expensive for many genomes. If a single hash is enough, even if it is slower, we can still save a lot of time for rehashing. This is also how I understand the nthash paper, using u64, the output is almost universal and can be directly used for downstream applications. The mashmap paper use this idea, they use murmurhash128 to hash kmers, and then extract minimizers and reuse the minimizer hash directly for bottom-k MinHash, we can do the same thing to use the hash directly for one permutation hashing. No need to sort and no need to rehash. I think this will be the most accurate but also fast minimizer-minhash estimator.

Does this make sense? --Jianshu

[RagnarGrootKoerkamp]

murmurhash128 to hash kmers

The point is that using murmurhash128 for every single kmer would be hard to implement using SIMD, and surely be quite slow. Anyway each 256bit simd vector could only hold 2 hashes instead of currently 8 32bit hashes, so that alone might give a 4x slowdown. Also this probably does not support rolling-hashing?

Thus, instead we choose to use a super simple 32-bit version of NtHash that parallellizes very well to compute the minimizers.
Then, we can simply extract the minimizers and their reverse complements (which is pretty efficient), take the minimum of the two as the canonical representation, and then only hash those.

no need to sort

why does whether things need to be sorted depend on the size of the hash?

most accurate

For accuracy, it shouldn't matter if we use a 16bit or 128bit hash for minimizer selection.

also fast

so to summarize my point is: it's much better to compute the slow hash only for a small subset of kmers. This way, we save a lot of time by not computing it for all kmers that are not minimizers.

[RagnarGrootKoerkamp]

Ok maybe a followup question because I'm curious: do you really need 128bit hashes for sketching purposes? Could you give some reasoning for this or an example where this is absolutely necessary?

Specifically if k<=32, each kmer is simple a 64bit number, so you could eg use some invertible hash (using bit-rotate and wrapping multiplications) which should be good enough?