Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-05T09:16:48.123Z
Answers.Text: Stated differently, each program can have different canonical k-mers given the same input.
Answers.UserDisplayName: Devon Ryan
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-05T20:27:01.150Z
Answers.Text: 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.
Answers.UserDisplayName: conchoecia
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-05T04:49:04.590Z
Answers.LastActivityDate: 2018-02-05T14:04:07.793Z
Answers.LastEditDate: 2018-02-05T14:04:07.793Z
Answers.UserDisplayName: user172818
Body: <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>
  
Tags: <k-mer>
Title: How do kmer counters determine which kmer is 'canonical'?
ThreadText: # 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](https://github.com/refresh-bio/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)<h(\overline{s})$}\\
  \overline{s} & \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.
  
  > **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.  
  
  ---
  
  