De Bruijn Graph in Python | Dataford Interview Questions

A simplified sequence-assembly utility for 10x Genomics Cell Ranger needs to represent overlaps between adjacent DNA k-mers. Given a DNA sequence and an integer k, construct its directed de Bruijn graph.

Formal Specification

Implement de_bruijn_graph(sequence, k). The input sequence is a non-empty string containing uppercase DNA bases, and k is an integer. For every substring of length k, create a directed edge from its first k - 1 characters to its last k - 1 characters. Return a dictionary mapping each node to a list of destination nodes.

Include nodes that appear only as destinations. Preserve duplicate edges because repeated k-mers represent repeated observations. Store each node's outgoing destinations in the order their corresponding k-mers occur from left to right in the sequence. Python dictionary insertion order determines the output order of keys.

Constraints

1 <= len(sequence) <= 10^5
2 <= k <= len(sequence)
sequence contains only uppercase DNA bases: A, C, G, and T
Repeated k-mers must produce repeated edges
Adjacency lists must preserve left-to-right occurrence order

Function Signature

def de_bruijn_graph(sequence, k):

Your question is De Bruijn Graph in Python. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Constraints

1 <= len(sequence) <= 10^5
2 <= k <= len(sequence)
sequence contains only uppercase DNA bases: A, C, G, and T
Repeated k-mers must produce repeated edges
Adjacency lists must preserve left-to-right occurrence order

Function Signature

def de_bruijn_graph(sequence, k):

Your question is De Bruijn Graph in Python. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.