Mahadik, K., Wright, C., Kulkarni, M., Bagchi, S., and Chaterji, S. (2019). Scalable Genome Assembly through Parallel de Bruijn Graph Construction for Multiple k-mers. Nature Scientific Reports, https://www.nature.com/articles/s41598-019-51284-9.
Abstract
Remarkable advancements in high-throughput gene sequencing technologies have led
to an exponential growth in the number of sequenced genomes. However, unavailability
of highly parallel and scalable de novo assembly algorithms have hindered biologists
attempting to swiftly assemble high-quality complex genomes. Popular de Bruijn graph
assemblers, such as IDBA-UD, generate high-quality assemblies by iterating over a
set of k-values used in the construction of de Bruijn graphs (DBG). However, this
process of sequentially iterating from small to large k-values slows down the process
of assembly. In this paper, we propose ScalaDBG, which metamorphoses this sequential
process, building DBGs for each distinct k-value in parallel. We develop an innovative
mechanism to “patch” a higher k-valued graph with contigs generated from a lower
k-valued graph. Moreover, ScalaDBG leverages multi-level parallelism, by both scaling
up on all cores of a node, and scaling out to multiple nodes simultaneously. We
demonstrate that ScalaDBG completes assembling the genome faster than IDBA-UD, but
with similar accuracy on a variety of datasets (6.8X faster for one of the most
complex genome in our dataset).