Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value? A common bioinformatics task is to decompose a DNA sequence into its constituent k-mers and compute a hash value for each k-mer. Rolling hash functions are an appealing solution for this task, since they can be computed very quickly. A rolling hash does not compute each the hash value from scratch with each k-mer: rather it updates a running hash value using an update strategy and a sliding window over the data.

It's also very useful for many applications to have a k-mer hash to the same value as its reverse complement. Unless the data were generated using a strand-specific sample prep, it's impossible to distinguish a k-mer from its reverse complement, and they should be treated as the same sequence.

Are there any rolling hashes that will map reverse complements to the same value? If not, how would we develop such an algorithm?

UPDATE: Ideally the hash function would be able to support k > 32, which would be lossy unless using something larger than a 64-bit integer.

ANOTHER UPDATE: I don't think it's necessary to store both the running k-mer and its reverse complement in a single value. If storing two k-mer strings and/or two hash values makes this easier, I'm totally cool with that.
Let f and r be two integers. They always keep the k-mer on the forward and reverse strand, respectively. At a new base c in a proper 2-bit encoding, we update the two integers as follows:

f = (f&lt;&lt;2|c) &amp; ((1ULL&lt;&lt;2*k) - 1)
r = r&gt;&gt;2 | (3ULL-c)&lt;&lt;2*(k-1)


With this updating rule, f keeps the forward strand k-mer ending at c and r is f's reverse complement. The hash of the k-mer can be min(f,r). If integer operations take constant time, computing the hashes of all k-mers of a sequence of length L takes O(L) time.

The above only works if k-mer fits a word, which means k&lt;=32 on x86. For long k-mers, you can overload bit operators in C++. In case of 32&lt;k&lt;=64, a simpler solution is to split into lower and higher bits:

c1 = c&amp;1, c2 = c&gt;&gt;1
f1 = (f1&lt;&lt;1|c1) &amp; ((1ULL&lt;&lt;k) - 1)
f2 = (f2&lt;&lt;1|c2) &amp; ((1ULL&lt;&lt;k) - 1)
r1 = r1&gt;&gt;1 | (1ULL-c1)&lt;&lt;(k-1)
r2 = r2&gt;&gt;1 | (1ULL-c2)&lt;&lt;(k-1)


This is twice as slow as the k&lt;=32 version. It is possible to implement these lines with SSE2 intrinsics, but that is overkilling.

When you want to hash a long k-mer into fewer bits, there are a few options:

xor:      f^r
min:      min(f,r)
min+hash: hash(min(f,r))


where hash() is a generic randomization hash function, which could be Murmur3, Wang's integer hash function, etc.

The following is a microbenchmark. Here, we squeeze all k-mers into a 32-bit hash table. collision_rate = 1 - #distinct_hash/#distinct_kmer. This is not the best metric, but it somehow measures the randomness, which is better than nothing.

====================================================
 Algorithm    data  max-k  k   %collision  CPU time
----------------------------------------------------
 xor          chr11  32    31     8.5%       0.9s
 xor+Wang     chr11  32    31     9.6%       1.3s
 min+Wang     chr11  32    31     1.4%       1.3s
 min+Wang     chr11  64    31     1.4%       1.9s
 min+murmur3  chr11  inf   31     1.4%       5.7s
 min+Wang     chr11  64    51     1.5%       2.1s
 min+murmur3  chr11  inf   51     1.5%       6.8s
 min+Wang     chr11  64    63     1.5%       2.1s
 min+murmur3  chr11  inf   63     1.5%       7.5s
 radix sort   chr11  -     -      -        5.6-7.3s
----------------------------------------------------
 min+Wang     hg38   64    63    26.2%        37s
 min+murmur3  hg38   inf   63    26.2%       192s
 radix sort   hg38   -     -      -         ~138s
====================================================


Observations:


Don't use XOR. In fact, XOR hashes all palindromes to 0xffff.... This is already worrying enough.
Unless you want to work with very long k-mers, don't use generic string hash functions like FNV and Murmur. Murmur is even slower than radix sorting all hashes.
For k&lt;=64, min+Wang is the best here. It is fast and simple to compute and has randomness nearly as good as murmur.