In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple times in a sequence. For a set of symbols the set of vertices is:

:<math>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)\}.</math>

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 (that is, directed edges) is

:<math>E=\{((t_1,t_2,\dots,t_n),(t_2,\dots,t_n,s_j)) : t_i \in S, 1\le i\le n, 1\le j\le m \}.</math>

Although De Bruijn graphs are named after Nicolaas Govert de Bruijn, they were invented independently by both de Bruijn

</references>

  • Tutorial on using De Bruijn Graphs in Bioinformatics by Homolog.us
  • De Bruijn Graph algorithm tutorial by Kurban Intelligence Lab