Answers.Body: <p>To expand on the answer above, in case it isn't clear, we show:</p>
  <ol>
  <li>Why palindromic sequences must be even in length</li>
  <li>Why palindromic sequences induce self-loops in a de Bruijn graph</li>
  <li>Why self loops in a de Bruijn graph are problematic</li>
  </ol>
  <hr />
  <h2>1. Palindromic sequence ⇒ sequence is of even length</h2>
  <blockquote>
  <p><strong>Idea:</strong> in an odd-length k-mer, its middle nucleotide is 'flipped' in its reverse complement, so the two can never be equal.</p>
  </blockquote>
  <p>Suppose you have a palindromic sequence <span class="math-container">$X$</span>. Then <span class="math-container">$X$</span> is identical to its reverse complement, which we will label <span class="math-container">$\bar{X}$</span>.</p>
  <p>Suppose <span class="math-container">$X$</span> is of odd length. Then it is of the form <span class="math-container">$AbC$</span>, where <span class="math-container">$len(A) = len(C) = \frac{len(X)-1}{2}$</span>, and <span class="math-container">$len(b) = 1$</span>.</p>
  <p>Then</p>
  <p><span class="math-container">$X = \bar{X} \implies AbC = \overline{AbC} = \bar{C}\bar{b}\bar{A}$</span></p>
  <p>And hence:</p>
  <p><span class="math-container">$b = \bar{b}$</span></p>
  <p>(since <span class="math-container">$len(A) = len(C) = len(\bar{C}))$</span>. But this is a contradiction, since <span class="math-container">$b$</span> is a single nucleotide, and cannot be equal to its complement. Therefore k-mers of odd length cannot form palindromes.</p>
  <p>Hence the length of a k-mer that forms a palindrome must be even.</p>
  <hr />
  <h2>2. Why palindromic k-mers induce self loops</h2>
  <p>Each node in a traditional de Bruijn graph is a unique string, but in most bio-informatics implementations each pair of reverse-complementary k-1-mers are identified as a single node, e.g for <span class="math-container">$k=6$</span>:</p>
  <p><a href="https://pmelsted.wordpress.com/2014/01/17/edge-cases-in-de-bruijn-graphs/" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Hbakm.png" alt="" /></a></p>
  <p>A palindromic k-mer (of <span class="math-container">$k \geq 2$</span>) is of the form:</p>
  <p><span class="math-container">$xAy$</span></p>
  <p>where <span class="math-container">$len(A) = k-2$</span>, <span class="math-container">$x=\bar{y}$</span> and <span class="math-container">$A=\bar{A}$</span> (possibly the empty string).</p>
  <p>Hence it will contribute two nodes in the de Bruijn graph:</p>
  <ol>
  <li>its left k-1-mer <span class="math-container">$xA$</span></li>
  <li>its right k-1-mer <span class="math-container">$Ay$</span></li>
  </ol>
  <p>And an edge going from 1 to 2.</p>
  <p>But since this k-mer is palindromic, <span class="math-container">$xA = \overline{Ay}$</span> and hence these two nodes are reverse-complementary, and thus the 'same' node, and so this edge is a self loop at this node.</p>
  <hr />
  <h2>3. Why are self loops problematic?</h2>
  <p>Self-loops (if they occur in a node with <span class="math-container">$in\_degree \geq 2$</span> and <span class="math-container">$out\_degree \geq 1$</span>) increase the number of possible Eulerian paths in a de Bruijn graph (or more specifically, in the connected component containing this node, which represents a <em>contig</em>, of which their may be multiple), as you have an additional possible Eulerian path for each time you traverse this node.</p>
  <p>This increases ambiguity in reading the graph, as each possible Eulerian path is an extra possible reconstruction of the full sequence.</p>
  <p>Consider the example:</p>
  <p><a href="https://i.sstatic.net/jZSpf.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/jZSpf.png" alt="enter image description here" /></a></p>
  <p>There is only one possible Eulerian path:</p>
  <ul>
  <li><span class="math-container">$A B C D B E$</span></li>
  </ul>
  <p>However, if we include a self loop at <span class="math-container">$B$</span>, which is visited twice above, this doubles to two possible Eulerian paths:</p>
  <p><a href="https://i.sstatic.net/0tkDw.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/0tkDw.png" alt="enter image description here" /></a></p>
  <ul>
  <li><span class="math-container">$A B B C D B E$</span></li>
  <li><span class="math-container">$A B C D B B E$</span></li>
  </ul>
  <p>Depending on whether we traverse the self loop during the first time we reach <span class="math-container">$B$</span>, or the second.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-23T13:55:04.307Z
