Constructing a De Bruijn Graph

Problem

Consider a set S of (k+1)-mers of some unknown DNA string. Let Src denote the set containing all reverse complements of the elements of S. (recall from “Counting Subsets” that sets are not allowed to contain duplicate elements).

The de Bruijn graph Bk of order k corresponding to S∪Src is a digraph defined in the following way:

Nodes of Bk correspond to all k-mers that are present as a substring of a (k+1)-mer from S∪Src.
Edges of Bk are encoded by the (k+1)-mers of S∪Src in the following way: for each (k+1)-mer r in S∪Src, form a directed edge (r[1:k], r[2:k+1]).
Given: A collection of up to 1000 DNA strings of equal length (not exceeding 50 bp) corresponding to a set S of (k+1)-mers.

Return: The adjacency list corresponding to the de Bruijn graph corresponding to S∪Src.