A Parallel Algorithm for Error Correction in High-Throughput Short-Read Data on CUDA-Enabled Graphics Hardware
A Parallel Algorithm for Error Correction in High-Throughput Short-Read Data on CUDA-Enabled Graphics Hardware
复制标题
DOI：
10.1089/cmb.2009.0062
复制
发表时间：
2010-04-01
影响因子：
1.7
通讯作者：
Mueller-Wittig, Wolfgang
中科院分区：
文献类型：
--
作者：
Shi, Haixiang;Schmidt, Bertil;Mueller-Wittig, Wolfgang
新兴的DNA测序技术通过产生具有巨大吞吐量的读取数据，为基因组测序打开了令人兴奋的新机会。然而，与传统的桑格散弹枪测序方法相比，产生的读数明显更短，更容易出错。这对从头开始的DNA片段组装算法在准确性(处理短的、容易出错的读取)和可扩展性(处理非常大的输入数据集)方面提出了挑战。在本文中，我们提出了一种可扩展的并行算法，用于纠正高通量短读数据中的测序错误，以便在DNA片段组装之前实现无错误读取，这对许多基于图的短读组装工具具有非常重要的意义。该算法基于频谱对齐，并使用计算统一设备架构(CUDA)编程模型。为了提高效率，我们正在利用CUDA纹理内存，使用空间高效的Bloom Filter数据结构来进行频谱成员查询。我们使用不同读取长度、错误率、输入大小和算法参数的真实和模拟Illumina数据测试了算法的运行时间和准确性。与公开提供的Euler-SR程序相比，使用支持CUDA的批量生产的GPU(在任何本地计算机销售点都可以买到不到400美元的价格)，并行纠错的速度提高了12-84倍，顺序预处理和并行纠错的速度提高了3-63倍。我们的实现可从http://cuda-ec.sourceforge.net.免费下载
Emerging DNA sequencing technologies open up exciting new opportunities for genome sequencing by generating read data with a massive throughput. However, produced reads are significantly shorter and more error-prone compared to the traditional Sanger shotgun sequencing method. This poses challenges for de novo DNA fragment assembly algorithms in terms of both accuracy (to deal with short, error-prone reads) and scalability (to deal with very large input data sets). In this article, we present a scalable parallel algorithm for correcting sequencing errors in high-throughput short-read data so that error-free reads can be available before DNA fragment assembly, which is of high importance to many graph-based short-read assembly tools. The algorithm is based on spectral alignment and uses the Compute Unified Device Architecture (CUDA) programming model. To gain efficiency we are taking advantage of the CUDA texture memory using a space-efficient Bloom filter data structure for spectrum membership queries. We have tested the runtime and accuracy of our algorithm using real and simulated Illumina data for different read lengths, error rates, input sizes, and algorithmic parameters. Using a CUDA-enabled mass-produced GPU (available for less than US$400 at any local computer outlet), this results in speedups of 12-84 times for the parallelized error correction, and speedups of 3-63 times for both sequential preprocessing and parallelized error correction compared to the publicly available Euler-SR program. Our implementation is freely available for download from http://cuda-ec.sourceforge.net.