<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>

CC BY-SA 4.0
2019-04-23T13:55:04.307Z
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."
bioio
CC BY-SA 4.0
2019-04-24T08:49:23.607Z
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.
Kamil S Jaron
CC BY-SA 4.0
2019-04-24T10:03:10.640Z
@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).
bioio
CC BY-SA 4.0
2019-04-19T00:08:29.877Z
2020-04-24T12:03:22.037Z
2020-06-18T08:30:41.743Z
bioio
<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>

CC BY-SA 3.0
2017-05-19T19:30:42.477Z
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).
Devon Ryan
CC BY-SA 4.0
2017-05-19T18:52:34.737Z
2019-02-28T13:13:44.453Z
2019-02-28T13:13:44.453Z
Kamil S Jaron
<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>

<ngs><assembly><k-mer><de-bruijn-graphs>
Why do some assemblers require an odd-length kmer for the construction of de Bruijn graphs?
# 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**: @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).  

---

