HelixForge
De Novo Genome Assembly
Built a genome assembly system that reconstructs DNA sequences from raw sequencing reads using De Bruijn Graphs, Eulerian traversal, shortest-path optimization, and advanced string algorithms.
System Architecture
Genome-assembly architecture derived from the HelixForge repository.
FASTQ sequence intake
Sequencing reads enter the assembly workflow with format and quality checks.
Count + filter
K-mer frequency analysis removes weak evidence and prepares graph construction.
De Bruijn assembly graph
Nodes and 75,145 graph edges encode overlaps for the core assembly algorithms.
Traverse + simplify
Ten core algorithms resolve paths, simplify graph structure, and produce contigs.
Assembly evaluation
N50, contig statistics, graph views, and diagnostics expose output quality.
Graph-backed genome assembly with a documented 1,143 bp N50.
Project Overview
HelixForge is a genome assembly system that reconstructs DNA sequences from raw FASTQ sequencing reads using graph-based and string-processing algorithms. The project was developed in C++ and combines multiple advanced Design and Analysis of Algorithms concepts into a complete bioinformatics pipeline.
The system begins by processing sequencing reads through a two-pass exact frequency counter and rolling hash mechanism to identify solid k-mers while filtering sequencing noise. These k-mers are then used to construct a De Bruijn Graph, where nodes represent k-1 mers and edges represent valid genomic transitions.
To generate assemblies, HelixForge evaluates three complementary strategies: Hierholzer's Eulerian Path algorithm for maximum edge coverage, Dijkstra's coverage-weighted shortest path for high-confidence assembly, and multi-start greedy traversal for fragmented graph structures.
Beyond assembly, HelixForge performs dynamic-programming-based error correction and implements a string analytics pipeline using Suffix Arrays and Kasai's LCP algorithm to identify repeat regions within assembled genomes.
The project also includes a Streamlit-based frontend and an interactive 3D De Bruijn Graph visualizer, enabling users to inspect graph structures, assembly outputs, and repeat-region analysis through an intuitive interface.
Problem
Genome assembly requires reconstructing long DNA sequences from noisy short reads while preserving graph structure, repeats, and high-confidence transitions.
Solution
Implemented a C++17 FASTQ-to-FASTA assembly pipeline using De Bruijn Graph construction, Eulerian traversal, shortest-path optimization, greedy assembly, and string analytics.