<p>However you want.</p>

<p>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 desirable/undesirable. What is actually done doesn't matter, as long as there is a deterministic algorithm that can be applied to every single possible sequence.</p>

<p>The nice thing about most modern languages is that they've already got their own hash implementations that map keys to values, which work fine for quick experiments: C++ has <a href="http://www.cplusplus.com/reference/unordered_map/unordered_map/" rel="nofollow noreferrer">unordered map</a>, perl has <a href="http://perldoc.perl.org/perlintro.html#Perl-variable-types" rel="nofollow noreferrer">hashes</a>, python has <a href="https://docs.python.org/3/tutorial/datastructures.html#dictionaries" rel="nofollow noreferrer">dictionaries</a>, and R has <a href="https://www.rdocumentation.org/packages/base/versions/3.4.3/topics/name" rel="nofollow noreferrer">names</a>.</p>

<p>The actual bare-metal implementation of the thing that converts a string of text into a number is complicated, particularly if you want code to be cryptographically secure, and the hash array to have an access speed that is very close to the amount of time it takes to retrieve a single value from memory. A useful starting point to explore this in more depth might be the Wikipedia page on the <a href="https://en.wikipedia.org/wiki/Java_hashCode%28%29" rel="nofollow noreferrer">Java hashcode function</a>.</p>

CC BY-SA 4.0
2018-02-08T04:40:20.200Z
2019-02-02T10:31:19.663Z
2019-02-02T10:31:19.663Z
gringer
<p>You can convert any string hash function to a "canonical" DNA string hash function.</p>

<p>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)=\tilde{h}(\overline{s})=\tilde{h}({\rm canonical}(s|h))
$$</p>

<p>PS: There are more than one ways to define "canonical" hash function. For example, let $h_0(\cdot)$ be the 2-bit encoding hash function. Given any <em>integer</em> hash function $g(\cdot)$, we can define:
$$
h'(s)\triangleq g\big[\min\{h_0(s),h_0(\overline{s})\}\big]
$$
Then we still have
$$
h'(s)=h'(\overline{s})
$$
You can also replace $\min\{\}$ with XOR or plus to get new definitions.</p>

CC BY-SA 3.0
2018-02-08T21:09:41.050Z
2018-02-08T21:21:39.330Z
2018-02-08T21:21:39.330Z
user172818
<p>This question is a follow up from <a href="https://bioinformatics.stackexchange.com/questions/3462">How do kmer counters determine which kmer is 'canonical'?</a>.</p>

<p>In that question we learned that kmer counting programs use a 2-bit hash function to internally represent canonical kmers as they are being counted.</p>

<p>Now I am wondering, how can we implement such a function in C/C++ or in python? More arbitrarily, how could I calculate the canonical kmer hash value using a mathematical function?</p>

<p>For example, how would we transform the 3-mer <code>GAT</code> or the 21-mer <code>GAATACCATAGGATA</code> to 1s and 0s such that:</p>

<pre><code>hash(GAT) == hash(ATC)
hash(GAATACCATAGGATA) == hash(TATCCTATGGTATTC)
</code></pre>

CC BY-SA 3.0
2018-02-08T08:14:56.373Z
https://bioinformatics.stackexchange.com/a/293/776
Alex Reynolds
<python><k-mer><c++><hashing>
How to write a hash function for canonical kmers?
# How to write a hash function for canonical kmers?

(Asked by: username_0 on 2018-02-08)

This question is a follow up from How do kmer counters determine which kmer is 'canonical'?.
In that question we learned that kmer counting programs use a 2-bit hash function to internally represent canonical kmers as they are being counted.
Now I am wondering, how can we implement such a function in C/C++ or in python? More arbitrarily, how could I calculate the canonical kmer hash value using a mathematical function?
For example, how would we transform the 3-mer GAT or the 21-mer GAATACCATAGGATA to 1s and 0s such that:
hash(GAT) == hash(ATC)
hash(GAATACCATAGGATA) == hash(TATCCTATGGTATTC)

**Tags:** python, k-mer, c++, hashing
> **Comments:**
> **username_1**: https://bioinformatics.stackexchange.com/a/293/776  

---

## 2 answers

### Answer by username_3 on 2018-02-08. Score: 7 | Accepted answer

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)=\tilde{h}(\overline{s})=\tilde{h}({\rm canonical}(s|h))
$$

PS: There are more than one ways to define "canonical" hash function. For example, let $h\_0(\cdot)$ be the 2-bit encoding hash function. Given any *integer* hash function $g(\cdot)$, we can define:
$$
h'(s)\triangleq g\big[\min\{h\_0(s),h\_0(\overline{s})\}\big]
$$
Then we still have
$$
h'(s)=h'(\overline{s})
$$
You can also replace $\min\{\}$ with XOR or plus to get new definitions.


---

### Answer by username_2 on 2018-02-08. Score: 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 desirable/undesirable. What is actually done doesn't matter, as long as there is a deterministic algorithm that can be applied to every single possible sequence.

The nice thing about most modern languages is that they've already got their own hash implementations that map keys to values, which work fine for quick experiments: C++ has [unordered map](http://www.cplusplus.com/reference/unordered_map/unordered_map/), perl has [hashes](http://perldoc.perl.org/perlintro.html#Perl-variable-types), python has [dictionaries](https://docs.python.org/3/tutorial/datastructures.html#dictionaries), and R has [names](https://www.rdocumentation.org/packages/base/versions/3.4.3/topics/name).

The actual bare-metal implementation of the thing that converts a string of text into a number is complicated, particularly if you want code to be cryptographically secure, and the hash array to have an access speed that is very close to the amount of time it takes to retrieve a single value from memory. A useful starting point to explore this in more depth might be the Wikipedia page on the [Java hashcode function](https://en.wikipedia.org/wiki/Java_hashCode%28%29).


---

