# Glossary

## de Bruijn graph

The de Bruijn graph is a directed graph used for representing overlapping strings in a collection of k-mers. Given a set $S$ containing DNA strings of length $k+1$, the de Bruijn graph $B$ corresponding to $S \cup S^{\textrm{rc}}$ (i.e., $S$ together with all possible reverse complements of strings in $S$) is defined in the following way:

• 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$.