The de Bruijn graph is a directed graph used for representing overlapping strings in a collection of k-mers.
Given a set

- Create a node of
$B$ for any length$k$ substring of some$(k+1)$ -mer in$S \cup S^{\textrm{rc}}$ . - Do not form multiple nodes corresponding to the same DNA string.
- Create a directed edge of
$B$ connecting node$s$ to node$t$ if there is some$(k+1)$ -mer$u$ in$S \cup S^{\textrm{rc}}$ whose prefix is$s$ and suffix is$t$ . Label the directed edge with the$(k+1)$ -mer$u$ .