Optimizing High Performance Distributed Memory Parallel Hash Tables for DNA k-mer Counting
Optimizing High Performance Distributed Memory Parallel Hash Tables for DNA k-mer Counting
复制标题
优化用于 DNA k 聚体计数的高性能分布式内存并行哈希表
DOI：
10.1109/sc.2018.00014
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Aluru
中科院分区：
文献类型：
--
作者：
Tony Pan;Sanchit Misra;S. Aluru
高通量DNA测序是现代基因组学研究的支柱。生物信息学分析中用于许多高通量测序应用的常用操作是DNA序列固定长度子串（称为k-mers）的计数和索引。k-mer计数通常通过散列来完成，而大型数据集的分布式内存k-mer计数算法受内存访问和网络通信的限制。在这项工作中，我们提出了两种优化的分布式并行哈希表技术，它们利用缓存友好算法进行本地哈希，重叠通信和计算以隐藏通信成本，以及专门用于fc-mer和其他短键索引的矢量哈希函数。在4096核的NERSC Cori超级计算机上，我们的实现在11.8秒和5.8秒内完成了对大约1tb人类基因组数据集的索引构建和查询，比之前最先进的分布式内存k-mer计数器分别提高了2.06倍和3.7倍。
High-throughput DNA sequencing is the mainstay of modern genomics research. A common operation used in bioinformatic analysis for many applications of high-throughput sequencing is the counting and indexing of fixed length substrings of DNA sequences called k-mers. Counting k-mers is often accomplished via hashing, and distributed memory k-mer counting algorithms for large datasets are memory access and network communication bound. In this work, we present two optimized distributed parallel hash table techniques that utilize cache friendly algorithms for local hashing, overlapped communication and computation to hide communication costs, and vectorized hash functions that are specialized for fc-mer and other short key indices. On 4096 cores of the NERSC Cori supercomputer, our implementation completed index construction and query on an approximately 1 TB human genome dataset in just 11.8 seconds and 5.8 seconds, demonstrating speedups of 2.06× and 3.7×, respectively, over the previous state-of-the-art distributed memory k-mer counter.
影响因子：
12
作者：
Koepfli KP;Paten B;Genome 10K Community of Scientists;O'Brien SJ
通讯作者：
O'Brien SJ
影响因子：
7
作者：
Salzberg, Steven L.;Phillippy, Adam M.;Yorke, James A.
通讯作者：
Yorke, James A.