Python Bioinformatics

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 SSrc 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 SSrc.
• Edges of Bk are encoded by the (k+1)-mers of SSrc in the following way: for each (k+1)-mer r in SSrc, form a directed edge (r[1:k], r[2:k+1]).

Given: A collection of up to 1000 (possibly repeating) 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 SSrc.

Sample Dataset

TGAT CATG TCAT ATGC CATC CATC

Sample Output

(ATC, TCA) (ATG, TGA) (ATG, TGC) (CAT, ATC) (CAT, ATG) (GAT, ATG) (GCA, CAT) (TCA, CAT) (TGA, GAT)