De Bruijn Graph

A de Bruijn graph, defined for an alphabet of a given size and a given string length, has as its vertices every possible string of that length over the alphabet, with a directed edge from one string to another whenever the last symbols of the first string exactly match the first symbols of the second, representing an overlap of one position. It is named after the Dutch mathematician Nicolaas Govert de Bruijn, who studied these graphs in a 1946 paper in connection with constructing de Bruijn sequences, cyclic sequences of symbols in which every possible substring of a given length appears exactly once. Because a Hamiltonian cycle through a de Bruijn graph corresponds exactly to a de Bruijn sequence, and because the graph also has a simpler Eulerian circuit that produces the same result, the construction gives an efficient method for building these sequences. De Bruijn graphs found a major later application in bioinformatics, where they underlie de Bruijn graph based algorithms for assembling a genome's full sequence from many short, overlapping fragments of sequenced DNA.