De Bruijn Genome Assembler
Systems / Algorithms | 2022
Assembly Result: Genome length: 5,396 bases (phiX174 ref: 5,386 → 99.9% coverage) Input reads: 33,609 Graph vertices: 111,283 Graph edges: 111,624 Tips removed: 18 Bubbles resolved: 2 Assembly time: 1,812 ms
Reassemble a genome from thirty-three thousand fragments.
End-to-end build: Java CLI assembler, Spring Boot REST API, React + Vite frontend, Docker packaging, deployed split-stack to Render (backend) + Vercel (frontend). Implements de Bruijn graph construction, Hierholzer's Eulerian cycle, and error correction via tip removal + bubble resolution — all from the bioinformatics primary literature, no library shortcuts.
One assembler jar drives a CLI ( java -jar genome-toolkit-1.0.0.jar assemble ...) and the REST endpoint inside the Spring Boot service. The React frontend is a thin drag-and-drop client over the same API. Two assembly modes ship — the de Bruijn pipeline as primary, and a greedy maximum suffix-prefix overlap assembler as a baseline.
Lives at debruijn-genome-assembler.vercel.app. Validates on the phi X174 bacteriophage reference — the canonical small-bacteriophage genome for sequencing tools — reconstructing 5,396 bp from 33,609 reads in under two seconds.
A de Bruijn assembler that finishes in under two seconds.
On the phi X174 benchmark (5,386 bp reference, 33,609 reads) the pipeline reconstructs 5,396 bases at 99.9% coverage, traverses a graph of ~111K edges via an iterative Hierholzer's implementation, and finishes in ~2 seconds on a laptop. Tip removal prunes 18 dead-end branches; bubble resolution picks the higher-coverage path on 2 competing parallels.
SPAdes and Velvet are referenced for verification, not imported.assemble) and a greedy overlap baseline (overlap). The overlap mode exists so the graph-based mode has something to be compared against.Genome assembly is graph algorithms with a dictionary.
Modern sequencers don't produce genomes — they produce millions of short reads, each 100–300 bp, that have to be stitched back into the original sequence. The classic computer-science answer is the de Bruijn graph: every k-mer becomes a vertex, every (k+1)-mer becomes an edge, and an Eulerian traversal of the graph reconstructs the source. Production tools like SPAdes and Velvet are de Bruijn at their core, with a couple of decades of engineering on top of the basic structure.
“How to apply de Bruijn graphs to genome assembly — the canonical reference for the algorithmic approach this project implements.”
“Construct an Eulerian circuit in a graph by depth-first edge traversal with backtracking on dead ends — used in iterative form here for memory safety on the 111K-edge graph.”
“State-of-the-art short-read assemblers use de Bruijn graphs with error correction (tip removal + bubble resolution) and multi-k assembly.”
“First DNA-based genome ever sequenced — 5,386 bp. Still the canonical small benchmark for any new assembler.”
A de Bruijn assembler from the paper, not a wrapper.
Build the graph, walk the cycle, clean the noise.
Greedy overlap baseline.
Started with the simpler algorithm — pairwise maximum suffix-prefix overlap merging. Works on short read sets and is easy to verify by hand, but scales O(n²) on the number of reads. Kept it in the jar under the overlap subcommand as the comparison baseline.
De Bruijn graph + recursive Hierholzer.
First de Bruijn implementation. K-mer extraction, vertex / edge construction, and a textbook recursive Hierholzer's traversal. Assembled correctly on toy inputs (~1K edges) and promptly stack-overflowed at full phi X174 scale (~111K edges). The algorithm was right; the implementation was wrong.
Iterative Hierholzer + error correction.
Rewrote the traversal as an explicit-stack iterative implementation. Added tip removal (dead-end branches shorter than a configurable depth threshold) and bubble resolution (parallel paths between the same two vertices, resolved by coverage comparison). Now finishes phi X174 in ~2 seconds at 99.9% coverage, prunes 18 tips, resolves 2 bubbles.
phi X174 is a circular genome — the assembled string starts and ends with the same k-1 prefix because the Eulerian cycle closes on itself. The first version of the output left those duplicated bases in place and reported 5,416 bp instead of 5,396. Fix: detect the overlap window between the head and tail of the assembled string and trim it, controllable via --no-trim for non-circular references.
Seven stages, one Eulerian walk.
The de Bruijn pipeline is seven deterministic stages — every stage consumes a typed input from the previous one and produces a typed output for the next. No hidden mutation, no global state. Same code powers the CLI and the REST endpoint.
Deque<Vertex> stack = new ArrayDeque<>();
List<Edge> trail = new ArrayList<>();
BitSet used = new BitSet(edges.size());
stack.push(startVertex);
while (!stack.isEmpty()) {
Vertex v = stack.peek();
Edge next = graph.unusedOutgoing(v, used);
if (next == null) { // dead-end → backtrack
trail.add(graph.incoming(v));
stack.pop();
} else { // walk forward
used.set(next.id());
stack.push(next.dest());
}
}
// trail is the Eulerian circuit in reverse
Collections.reverse(trail);# Primary mode genome-toolkit assemble <reads-file> [options] -k <size> k-mer size (default 20) -o <file> write assembled genome to file --no-trim disable circular trim --no-tips disable tip removal --stats print assembly statistics # Baseline mode genome-toolkit overlap <reads-file> # greedy maximum suffix-prefix overlap merging # O(n²) on reads — for small-set comparison only # Inputs reads.txt one read per line ref.fasta FASTA — sliding-window simulated reads
A drag-and-drop UI in front of the same assembler.
Two surfaces, one engine. The CLI is the truth-teller — every flag, every stat, full reproducibility. The web UI at debruijn-genome-assembler.vercel.app wraps the same jar behind a Spring Boot REST endpoint, accepts file drops, and renders the same assembly result + downloadable genome.
