Next Generation Sequencing (NGS) platforms typically produce short reads of size 50–150 base pairs (bp). The number of such short reads can be up to 6 billion per run. To align these short reads to a large genome is a computationally challenging problem. In this paper, we address this problem by considering the design and optimization of parallel sequence alignment on GPU based hybrid architectures. Even though the sequence alignment algorithm is inherently data-parallel, issues such as (a) space-time trade-offs in the Indexing schema, (b) need for fast candidate location search (CAL) on GPU, (c) maintaining low divergence along with low space for the dynamic programming based local alignment, make this a very challenging problem. We present the design of our novel parallel algorithm Graphics processor Accelerated BFAST (GrABFAST) for large scale read alignment that overcomes these challenges and demonstrates superior performance compared to Intel multi-core architectures. Using 5 large genomes including those of Humans, Maize, Horse, Dog and Bacteria, we demonstrate a speedup of around 6x using Fermi Tesla C2070 GPUs vs the BFAST algorithm on 16 core Intel Xeon 5570 architecture.
展开▼
机译：下一代测序（NGS）平台通常产生尺寸为50-150个碱基对（BP）的短读取。每次运行此类短读数的数量可达60亿。将这些短读对齐至大型基因组是一个计算挑战性问题。在本文中，我们通过考虑基于GPU的混合架构上的并行序列对齐的设计和优化来解决这个问题。即使序列对齐算法本质上是数据并行的，索引模式中的（a）在索引模式中的时空折衷等问题，（b）需要在gpu上需要快速候选位置搜索（cal），（c）保持低发散随着基于动态编程的局部对齐的低空间，使这成为一个非常具有挑战性的问题。我们介绍了我们的新型并行算法图形处理器加速BFast（Grabfast）的设计，用于大规模读取对齐，克服了这些挑战，并与英特尔多核架构相比，表现出优越的性能。使用5种大型基因组，包括人类，玉米，马，狗和细菌，我们使用Fermi Tesla C2070 GPU展示了大约6倍的加速，VS在16个核心英特尔Xeon 5570架构上的BFast算法。
展开▼
