Scalable Parallel Algorithms for de novo Assembly of Complex Genomes

De novo whole genome assembly reconstructs genomic sequence from short, overlapping, and potentially erroneous DNA segments and is one of the most important computations in modern genomics. This work presents the first high-quality end-to-end de novo assembler designed for extreme scale analysis, via efficient parallelization of the Meraculous code. In this talk, I will first present distributed-memory parallelization of de Bruijn graph construction and traversal, which is a key component of most de novo genome assemblers. I will also talk about load-balancing techniques for repetitive genomes with highly skewed k-mer distributions. Then, I will briefly talk about merAligner, a highly parallel sequence aligner that implements a seed-and-extend algorithm. Since merAligner employs parallelism in all of its components, especially the seed index construction, it is particularly useful for aligning contigs to reads within the context of de novo genome assembly. Finally, I will mention parallelization of the Meraculous scaffolding modules by leveraging the one-sided communication capabilities of the Unified Parallel C (UPC) while effectively mitigating load imbalance. Large-scale results on a Cray XC30 using grand-challenge genomes demonstrate efficient performance and scalability on thousands of cores. Overall, our pipeline accelerates Meraculous performance by orders of magnitude, creating unprecedented capability for extreme-scale genomic analysis.