<p>When a k-mer is identical to its reverse complement, both are canonical. Note that a canonical k-mer is a sequence, irrelevant to its position(s) in the input string. More precisely, give a string $s$, its <em>canonical string</em> is
$$
{\rm canonical}(s|h)=\left\{\begin{array}{ll}
s &amp; \mbox{if $h(s)&lt;h(\overline{s})$}\\
\overline{s} &amp; \mbox{otherwise}\\
\end{array}\right.
$$
where $\overline{s}$ is the Watson-Crick reverse complement of $s$ and $h$ is an arbitrary string hash function. In practice, we most often use 2-bit encoding as $h$. Order under such a hash function is equivalent to the lexicographical order.</p>

CC BY-SA 3.0
2018-02-05T09:16:48.123Z
Stated differently, each program can have different canonical k-mers given the same input.
Devon Ryan
CC BY-SA 3.0
2018-02-05T20:27:01.150Z
Thanks for the comment. My less jargon-y translation is: "Kmer counting programs store kmers using a hash, not a string. The hash function produces the same value for a kmer and its Watson-Crick reverse complement. When the kmer counting program prints the counts in human-readable format, it translates the kmer's hash value to a string. Whether one string representation of a kmer or its reverse complement is reported depends on the program-defined "alphabetical order." In the case of KMC, that "alphabetical order" is {ACGT}. This explains why the kmers observed above were reported.
conchoecia
CC BY-SA 3.0
2018-02-05T04:49:04.590Z
2018-02-05T14:04:07.793Z
2018-02-05T14:04:07.793Z
user172818
<p>When counting canonical kmers, ie kmers in which both the forward and reverse complement of a sequence are treated as identical, how do kmer counting programs decide which kmer to use as the canonical sequence? Do they all work the same way?</p>

<p>To investigate I made a string with <code>GAGTGCGGAATACCACTCTT</code> which contains all 16 possible 2mers. I then used <a href="https://github.com/refresh-bio/KMC" rel="noreferrer">kmc</a> to figure out how they determine which kmer is used. Only the kmers in the <code>filtered</code> column below appeared. So, it looks like KMCs' 'canonical' kmers are the ones that first occur alphabetically.</p>

<pre><code>╔════════════════╦═════╦════════════════════╦══════════╗
║ Possible Kmers ║ RCs ║ RC occurs earlier? ║ filtered ║
╠════════════════╬═════╬════════════════════╬══════════╣
║ TT             ║ AA  ║ YES                ║ TA       ║
║ TG             ║ CA  ║ YES                ║ GC       ║
║ TC             ║ GA  ║ YES                ║ GA       ║
║ TA             ║ TA  ║                    ║ CG       ║
║ GT             ║ AC  ║ YES                ║ CC       ║
║ GG             ║ CC  ║ YES                ║ CA       ║
║ GC             ║ GC  ║                    ║ AT       ║
║ GA             ║ TC  ║                    ║ AG       ║
║ CT             ║ AG  ║ YES                ║ AC       ║
║ CG             ║ CG  ║                    ║ AA       ║
║ CC             ║ GG  ║                    ║          ║
║ CA             ║ TG  ║                    ║          ║
║ AT             ║ AT  ║                    ║          ║
║ AG             ║ CT  ║                    ║          ║
║ AC             ║ GT  ║                    ║          ║
║ AA             ║ TT  ║                    ║          ║
╚════════════════╩═════╩════════════════════╩══════════╝
</code></pre>

<p>Do all kmer counting programs use the same canonical kmers, and if so do you have documentation explaining this? I wasn't able to find anything in the papers for <code>jellyfish</code> or <code>kmc</code>. </p>

<k-mer>
How do kmer counters determine which kmer is 'canonical'?
# How do kmer counters determine which kmer is 'canonical'?

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

When counting canonical kmers, ie kmers in which both the forward and reverse complement of a sequence are treated as identical, how do kmer counting programs decide which kmer to use as the canonical sequence? Do they all work the same way?
To investigate I made a string with GAGTGCGGAATACCACTCTT which contains all 16 possible 2mers. I then used kmc to figure out how they determine which kmer is used. Only the kmers in the filtered column below appeared. So, it looks like KMCs' 'canonical' kmers are the ones that first occur alphabetically.
╔════════════════╦═════╦════════════════════╦══════════╗
║ Possible Kmers ║ RCs ║ RC occurs earlier? ║ filtered ║
╠════════════════╬═════╬════════════════════╬══════════╣
║ TT             ║ AA  ║ YES                ║ TA       ║
║ TG             ║ CA  ║ YES                ║ GC       ║
║ TC             ║ GA  ║ YES                ║ GA       ║
║ TA             ║ TA  ║                    ║ CG       ║
║ GT             ║ AC  ║ YES                ║ CC       ║
║ GG             ║ CC  ║ YES                ║ CA       ║
║ GC             ║ GC  ║                    ║ AT       ║
║ GA             ║ TC  ║                    ║ AG       ║
║ CT             ║ AG  ║ YES                ║ AC       ║
║ CG             ║ CG  ║                    ║ AA       ║
║ CC             ║ GG  ║                    ║          ║
║ CA             ║ TG  ║                    ║          ║
║ AT             ║ AT  ║                    ║          ║
║ AG             ║ CT  ║                    ║          ║
║ AC             ║ GT  ║                    ║          ║
║ AA             ║ TT  ║                    ║          ║
╚════════════════╩═════╩════════════════════╩══════════╝

Do all kmer counting programs use the same canonical kmers, and if so do you have documentation explaining this? I wasn't able to find anything in the papers for jellyfish or kmc.

**Tags:** k-mer

---

## 1 answers

### Answer by username_1 on 2018-02-05. Score: 9 | Accepted answer

When a k-mer is identical to its reverse complement, both are canonical. Note that a canonical k-mer is a sequence, irrelevant to its position(s) in the input string. More precisely, give a string $s$, its *canonical string* is
$$
{\rm canonical}(s|h)=\left\{\begin{array}{ll}
s & \mbox{if $h(s)

> **Comments:**
> **username_2**: Stated differently, each program can have different canonical k-mers given the same input.  
> **username_0**: Thanks for the comment. My less jargon-y translation is: "Kmer counting programs store kmers using a hash, not a string. The hash function produces the same value for a kmer and its Watson-Crick reverse complement. When the kmer counting program prints the counts in human-readable format, it translates the kmer's hash value to a string. Whether one string representation of a kmer or its reverse complement is reported depends on the program-defined "alphabetical order." In the case of KMC, that "alphabetical order" is {ACGT}. This explains why the kmers observed above were reported.  

---

