Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

De Bruijn graphs: compact non-branching k-mer routes into unitigs

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A de Bruijn graph built from fixed-length k-mers uses each length-(k−1) prefix as an edge source and its length-(k−1) suffix as the destination. The k-mer itself is the directed edge. A unitig follows a maximal path whose internal vertices have exactly one incoming and one outgoing edge. Branches stop extension, preserving alternative routes instead of silently choosing one. This builder deduplicates input k-mers, rejects mixed lengths and k less than two, and retains explicit incoming and outgoing edge lists. After starting paths at branch or endpoint vertices, it processes any unused edges, which covers isolated one-in/one-out cycles. Each returned sequence spells its represented edges by taking the first k-mer and appending the last character of each successor. It does not estimate coverage, resolve repeats, or assemble an original genome.

Operational case

The k-mers ATG, TGA, GAC, ACT, CTG, TGC, and GCA form three displayed unitigs: ATG, TGACTG, and TGCA. Vertex TG branches toward GA and GC, so the compacted paths do not claim one unique continuation across it. The first k-mer of every path supplies the initial two characters; appending a successor's final character spells each later edge once. Duplicate input k-mers are collapsed to one edge. If the task needs multiplicity or read depth, a count field must be added instead of assuming the deduplicated graph retains it. An isolated directed cycle may be represented with an arbitrary sorted starting edge; its rotation is not a canonical biological result.

Working Python program

python
from collections import defaultdict


class KmerRouteIndex:
    def __init__(self, kmers):
        kmers = set(kmers)
        if not kmers or len({len(kmer) for kmer in kmers}) != 1 or len(next(iter(kmers))) < 2:
            raise ValueError("need equal-length k-mers with k at least two")
        self.k = len(next(iter(kmers)))
        outgoing = defaultdict(list)
        incoming = defaultdict(list)
        for kmer in sorted(kmers):
            source, target = kmer[:-1], kmer[1:]
            outgoing[source].append(kmer)
            incoming[target].append(kmer)
        self.vertices = set(outgoing) | set(incoming)
        self.outgoing = dict(outgoing)
        self.incoming = dict(incoming)
        self.edges = kmers

    def unitigs(self):
        used = set()
        paths = []

        def extend(first):
            sequence = first
            used.add(first)
            vertex = first[1:]
            while len(self.incoming.get(vertex, [])) == 1 and len(self.outgoing.get(vertex, [])) == 1:
                successor = self.outgoing[vertex][0]
                if successor in used:
                    break
                sequence += successor[-1]
                used.add(successor)
                vertex = successor[1:]
            return sequence

        for vertex in sorted(self.vertices):
            if len(self.incoming.get(vertex, [])) == 1 and len(self.outgoing.get(vertex, [])) == 1:
                continue
            for edge in self.outgoing.get(vertex, []):
                if edge not in used:
                    paths.append(extend(edge))
        for edge in sorted(self.edges):
            if edge not in used:
                paths.append(extend(edge))
        return paths


if __name__ == "__main__":
    index = KmerRouteIndex(["ATG", "TGA", "GAC", "ACT", "CTG", "TGC", "GCA"])
    print(index.unitigs())
    print(len(index.edges), len(index.vertices))

Output

Output
['ATG', 'TGACTG', 'TGCA']
7 7

Time, space, and tradeoff

Let E be the number of distinct k-mers and V the number of observed prefix/suffix vertices. Building edge lists takes O(Ek) time due to slicing k-character strings and O(Ek + V) Python storage. Sorting k-mers and vertices for stable output adds O(E log E + V log V) comparisons with string costs. The graph walk marks each edge once, but repeated Python string concatenation can make one long output path quadratic in its length; collecting characters and joining once would remove that avoidable copying. A CSR graph is a better frozen general-purpose adjacency layout, while this structure uses overlap semantics specific to equal-length strings.

Common Mistakes

  • Do not extend a unitig through a vertex with two outgoing choices.
  • Do not forget isolated one-in/one-out cycles after endpoint walks.
  • Do not interpret deduplicated edges as read coverage counts.
  • Do not claim that unitig compaction reconstructs one unique source sequence.

Connected lessons

Compare the operation boundary with Double-array tries: static incident-code transitions with BASE and CHECK, Hopscotch hashing: keep each shipment near its home bucket, Invertible Bloom tables: peel differences between replica ID sets, then complete the audit project and decision quiz.

data structures
range-query-structures
Storage details