``````

In [1]:

def de_bruijn_ize(st, k):
""" Return a list holding, for each k-mer, its left
k-1-mer and its right k-1-mer in a pair """
edges = []
nodes = set()
for i in range(len(st) - k + 1):
edges.append((st[i:i+k-1], st[i+1:i+k]))
return nodes, edges

``````
``````

In [2]:

nodes, edges = de_bruijn_ize("ACGCGTCG", 3)

``````
``````

In [3]:

nodes

``````
``````

Out[3]:

{'AC', 'CG', 'GC', 'GT', 'TC'}

``````
``````

In [4]:

edges

``````
``````

Out[4]:

[('AC', 'CG'),
('CG', 'GC'),
('GC', 'CG'),
('CG', 'GT'),
('GT', 'TC'),
('TC', 'CG')]

``````
``````

In [5]:

def visualize_de_bruijn(st, k):
""" Visualize a directed multigraph using graphviz """
nodes, edges = de_bruijn_ize(st, k)
dot_str = 'digraph "DeBruijn graph" {\n'
for node in nodes:
dot_str += '  %s [label="%s"] ;\n' % (node, node)
for src, dst in edges:
dot_str += '  %s -> %s ;\n' % (src, dst)
return dot_str + '}\n'

``````
``````

In [6]:

# might have to do this first:
# %install_ext https://raw.github.com/cjdrake/ipython-magic/master/gvmagic.py

``````
``````

In [7]:

%dotstr visualize_de_bruijn("ACGCGTCG", 3)

``````
``````

DeBruijn graph

GC

GC

CG

CG

GC->CG

AC

AC

AC->CG

GT

GT

TC

TC

GT->TC

CG->GC

CG->GT

TC->CG

``````