<p>In addition to the regular De Bruijn graph as depicted on the wikipedia, some implementations in bioinformatics feature additional processing. I guess the main reason figure 1 in the paper you linked (concerning the Velvet genome assembler) is slightly different is that a node represents <em>a series of overlapping k-mers</em>. In order to visualize this as a more classic De Bruin graph you would have to connect the k-mers depicted <em>above</em> the nodes. The caption next to figure one describes the processing quite clearly.</p>

<p>As per your last question: I don't think there is a 'Bioinformatic interpretation of a De Bruijn graph'. There are different implementations, which all have there specifics. Thus it would be best to refer to the actual implementation.</p>

<p>As an example: <a href="https://www.ncbi.nlm.nih.gov/pubmed/27587666" rel="nofollow noreferrer">this</a> is a nice paper on how to construct a pan-genome De Bruijn graph of multiple genomes simultaneously.  </p>

CC BY-SA 3.0
2017-05-19T12:50:52.030Z
But an "implementation" of a de Bruijn graph that doesn't include all k-mers is not a de Bruijn graph (in the original sense) any more, right? If the implementation doesn't satisfy condition (1) above, I wonder if there is another name (or a qualifier) being used.
Leo Martins
CC BY-SA 3.0
2017-05-22T08:48:36.097Z
I am quite sure that all original k-mers are present in some form.
holmrenser
CC BY-SA 3.0
2017-05-19T11:07:00.467Z
2017-05-19T11:07:00.467Z
holmrenser
<p>Let's first assume DNA only has one strand. An assembly de Bruijn graph is a subgraph of a complete de Bruijn graph. It contains a vertex u if u is a k-mer in reads; it contains an edge u->v, if u and v are adjacent k-mers on a read. Alternatively, we note that an edge u->v is represented by a (k+1)-mer. An assembly de Bruijn graph can be considered a subgraph edge induced from all (k+1)-mers in reads – in fact, some assemblers take the list of (k+1)-mer as a succinct representation of de Bruijn graphs.</p>

<p>DNA has two strands. We just need to induce an assembly de Bruijn graph from all (k+1)-mers and their reverse complement. It is still a subgraph of a complete de Bruijn graph.</p>

<p>Because an assembly de Bruijn graph is just a subgraph. It is not necessary to give it a new name.</p>

<p>PS: I deleted my old answer as that was not what you are asking for based on your comments. I was confused by your mentioning velvet. Velvet uses an equivalent but uncommon representation of de Bruijn graphs, which complicates your question.</p>

CC BY-SA 3.0
2017-05-19T14:14:34.317Z
2017-05-19T14:14:34.317Z
user172818
<p>Several papers have made this distinction, and a few indeed use different terms to distinguish between them. For example, <a href="http://www.sciencedirect.com/science/article/pii/S0022000016300502" rel="noreferrer">Kazaux et al. (2016)</a> acknowledge that:</p>

<blockquote>
  <p>These constraints favour the use of a version of the de Bruijn Graph (dBG) dedicated to genome assembly – a version which differs from the combinatorial structure invented by N.G. de Bruijn.</p>
</blockquote>

<p><a href="https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-11-21" rel="noreferrer">Kingsford et al. (2010)</a> also recognise the distinction:</p>

<blockquote>
  <p>Note that this definition of a de Bruijn graph differs from the traditional definition described in the mathematical literature in the 1940s that requires the graph to contain all length-k strings that can be formed from an alphabet (rather than just those strings present in the genome). </p>
</blockquote>

<p>The oldest reference I found for a specific term to refer to the assembly-related structure is <a href="http://online.liebertpub.com/doi/abs/10.1089/cmb.1995.2.333" rel="noreferrer">Skiena and Sundaram (1995)</a>, where they call it a <strong>subgraph of the de Bruijn digraph</strong>. Later, in 2002, <a href="http://www.sciencedirect.com/science/article/pii/S0012365X01001339" rel="noreferrer">Błażewicz et al.</a> will refer to it as a <strong>de Bruijn induced subgraph</strong>.  The term <strong>de Bruijn subgraph</strong> is also formally defined in <a href="https://pub.uni-bielefeld.de/publication/2302499" rel="noreferrer">Quitzau’s thesis (2009)</a>. There, and also in the article (<a href="http://link.springer.com/chapter/10.1007/978-3-540-87361-7_29" rel="noreferrer">Quitzau and Stoye, 2008)</a> the authors describe the <strong>sequence graph</strong> as a modification of the sparse de Bruijn subgraph (commonly used in assembly problems), where non-branching paths are replaced by a single vertex. The term <strong>sparse de Bruijn graph</strong> is also used by <a href="https://arxiv.org/abs/1306.4353" rel="noreferrer">Chauve et al. (2013)</a>.</p>

