SCALABLE ALGORITHMS AND SOFTWARE FOR GENOME ASSEMBLY AND HYBRID SCAFFOLDING

Oieswarya Bhowmik

doi:10.7273/000008377

The increasing accuracy and accessibility of long read sequencing technologies, such as PacBio HiFi, have revolutionized genome assembly. However, assembling complex genomes with high contiguity and minimal computational overhead remains a significant challenge. Current state-of-the-art tools struggle with scalability as genome size increases, often requiring weeks to months for mammalian-sized genomes while consuming hundreds of gigabytes of memory. Moreover, existing approaches leave substantial gaps in genome completeness--only 1.5-6.5% of assemblies in public repositories achieve reference quality, creating a backlog of over 2.5 million fragmented draft genomes. This dissertation addresses these challenges through two complementary graph-theoretic approaches: a parallel hybrid scaffolding workflow that upgrades existing draft assemblies using long reads, and a scalable long read assembly framework based on explicit vertex reordering. Our first contribution, Maptcha, is a novel parallel workflow for hybrid genome scaffolding that combines pre-constructed assemblies with newly sequenced long reads. Maptcha employs alignment-free sketch-based mapping to rapidly identify long reads spanning multiple contigs, then constructs a ⟨contig,contig⟩ graph capturing these linkages. We introduce a novel graph-theoretic "wiring" heuristic that iteratively connects contigs by selecting the most credible links based on long read support while avoiding questionable connections in repetitive regions. A batching design partitions the scaffolding problem into independent parallel subproblems, enabling efficient distributed execution while bounding memory consumption. Our second contribution, Tile-X, addresses the scalability of de novo long read assembly through a vertex reordering framework. Rather than implicitly determining read order during assembly, Tile-X explicitly computes read orderings using graphtheoretic techniques to group reads from similar genomic regions, enabling partitioned parallel assembly. We also introduce a novel sparsified ordering heuristic tailored specifically for genome assembly that selects a minimal informative subset of reads covering the genome with reduced redundancy. Experiments demonstrate that Tile-X maintains assembly quality comparable to state-of-the-art long read assemblers while achieving up to 3.5× faster runtime and 3.3× lower memory consumption, with the sparsification approach proving particularly effective for high-coverage datasets. Together, these contributions demonstrate that graph-theoretic approaches coupled with intelligent parallelization strategies can simultaneously improve both assembly quality and computational efficiency. This dissertation provides the genome assembly community with practical, scalable tools capable of generating high-quality, chromosome-scale assemblies for large and complex genomes without requiring a high resource infrastructure. Both frameworks are available as open-source software, enabling broad accessibility for researchers working with diverse organisms and resource constraints. The techniques presented here establish a foundation for making reference-quality genome assembly achievable for the broader scientific community.

SCALABLE ALGORITHMS AND SOFTWARE FOR GENOME ASSEMBLY AND HYBRID SCAFFOLDING

Files and links (1)

Abstract

Metrics

Details