文章基本信息

标题：Scalable Genome Assembly through Parallel de Bruijn Graph Construction for Multiple k-mers
本地全文：下载
作者：Kanak Mahadik ; Christopher Wright ; Milind Kulkarni 等
期刊名称：Scientific Reports
电子版ISSN：2045-2322
出版年度：2019
卷号：9
期号：1
页码：1-15
DOI：10.1038/s41598-019-51284-9
出版社：Springer Nature
摘要：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).