Answers.Text: https://homolog.us/Tutorials/book4/p2.4.html "Genome assembly programs also avoid even k, because with even k, many k-mers become reverse complements of their own sequences. **That causes ambiguities in the strand-specificness of the graph.** Therefore, odd k-values are preferred."
Answers.UserDisplayName: bioio
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-24T08:49:23.607Z
Answers.Text: Nice answer @ukemi. It took me a while to understand the conclusion of the point 1, so I have added there a sentence that would have helped me. I you don't like it you can reverse the change, but I would say that a small clarification would be good there.
Answers.UserDisplayName: Kamil S Jaron
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-24T10:03:10.640Z
Answers.Text: @KamilSJaron no worries, the clearer the better - yeah, technically I should have also shown existence for the implication that they must be even to follow (as opposed to just not-odd), but showing existence is trivial via example (e.g. AT, ATAT etc).
Answers.UserDisplayName: bioio
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-19T00:08:29.877Z
Answers.LastActivityDate: 2020-04-24T12:03:22.037Z
Answers.LastEditDate: 2020-06-18T08:30:41.743Z
Answers.UserDisplayName: bioio
Answers.Body: <p>From the <a href="http://www.ebi.ac.uk/~zerbino/velvet/Manual.pdf" rel="noreferrer">manual of Velvet</a>:</p>
  
  <blockquote>
    <p>it must be an odd number, to avoid palindromes. If you put in an even
    number, Velvet will just decrement it and proceed.</p>
  </blockquote>
  
  <p>the <a href="https://en.wikipedia.org/wiki/Palindromic_sequence" rel="noreferrer">palindromes</a> in biology are defined as reverse complementary sequences. The problem of palindromes is explained in this <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2874646/" rel="noreferrer">review</a>:</p>
  
  <blockquote>
    <p>Palindromes induce paths that fold back on themselves. At least one
    assembler avoids these elegantly; Velvet requires K, the length of a
    K-mer, to be odd. An odd-size K-mer cannot match its reverse
    complement.</p>
  </blockquote>
  
  <p>It is possible to construct graph with palindromes, but then the interpretation will be harder. Allowing only graphs of odd <em>k</em>-mers is just an elegant way to avoid writing a code for interpretation of a more complicated graph.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-05-19T19:30:42.477Z
