Hot answers tagged

9 votes

Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

Let f and r be two integers. They always keep the k-mer on the forward and reverse strand, respectively. At a new base ...
user172818's user avatar
  • 6,525
8 votes
Accepted

Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

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 ...
Karel Břinda's user avatar
7 votes

Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

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 ...
BaCh's user avatar
  • 754
7 votes
Accepted

How to write a hash function for canonical kmers?

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}$...
user172818's user avatar
  • 6,525
5 votes

How to write a hash function for canonical kmers?

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 ...
gringer's user avatar
  • 13.9k
5 votes

Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

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 +...
Konrad Rudolph's user avatar

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