PaKman: A Scalable Algorithm for Generating Genomic Contigs on Distributed Memory Machines
PaKman: A Scalable Algorithm for Generating Genomic Contigs on Distributed Memory Machines
复制标题
DOI：
10.1109/tpds.2020.3043241
复制
发表时间：
2021-05
影响因子：
5.3
通讯作者：
Priyanka Ghosh;S. Krishnamoorthy;A. Kalyanaraman
中科院分区：
文献类型：
--
作者：
Priyanka Ghosh;S. Krishnamoorthy;A. Kalyanaraman
基因组从头组装（De novo genome assembly）是生物信息学领域的一个基本问题，其目的是从一个未知基因组中获得大量的DNA片段（reads），并将其组装起来。随着高通量测序技术的出现，数十亿的reads可以在几个小时内产生，这就需要高效的并行组装过程。虽然过去已经提出了多个并行解决方案，但由于与数据移动相关联的固有复杂性以及存储器和I/O操作的不规则访问占用空间，大规模进行大规模组装仍然是一个具有挑战性的问题。在这篇文章中，我们提出了一种新的算法，称为PaKman，来解决在分布式内存并行计算机上进行大规模基因组组装的问题。我们的方法侧重于提高性能，通过结合新的数据结构和算法策略，以减少在组装过程中的通信和I/O足迹。PaKman为全基因组组装流水线中最耗时的两个阶段提供了解决方案，即k-mer计数和重叠群生成。我们的算法的一个关键方面是它的图形数据结构（PaK-Graph），它包括胖节点（或我们称之为“宏节点”），减少了重叠群生成过程中的通信负担。我们提出了一个广泛的性能和定性评估我们的算法在广泛的基因组（不同的大小和物种组），包括比较其他国家的最先进的并行汇编程序。我们的研究结果表明，NERSC科里超级计算机上最多16 K个核心（测试）实现近线性加速的能力;在性能方面优于或媲美其他最先进的分布式内存和共享内存工具，同时提供相当（如果不是更好）的质量;并显着减少解决方案的时间。例如，PaKman能够在16 K核心上在一分钟内为复杂基因组（如人类和面包小麦基因组）生成一组高质量的组装重叠群。此外，PaKman能够在16 K核心上成功处理3.1 TB的模拟数据集，该数据集是迄今为止已知最大的基因组之一-Ambystoma mexicanum（蝾螈）。
De novo genome assembly is a fundamental problem in the field of bioinformatics, that aims to assemble the DNA sequence of an unknown genome from numerous short DNA fragments (aka reads) obtained from it. With the advent of high-throughput sequencing technologies, billions of reads can be generated in a matter of hours, necessitating efficient parallelization of the assembly process. While multiple parallel solutions have been proposed in the past, conducting a large-scale assembly at scale remains a challenging problem because of the inherent complexities associated with data movement, and irregular access footprints of memory and I/O operations. In this article, we present a novel algorithm, called PaKman, to address the problem of performing large-scale genome assemblies on a distributed memory parallel computer. Our approach focuses on improving performance through a combination of novel data structures and algorithmic strategies for reducing the communication and I/O footprint during the assembly process. PaKman presents a solution for the two most time-consuming phases in the full genome assembly pipeline, namely, k-mer counting and contig generation. A key aspect of our algorithm is its graph data structure (PaK-Graph), which comprises fat nodes (or what we call “macro-nodes”) that reduce the communication burden during contig generation. We present an extensive performance and qualitative evaluation of our algorithm across a wide range of genomes (varying in both size and species group), including comparisons to other state-of-the-art parallel assemblers. Our results demonstrate the ability to achieve near-linear speedups on up to 16K cores (tested) on the NERSC Cori supercomputer; perform better than or comparable to other state-of-the-art distributed memory and shared memory tools in terms of performance while delivering comparable (if not better) quality; and reduce time to solution significantly. For instance, PaKman is able to generate a high-quality set of assembled contigs for complex genomes such as the human and bread wheat genomes in under a minute on 16K cores. In addition, PaKman was able to successfully process a 3.1 TB simulated dataset of one of the largest known genomes (to date)-Ambystoma mexicanum (the axolotl), in just over 200 seconds on 16K cores.