Flexible, Fast and Accurate Sequence Alignment Profiling on GPGPU with PaSWAS

MotivationTo obtain large-scale sequence alignments in a fast and flexible way is an important step in the analyses of next generation sequencing data. Applications based on the Smith-Waterman (SW) algorithm are often either not fast enough, limited to dedicated tasks or not sufficiently accurate due to statistical issues. Current SW implementations that run on graphics hardware do not report the alignment details necessary for further analysis.ResultsWith the Parallel SW Alignment Software (PaSWAS) it is possible (a) to have easy access to the computational power of NVIDIA-based general purpose graphics processing units (GPGPUs) to perform high-speed sequence alignments, and (b) retrieve relevant information such as score, number of gaps and mismatches. The software reports multiple hits per alignment. The added value of the new SW implementation is demonstrated with two test cases: (1) tag recovery in next generation sequence data and (2) isotype assignment within an immunoglobulin 454 sequence data set. Both cases show the usability and versatility of the new parallel Smith-Waterman implementation.研究背景与动机：快速且灵活地获取大规模序列比对结果，是下一代测序（next generation sequencing）数据分析的关键环节。基于史密斯-沃特曼（Smith-Waterman, SW）算法的应用方案，往往存在速度不足、仅适配特定任务，或是因统计问题导致精度欠佳等缺陷。当前运行于图形硬件的SW算法实现，无法提供后续分析所需的完整比对细节信息。 研究结果：借助并行史密斯-沃特曼比对软件（PaSWAS），可实现两项核心功能：(a) 便捷调用基于英伟达（NVIDIA）的通用图形处理器（General Purpose Graphics Processing Unit, GPGPU）的算力，开展高速序列比对；(b) 提取比对相关的关键信息，如比对得分、缺口数量与错配数。该软件可单次比对输出多个匹配位点。本研究通过两个测试案例验证了新型SW算法实现方案的附加价值：(1) 下一代测序数据中的标签恢复任务；(2) 免疫球蛋白454测序数据集的亚型分型任务。两项案例均证实了该新型并行史密斯-沃特曼算法实现方案的可用性与通用性。