PUNAS: A Parallel Ungapped-Alignment-Featured Seed Verification Algorithm for Next-Generation Sequencing Read Alignment
PUNAS: A Parallel Ungapped-Alignment-Featured Seed Verification Algorithm for Next-Generation Sequencing Read Alignment
复制标题
PUNAS：用于下一代测序读取比对的并行无间隙比对种子验证算法
DOI：
10.1109/ipdps.2017.35
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
B. Schmidt
中科院分区：
文献类型：
--
作者：
Yuandong Chan;Kai Xu;Haidong Lan;Weiguo Liu;Yongchao Liu;B. Schmidt
新一代测序技术的进展对医学和基因组研究产生了重大影响。这项技术现在可以在一次运行中产生数十亿个短DNA片段（读取）。几乎每个测序管道使用的最苛刻的计算问题之一是短读比对；即确定每个片段在原始基因组中的起源。目前的大多数解决方案都是基于种子-扩展方法，首先确定有希望的候选区域（种子），然后扩展，以验证在每个种子附近是否确实存在完整的高分序列。种子验证是许多最先进的对准器的主要瓶颈，因此找到快速解决方案非常重要。我们提出了一种并行的unapped -alignment-feature seed verification （PUNAS）算法，这是一种快速过滤器，可以有效地去除大多数假阳性种子，从而显着加快短读比对过程。PUNAS基于位并行性，并利用现代微处理器的SIMD矢量单元。我们的实现采用矢量化和规模化方法，支持多核cpu和多核骑士登陆（KNL）的Xeon Phi处理器。性能评估表明，PUNAS比Smith-Waterman算法的种子验证快3个数量级，比Myers位向量算法的带状版本的种子验证快1个数量级。与基于SSE、AVX2和AVX-512的CPU/KNL上的移位汉明距离过滤器相比，使用单个线程可以实现最高7.3、27.1和11.6的加速。我们的框架的速度进一步几乎与核心数量成线性关系。PUNAS是开源软件，可在https://github.com/Xu-Kai/PUNASfilter上获得。
The progress of next-generation sequencing has a major impact on medical and genomic research. This technology can now produce billions of short DNA fragments (reads) in a single run. One of the most demanding computational problems used by almost every sequencing pipeline is short-read alignment; i.e. determining where each fragment originated from in the original genome. Most current solutions are based on a seed-and-extend approach, where promising candidate regions (seeds) are first identified and subsequently extended in order to verify whether a full high-scoring alignment actually exists in the vicinity of each seed. Seed verification is the main bottleneck in many state-of-the-art aligners and thus finding fast solutions is of high importance. We present a parallel ungapped-alignment-featured seed verification (PUNAS) algorithm, a fast filter for effectively removing the majority of false positive seeds, thus significantly accelerating the short-read alignment process. PUNAS is based on bit-parallelism and takes advantage of SIMD vector units of modern microprocessors. Our implementation employs a vectorize-and-scale approach supporting multi-core CPUs and many-core Knights Landing (KNL)-based Xeon Phi processors. Performance evaluation reveals that PUNAS is over three orders-of-magnitude faster than seed verification with the Smith-Waterman algorithm and around one order-of-magnitude faster than seed verification with the banded version of Myers bit-vector algorithm. Using a single thread it achieves a speedup of up to 7.3, 27.1, and 11.6 compared to the shifted Hamming distance filter on a SSE, AVX2, and AVX-512 based CPU/KNL, respectively. The speed of our framework further scales almost linearly with the number of cores. PUNAS is open-source software available at https://github.com/Xu-Kai/PUNASfilter.
影响因子：
9.8
作者：
Stephens ZD;Lee SY;Faghri F;Campbell RH;Zhai C;Efron MJ;Iyer R;Schatz MC;Sinha S;Robinson GE
通讯作者：
Robinson GE