MBG

MBG constructs sparse de Bruijn graphs from homopolymer-compressed high-fidelity (HiFi) long reads to enable efficient genome assembly from high-coverage sequencing data.

Key Features:

• Homopolymer Compression (HPC): Compresses input sequences via homopolymer compression to reduce redundancy and improve computational efficiency.
• Syncmer/Minimizer Selection: Selects syncmers (minimizers) from HPC-compressed sequences to represent larger genomic regions sparsely.
• Sparse de Bruijn Graph Construction: Connects selected syncmers with edges when they are adjacent within reads to form a sparse de Bruijn graph.
• Unitig Formation: Unitifies the graph by merging connected components into contiguous unitigs.
• Read Type Optimization: Optimized for PacBio HiFi/CCS reads and reported to also function with Illumina reads.
• High-Coverage Scaling: Designed to operate on high-coverage sequencing datasets.

Scientific Applications:

• Sparse graph construction: Construction of sparse de Bruijn graphs from high-coverage HiFi long-read datasets.
• Human genome assembly: Assembly of a 50× coverage whole human genome from HiFi reads reported in approximately four hours on a single core.
• Bacterial genome assembly: Rapid assembly of bacterial genomes, exemplified by assembling the E. coli genome into a single contig in eight seconds.
• Performance compared to dense graphs: Demonstrated to significantly outperform tools designed for dense de Bruijn graph construction on large-scale datasets.

Methodology:

Input sequences undergo homopolymer compression (HPC); syncmers (minimizers) are selected from HPC-compressed sequences; selected syncmers are connected by edges if adjacent within reads to form a sparse de Bruijn graph; the graph is unitified into unitigs.