<p>Another term that I found was <strong>word graph</strong>, described by both <a href="https://academic.oup.com/bioinformatics/article/21/8/1371/249821/A-graph-based-algorithm-for-generating-EST" rel="noreferrer">Malde et al. (2005)</a> and by <a href="http://link.springer.com/chapter/10.1007/978-3-540-72031-7_29" rel="noreferrer">Heath and Pati (2007)</a> as a <em>subgraph</em> or as a <em>generalization</em> of a de Bruijn graph. <a href="http://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-14-313" rel="noreferrer">Rødland (2013)</a> summarises some of the terms used for this data structure:</p>

<blockquote>
  <p>The data structure is best understood in terms of the de Bruijn subgraph representation of S[k]. (...) Some authors may refer to this as a word graph, or even just a de Bruijn graph.</p>
</blockquote>

<p>Although we can recognise that the distinction is not very relevant, the question is asking specifically for the situation where one wants to make such a distinction. </p>

CC BY-SA 3.0
2017-05-22T22:13:10.267Z
As many papers and myself said, assembly de Bruijn graph is just a subgraph of the full de Bruijn graph. Anyone saying differently fails to acknowledge this simple relationship. "Sequence graph" is too general and used in other context (e.g. sequence assembly graph). "Sparse de Bruijn graph" is more appropriate for a graph constructed by skipping some k-mers in reads (e.g. in sparse assembler). Directed acyclic word graph (DAWG) is a pre-existing concept, at least dated back to the 80's, which makes "word graph" ambiguous, too. People should stop inventing new names for a subgraph.
user172818
CC BY-SA 3.0
2017-05-23T16:24:22.707Z
Pevzner did seminal work in using de Bruijn graphs in assembly (http://www.pnas.org/content/98/17/9748.full) and alternative splicing (https://www.ncbi.nlm.nih.gov/pubmed/12169546)
Jeremy Leipzig
CC BY-SA 3.0
2017-05-22T20:33:56.417Z
2017-05-22T20:33:56.417Z
Leo Martins
<p>In Computer Science a <a href="https://en.wikipedia.org/wiki/De_Bruijn_graph" rel="noreferrer">De Bruijn graph</a> has (1) <code>m^n</code> vertices representing all possible  sequences of length <code>n</code> over <code>m</code> symbols, and (2) directed edges connecting nodes that differ by a shift of <code>n-1</code> elements (the successor having the new element at the right).</p>

<p>However in Bioinformatics while condition (2) is preserved, what is called a De Bruijn graph <a href="http://www.homolog.us/Tutorials/index.php?p=2.1&amp;s=1" rel="noreferrer">doesn't seem to respect condition</a> (1). In some cases the graph doesn't look anything like a de Bruijn graph at all (e.g. <a href="http://genome.cshlp.org/content/18/5/821.full" rel="noreferrer">http://genome.cshlp.org/content/18/5/821.full</a>).     </p>

<p>So my question is, if I want to make it explicit that I am using the Bioinformatics interpretation of a de Bruijn graph, is there a term for it? Something like "simplified de Bruijn graph", "projection of a de Bruijn graph", or "graph of neighbouring k-mers"? Are there any papers making this distinction, or did I get it all wrong?</p>

CC BY-SA 3.0
2017-05-19T14:30:44.100Z
Basically the condition 1 means that even edge-less vertices should be present in the graph, right?
Kamil S Jaron
CC BY-SA 3.0
2017-05-19T14:37:25.637Z
I mean, I wonder if any non-bioinformatics implementation of De Bruijn graph actually store them, since they do not carry any useful information.
Kamil S Jaron
CC BY-SA 3.0
2017-05-19T14:57:29.463Z
There is one more difference in De Brujin graphs used for genome assembly - edges are weighted.
Kamil S Jaron
CC BY-SA 3.0
2017-05-19T15:19:57.403Z
Hi @Slim re. Q1, I believe de Bruijn graphs are connected (one component). You can build them just by providing `m` and `n` (http://mathworld.wolfram.com/deBruijnGraph.html).  Q2: yes, implementations don't need all nodes; de Bruijn graph is an abstract entity, a combinatorial structure, like a "complete graph".  But if my very important graph miss some edges (b/c useless) I can't call it "complete". It doesn't make it less important BTW! Q3: that's true! Thanks for editing the question.
Leo Martins
<ngs><assembly><k-mer><de-bruijn-graphs>
How to make a distinction between the "classical" de Bruijn graph and the one described in NGS papers?
# How to make a distinction between the "classical" de Bruijn graph and the one described in NGS papers?

(Asked by: username_0 on 2017-05-19)

In Computer Science a [De Bruijn graph](https://en.wikipedia.org/wiki/De_Bruijn_graph) has (1) `m^n` vertices representing all possible sequences of length `n` over `m` symbols, and (2) directed edges connecting nodes that differ by a shift of `n-1` elements (the successor having the new element at the right).

However in Bioinformatics while condition (2) is preserved, what is called a De Bruijn graph [doesn't seem to respect condition](http://www.homolog.us/Tutorials/index.php?p=2.1&s=1) (1). In some cases the graph doesn't look anything like a de Bruijn graph at all (e.g. <http://genome.cshlp.org/content/18/5/821.full>).

So my question is, if I want to make it explicit that I am using the Bioinformatics interpretation of a de Bruijn graph, is there a term for it? Something like "simplified de Bruijn graph", "projection of a de Bruijn graph", or "graph of neighbouring k-mers"? Are there any papers making this distinction, or did I get it all wrong?

**Tags:** ngs, assembly, k-mer, de-bruijn-graphs
> **Comments:**
> **username_1**: Basically the condition 1 means that even edge-less vertices should be present in the graph, right?  
> **username_1**: I mean, I wonder if any non-bioinformatics implementation of De Bruijn graph actually store them, since they do not carry any useful information.  
> **username_1**: There is one more difference in De Brujin graphs used for genome assembly - edges are weighted.  
> **username_0**: Hi @Slim re. Q1, I believe de Bruijn graphs are connected (one component). You can build them just by providing `m` and `n` (http://mathworld.wolfram.com/deBruijnGraph.html).  Q2: yes, implementations don't need all nodes; de Bruijn graph is an abstract entity, a combinatorial structure, like a "complete graph".  But if my very important graph miss some edges (b/c useless) I can't call it "complete". It doesn't make it less important BTW! Q3: that's true! Thanks for editing the question.  

---

## 3 answers

### Answer by username_0 on 2017-05-22. Score: 7

Several papers have made this distinction, and a few indeed use different terms to distinguish between them. For example, [Kazaux et al. (2016)](http://www.sciencedirect.com/science/article/pii/S0022000016300502) acknowledge that:

> These constraints favour the use of a version of the de Bruijn Graph (dBG) dedicated to genome assembly – a version which differs from the combinatorial structure invented by N.G. de Bruijn.

[Kingsford et al. (2010)](https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-11-21) also recognise the distinction:

> Note that this definition of a de Bruijn graph differs from the traditional definition described in the mathematical literature in the 1940s that requires the graph to contain all length-k strings that can be formed from an alphabet (rather than just those strings present in the genome).

The oldest reference I found for a specific term to refer to the assembly-related structure is [Skiena and Sundaram (1995)](http://online.liebertpub.com/doi/abs/10.1089/cmb.1995.2.333), where they call it a **subgraph of the de Bruijn digraph**. Later, in 2002, [Błażewicz et al.](http://www.sciencedirect.com/science/article/pii/S0012365X01001339) will refer to it as a **de Bruijn induced subgraph**. The term **de Bruijn subgraph** is also formally defined in [Quitzau’s thesis (2009)](https://pub.uni-bielefeld.de/publication/2302499). There, and also in the article ([Quitzau and Stoye, 2008)](http://link.springer.com/chapter/10.1007/978-3-540-87361-7_29) the authors describe the **sequence graph** as a modification of the sparse de Bruijn subgraph (commonly used in assembly problems), where non-branching paths are replaced by a single vertex. The term **sparse de Bruijn graph** is also used by [Chauve et al. (2013)](https://arxiv.org/abs/1306.4353).

Another term that I found was **word graph**, described by both [Malde et al. (2005)](https://academic.oup.com/bioinformatics/article/21/8/1371/249821/A-graph-based-algorithm-for-generating-EST) and by [Heath and Pati (2007)](http://link.springer.com/chapter/10.1007/978-3-540-72031-7_29) as a *subgraph* or as a *generalization* of a de Bruijn graph. [Rødland (2013)](http://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-14-313) summarises some of the terms used for this data structure:

> The data structure is best understood in terms of the de Bruijn subgraph representation of S[k]. (...) Some authors may refer to this as a word graph, or even just a de Bruijn graph.

Although we can recognise that the distinction is not very relevant, the question is asking specifically for the situation where one wants to make such a distinction.

> **Comments:**
> **username_3**: As many papers and myself said, assembly de Bruijn graph is just a subgraph of the full de Bruijn graph. Anyone saying differently fails to acknowledge this simple relationship. "Sequence graph" is too general and used in other context (e.g. sequence assembly graph). "Sparse de Bruijn graph" is more appropriate for a graph constructed by skipping some k-mers in reads (e.g. in sparse assembler). Directed acyclic word graph (DAWG) is a pre-existing concept, at least dated back to the 80's, which makes "word graph" ambiguous, too. People should stop inventing new names for a subgraph.  
> **username_4**: Pevzner did seminal work in using de Bruijn graphs in assembly (http://www.pnas.org/content/98/17/9748.full) and alternative splicing (https://www.ncbi.nlm.nih.gov/pubmed/12169546)  

---

### Answer by username_2 on 2017-05-19. Score: 4

In addition to the regular De Bruijn graph as depicted on the wikipedia, some implementations in bioinformatics feature additional processing. I guess the main reason figure 1 in the paper you linked (concerning the Velvet genome assembler) is slightly different is that a node represents *a series of overlapping k-mers*. In order to visualize this as a more classic De Bruin graph you would have to connect the k-mers depicted *above* the nodes. The caption next to figure one describes the processing quite clearly.

As per your last question: I don't think there is a 'Bioinformatic interpretation of a De Bruijn graph'. There are different implementations, which all have there specifics. Thus it would be best to refer to the actual implementation.

As an example: [this](https://www.ncbi.nlm.nih.gov/pubmed/27587666) is a nice paper on how to construct a pan-genome De Bruijn graph of multiple genomes simultaneously.

> **Comments:**
> **username_0**: But an "implementation" of a de Bruijn graph that doesn't include all k-mers is not a de Bruijn graph (in the original sense) any more, right? If the implementation doesn't satisfy condition (1) above, I wonder if there is another name (or a qualifier) being used.  
> **username_2**: I am quite sure that all original k-mers are present in some form.  

---

### Answer by username_3 on 2017-05-19. Score: 3

Let's first assume DNA only has one strand. An assembly de Bruijn graph is a subgraph of a complete de Bruijn graph. It contains a vertex u if u is a k-mer in reads; it contains an edge u->v, if u and v are adjacent k-mers on a read. Alternatively, we note that an edge u->v is represented by a (k+1)-mer. An assembly de Bruijn graph can be considered a subgraph edge induced from all (k+1)-mers in reads – in fact, some assemblers take the list of (k+1)-mer as a succinct representation of de Bruijn graphs.

DNA has two strands. We just need to induce an assembly de Bruijn graph from all (k+1)-mers and their reverse complement. It is still a subgraph of a complete de Bruijn graph.

Because an assembly de Bruijn graph is just a subgraph. It is not necessary to give it a new name.

PS: I deleted my old answer as that was not what you are asking for based on your comments. I was confused by your mentioning velvet. Velvet uses an equivalent but uncommon representation of de Bruijn graphs, which complicates your question.


---