Answers.Text: Lest someone in the future misinterpret this, it should be noted that [palindrome](https://en.wikipedia.org/wiki/Palindromic_sequence) in this context has a slightly more specific meaning than it [normally would in English](https://en.wiktionary.org/wiki/palindrome).
Answers.UserDisplayName: Devon Ryan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-05-19T18:52:34.737Z
Answers.LastActivityDate: 2019-02-28T13:13:44.453Z
Answers.LastEditDate: 2019-02-28T13:13:44.453Z
Answers.UserDisplayName: Kamil S Jaron
Body: <p>Why do some assemblers like <a href="https://github.com/aquaskyline/SOAPdenovo2" rel="noreferrer">SOAPdenovo2</a> or <a href="https://github.com/dzerbino/velvet" rel="noreferrer">Velvet</a> require an odd-length <em>k</em>-mer size for the construction of de Bruijn graph, while some other assemblers like <a href="https://github.com/bcgsc/abyss" rel="noreferrer">ABySS</a> are fine with even-length <em>k</em>-mers?</p>
  
Tags: <ngs><assembly><k-mer><de-bruijn-graphs>
Title: Why do some assemblers require an odd-length kmer for the construction of de Bruijn graphs?
ThreadText: # Why do some assemblers require an odd-length kmer for the construction of de Bruijn graphs?
  
  (Asked by: username_0 on 2017-05-19)
  
  Why do some assemblers like [SOAPdenovo2](https://github.com/aquaskyline/SOAPdenovo2) or [Velvet](https://github.com/dzerbino/velvet) require an odd-length *k*-mer size for the construction of de Bruijn graph, while some other assemblers like [ABySS](https://github.com/bcgsc/abyss) are fine with even-length *k*-mers?
  
  **Tags:** ngs, assembly, k-mer, de-bruijn-graphs
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2017-05-19. Score: 31 | Accepted answer
  
  From the [manual of Velvet](http://www.ebi.ac.uk/~zerbino/velvet/Manual.pdf):
  
  > it must be an odd number, to avoid palindromes. If you put in an even
  > number, Velvet will just decrement it and proceed.
  
  the [palindromes](https://en.wikipedia.org/wiki/Palindromic_sequence) in biology are defined as reverse complementary sequences. The problem of palindromes is explained in this [review](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2874646/):
  
  > Palindromes induce paths that fold back on themselves. At least one
  > assembler avoids these elegantly; Velvet requires K, the length of a
  > K-mer, to be odd. An odd-size K-mer cannot match its reverse
  > complement.
  
  It is possible to construct graph with palindromes, but then the interpretation will be harder. Allowing only graphs of odd *k*-mers is just an elegant way to avoid writing a code for interpretation of a more complicated graph.
  
  > **Comments:**
  > **username_2**: Lest someone in the future misinterpret this, it should be noted that [palindrome](https://en.wikipedia.org/wiki/Palindromic_sequence) in this context has a slightly more specific meaning than it [normally would in English](https://en.wiktionary.org/wiki/palindrome).  
  
  ---
  
  ### Answer by username_1 on 2019-04-19. Score: 14
  
  To expand on the answer above, in case it isn't clear, we show:
  
  1. Why palindromic sequences must be even in length
  2. Why palindromic sequences induce self-loops in a de Bruijn graph
  3. Why self loops in a de Bruijn graph are problematic
  
  ---
  
  ## 1. Palindromic sequence ⇒ sequence is of even length
  
  > **Idea:** in an odd-length k-mer, its middle nucleotide is 'flipped' in its reverse complement, so the two can never be equal.
  
  Suppose you have a palindromic sequence $X$. Then $X$ is identical to its reverse complement, which we will label $\bar{X}$.
  
  Suppose $X$ is of odd length. Then it is of the form $AbC$, where $len(A) = len(C) = \frac{len(X)-1}{2}$, and $len(b) = 1$.
  
  Then
  
  $X = \bar{X} \implies AbC = \overline{AbC} = \bar{C}\bar{b}\bar{A}$
  
  And hence:
  
  $b = \bar{b}$
  
  (since $len(A) = len(C) = len(\bar{C}))$. But this is a contradiction, since $b$ is a single nucleotide, and cannot be equal to its complement. Therefore k-mers of odd length cannot form palindromes.
  
  Hence the length of a k-mer that forms a palindrome must be even.
  
  ---
  
  ## 2. Why palindromic k-mers induce self loops
  
  Each node in a traditional de Bruijn graph is a unique string, but in most bio-informatics implementations each pair of reverse-complementary k-1-mers are identified as a single node, e.g for $k=6$:
  
  [![](https://i.sstatic.net/Hbakm.png)](https://pmelsted.wordpress.com/2014/01/17/edge-cases-in-de-bruijn-graphs/)
  
  A palindromic k-mer (of $k \geq 2$) is of the form:
  
  $xAy$
  
  where $len(A) = k-2$, $x=\bar{y}$ and $A=\bar{A}$ (possibly the empty string).
  
  Hence it will contribute two nodes in the de Bruijn graph:
  
  1. its left k-1-mer $xA$
  2. its right k-1-mer $Ay$
  
  And an edge going from 1 to 2.
  
  But since this k-mer is palindromic, $xA = \overline{Ay}$ and hence these two nodes are reverse-complementary, and thus the 'same' node, and so this edge is a self loop at this node.
  
  ---
  
  ## 3. Why are self loops problematic?
  
  Self-loops (if they occur in a node with $in\\_degree \geq 2$ and $out\\_degree \geq 1$) increase the number of possible Eulerian paths in a de Bruijn graph (or more specifically, in the connected component containing this node, which represents a *contig*, of which their may be multiple), as you have an additional possible Eulerian path for each time you traverse this node.
  
  This increases ambiguity in reading the graph, as each possible Eulerian path is an extra possible reconstruction of the full sequence.
  
  Consider the example:
  
  [![enter image description here](https://i.sstatic.net/jZSpf.png)](https://i.sstatic.net/jZSpf.png)
  
  There is only one possible Eulerian path:
  
  * $A B C D B E$
  
  However, if we include a self loop at $B$, which is visited twice above, this doubles to two possible Eulerian paths:
  
  [![enter image description here](https://i.sstatic.net/0tkDw.png)](https://i.sstatic.net/0tkDw.png)
  
  * $A B B C D B E$
  * $A B C D B B E$
  
  Depending on whether we traverse the self loop during the first time we reach $B$, or the second.
  
  > **Comments:**
  > **username_1**: https://homolog.us/Tutorials/book4/p2.4.html "Genome assembly programs also avoid even k, because with even k, many k-mers become reverse complements of their own sequences. **That causes ambiguities in the strand-specificness of the graph.** Therefore, odd k-values are preferred."  
  > **username_0**: Nice answer @ukemi. It took me a while to understand the conclusion of the point 1, so I have added there a sentence that would have helped me. I you don't like it you can reverse the change, but I would say that a small clarification would be good there.  
  > **username_1**: @username_0 no worries, the clearer the better - yeah, technically I should have also shown existence for the implication that they must be even to follow (as opposed to just not-odd), but showing existence is trivial via example (e.g. AT, ATAT etc).  
  
  ---
  
  