14
$\begingroup$

In Computer Science a 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 (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?

$\endgroup$
4
  • $\begingroup$ Basically the condition 1 means that even edge-less vertices should be present in the graph, right? $\endgroup$ – Kamil S Jaron May 19 '17 at 14:30
  • $\begingroup$ I mean, I wonder if any non-bioinformatics implementation of De Bruijn graph actually store them, since they do not carry any useful information. $\endgroup$ – Kamil S Jaron May 19 '17 at 14:37
  • 3
    $\begingroup$ There is one more difference in De Brujin graphs used for genome assembly - edges are weighted. $\endgroup$ – Kamil S Jaron May 19 '17 at 14:57
  • 2
    $\begingroup$ Hi @Slim re. Q1, I believe de Bruijn graphs are connected (one component). You can build them just by providing m and n (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. $\endgroup$ – Leo Martins May 19 '17 at 15:19
7
$\begingroup$

Several papers have made this distinction, and a few indeed use different terms to distinguish between them. For example, Kazaux et al. (2016) 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) 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), where they call it a subgraph of the de Bruijn digraph. Later, in 2002, Błażewicz et al. will refer to it as a de Bruijn induced subgraph. The term de Bruijn subgraph is also formally defined in Quitzau’s thesis (2009). There, and also in the article (Quitzau and Stoye, 2008) 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).

Another term that I found was word graph, described by both Malde et al. (2005) and by Heath and Pati (2007) as a subgraph or as a generalization of a de Bruijn graph. Rødland (2013) 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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – user172818 May 22 '17 at 22:13
  • $\begingroup$ Pevzner did seminal work in using de Bruijn graphs in assembly (pnas.org/content/98/17/9748.full) and alternative splicing (ncbi.nlm.nih.gov/pubmed/12169546) $\endgroup$ – Jeremy Leipzig May 23 '17 at 16:24
4
$\begingroup$

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 is a nice paper on how to construct a pan-genome De Bruijn graph of multiple genomes simultaneously.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Leo Martins May 19 '17 at 12:50
  • $\begingroup$ I am quite sure that all original k-mers are present in some form. $\endgroup$ – holmrenser May 22 '17 at 8:48
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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