How to make a distinction between the "classical" de Bruijn graph and the one described in NGS papers?

Question

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?

Answer 1

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.

Answer 2

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.

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