text: user57: Why do some assemblers like SOAPdenovo2 or Velvet require an odd-length k-mer size for the construction of de Bruijn graph, while some other assemblers like ABySS are fine with even-length k-mers?
  
  user4327: To expand on the answer above, in case it isn't clear, we show:
  
  Why palindromic sequences must be even in length
  Why palindromic sequences induce self-loops in a de Bruijn graph
  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$:
  
  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:
  
  its left k-1-mer $xA$
  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:
  
  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:
  
  
  $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.
  
  user57: From the manual of Velvet:
  
  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 in biology are defined as reverse complementary sequences. The problem of palindromes is explained in this review:
  
  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.
  
original_text: 57: <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>
   4327: <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.stack.imgur.com/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.stack.imgur.com/jZSpf.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/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.stack.imgur.com/0tkDw.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/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>
   57: <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>
  