Girish Mahajan (Editor)

De Bruijn graph

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
De Bruijn graph

In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn 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 S := { s 1 , … , s m } then the set of vertices is:

Contents

V = S n = { ( s 1 , … , s 1 , s 1 ) , ( s 1 , … , s 1 , s 2 ) , … , ( s 1 , … , s 1 , s m ) , ( s 1 , … , s 2 , s 1 ) , … , ( s m , … , 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

E = { ( ( v 1 , v 2 , … , v n ) , ( v 2 , … , v n , s i ) ) : i = 1 , … , m } .

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

Properties

  • If 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 m 2 edges.
  • Each vertex has exactly m incoming and m outgoing edges.
  • Each n -dimensional De Bruijn graph is the line digraph of the ( n − 1 ) -dimensional De Bruijn graph with the same set of symbols.
  • Each De Bruijn graph is Eulerian and 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 n -dimensional De Bruijn graph corresponds to an edge of the ( n − 1 ) -dimensional De Bruijn graph, and each edge in the n -dimensional De Bruijn graph corresponds to a two-edge path in the ( 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 dynamical systems, such as the Lorenz attractor (below, right):

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

    x ↦ m x   mod   1

    The Bernoulli map (also called the 2x mod 1 map for m = 2) is an ergodic dynamical system, which can be understood to be a single shift of a m-adic number. The trajectories of this dynamical system correspond to walks in the De Bruijn graph, where the correspondence is given by mapping each real x in the interval [0,1) to the vertex corresponding to the first n digits in the base-m representation of x. Equivalently, walks in the De Bruijn graph correspond to trajectories in a one-sided subshift of finite type.

    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 (short) read sequences into a genome.

    • References

    De Bruijn graph Wikipedia
    (Text) CC BY-SA


    Similar Topics