De Bruijn Graphs: Construction from K-mer Composition

Let’s explore how we can make de Bruijn graphs without gluing, with the help of k-mer composition.

We'll cover the following

Constructing the de Bruijn graph by gluing identically labeled nodes will help us later when we generalize the notion of de Bruijn graph for other applications. We’ll now describe another useful way to construct de Bruijn graphs without gluing.

Construction without gluing

Given a collection of k-mers Patterns, the nodes of DeBruijnk_{k} (Patterns) are simply all unique (k − 1)-mers occurring as a prefix or suffix of 3-mers in Patterns. For example, say we’re given the following collection of 3-mers:

Get hands-on with 1200+ tech skills courses.