Tag Info

9

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<<2|c) & ((1ULL<<2*k) - 1) r = r>>2 | (3ULL-c)<<2*(k-1) With this updating rule, f keeps the forward strand k-mer ending at c and r is f'...

7

If your goal is to minimise storage by just having one hash per kmer and its reverse complement, there is a simple solution for non-rolling hashes. For any sequence S, you compute and store the hash of the smaller of S and its reverse complement. A simple lexicographical comparison for "smaller" is enough. In programming terms: hash=computeHash(min(S,rev(S))...

7

A rolling hash function for DNA sequences called ntHash has recently been published in Bioinformatics and the authors dealt with reverse complements: Using this table, we can easily compute the hash value for the reverse-complement (as well as the canonical form) of a sequence efficiently, without actually reverse- complementing the input sequence, as ...

7

You can convert any string hash function to a "canonical" DNA string hash function. Given a DNA string $s$, let $\overline{s}$ be its Watson-Crick reverse complement. Suppose $h:\Sigma^*\to\mathbb{Z}$ is an arbitrary string hash function. You can define $$\tilde{h}(s)\triangleq \min\{h(s),h(\overline{s})\}$$ Then for any DNA string $s$ $$\tilde{h}(s)=\... 5 However you want. One way to do this is to generate both the forward and reverse complement kmers, then choose the lexicographically-least kmer for the storage key. To delve further into this requires discussion about things like the size of the underlying array, the expected distribution of keys throughout the array, and what type of key clustering is ... 5 At its easiest, you just store the forward (F) and reverse (R) hash value. You update the forward hash value by conventional means, e.g. bit-shifting the base value into its lower bits:$$ F_{n + 1} = ((F_n \ll B \mid x) \mathop\& M,  $B$ is the bit size of the base encoding, $M$ is the word mask for a word of length $W$ bits, and can be omitted ...

Only top voted, non community-wiki answers of a minimum length are eligible