de Bruijn graph theory

Recently, de Bruijn graph theory has widely used in the filed of genome assembly.

Expecially, Velvet assembler is based on this graph theory.

The goal of De Bruijn graph is to make superstring through overlapping k - 1 suffix sequence.

So this concept can well match with assembly of short reads of a genome.

de Bruijn graph sample (cited from Wikipedia)

How can de Bruijn graph make a superstring?

Because de Bruijn graph is bidirectional graph, about some input information, it can make superstring as output through traveling every edges or node.

de Bruijn graph can be represented as one of between Hamiltonian cycle or Eulerian cycle.