35
$\begingroup$

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?

$\endgroup$

2 Answers 2

31
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ Lest someone in the future misinterpret this, it should be noted that palindrome in this context has a slightly more specific meaning than it normally would in English. $\endgroup$
    – Devon Ryan
    May 19, 2017 at 19:30
14
$\begingroup$

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

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

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

  • $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.

$\endgroup$
3
  • $\begingroup$ 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." $\endgroup$
    – ukemi
    Apr 23, 2019 at 13:55
  • $\begingroup$ 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. $\endgroup$ Apr 24, 2019 at 8:49
  • $\begingroup$ @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). $\endgroup$
    – ukemi
    Apr 24, 2019 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.