De Bruijn graph: Difference between revisions

In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mⁿ vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence. If we have the set of m symbols ${\displaystyle S:=\{s_{1},\dots ,s_{m}\}}$ then the set of vertices is:

${\displaystyle V=S^{n}=\{(s_{1},\dots ,s_{1},s_{1}),(s_{1},\dots ,s_{1},s_{2}),\dots ,(s_{1},\dots ,s_{1},s_{m}),(s_{1},\dots ,s_{2},s_{1}),\dots ,(s_{m},\dots ,s_{m},s_{m})\}.}$

If one of the vertices can be expressed as another vertex by shifting all its symbols by one place to the left and adding a new symbol at the end of this vertex, then the latter has a directed edge to the former vertex. Thus the set of arcs (aka directed edges) is

${\displaystyle E=\{((v_{1},v_{2},\dots ,v_{n}),(v_{2},\dots ,v_{n},s_{i})):i=1,\dots ,m\}.}$

Although De Bruijn graphs are named after Nicolaas Govert de Bruijn, they were discovered independently by both De Bruijn^[1] and I. J. Good.^[2] Much earlier, Camille Flye Sainte-Marie^[3] implicitly used their properties.

Properties

• If ${\displaystyle n=1}$ then the condition for any two vertices forming an edge holds vacuously, and hence all the vertices are connected forming a total of ${\displaystyle m^{2}}$ edges.
• Each vertex has exactly ${\displaystyle m}$ incoming and ${\displaystyle m}$ outgoing edges.
• Each ${\displaystyle n}$-dimensional De Bruijn graph is the line digraph of the ${\displaystyle (n-1)}$-dimensional De Bruijn graph with the same set of symbols.^[4]
• Each De Bruijn graph is
  Hamiltonian. The Euler cycles and Hamiltonian cycles of these graphs (equivalent to each other via the line graph construction) are De Bruijn sequences
  .

The line graph construction of the three smallest binary De Bruijn graphs is depicted below. As can be seen in the illustration, each vertex of the ${\displaystyle n}$-dimensional De Bruijn graph corresponds to an edge of the ${\displaystyle (n-1)}$-dimensional De Bruijn graph, and each edge in the ${\displaystyle n}$-dimensional De Bruijn graph corresponds to a two-edge path in the ${\displaystyle (n-1)}$-dimensional De Bruijn graph.

Dynamical systems

Binary De Bruijn graphs can be drawn (below, left) in such a way that they resemble objects from the theory of

This analogy can be made rigorous: the n-dimensional m-symbol De Bruijn graph is a model of the

${\displaystyle x\mapsto mx\ {\bmod {\ }}1}$

The Bernoulli map (also called the

Uses

• Some grid network topologies are De Bruijn graphs.
• The distributed hash table protocol Koorde uses a De Bruijn graph.
• In bioinformatics, De Bruijn graphs are used for de novo assembly of sequencing reads into a genome.^[6][7][8][9]

See also

• De Bruijn sequence
• De Bruijn torus
• Hamming graph
• Kautz graph

References

• Weisstein, Eric W. "De Bruijn Graph". MathWorld.
• Tutorial on using De Bruijn Graphs in Bioinformatics by Homolog.us