基于CUDA平台的数据库序列比对算法加速  

Accelerating Database Sequence Comparison on CUDA Platform

作　　者：袁竞杰[1] 李叶[1] 

机构地区：[1]中国矿业大学(北京)机电与信息工程学院,北京100083

出　　处：《智能计算机与应用》2013年第2期44-49,共6页Intelligent Computer and Applications

基　　金：中央高校基本科研业务费专项资金项目(2010YJ19)

摘　　要：在生物信息学中,数据库序列比对是极为常用的操作,Smith-Waterman算法是最流行的序列比对算法,精确度高,但是计算复杂度高,在进行大量的序列比对非常耗时。另外,生物技术的发展使得已知的序列数据库变得越来越庞大,这导致进行数据库序列比对所消耗的时间也越来越长,因而有必要加速数据库序列比对算法。NVIDIA提出了CUDA编程架构,相比之前的GPGPU具有更好的可编程性,用户可以更轻松地发掘出GPU强大的计算能力。在CUDA平台上实现了Smith-Waterman的数据库序列比对算法的并行加速,速度优于已有的基于GPU的实现,超过了基于启发式算法的BLAST算法执行速度。In bioinformatics, database sequence comparison is quite commonly used, and Smith - Waterman algorithm is the most popular one in sequence comparison. In addition to high precision, Smith - Waterman algorithm also has a high computation complexity, thus it is very time - consuming when comparing a large number of sequences. Nevertheless, the sequence bank size is becoming huger and huger as the development of biotechnology. This leads to more and more consu- ming time, so it becomes very necessary to accelerate this kind of database sequence comparison algorithm. NVIDIA re- leased a kind of programming environment named CUDA. It has a much better programmability than GPGPU, and makes people much easier to take advantage of GPU＇ s large computing power. This paper implements the parallelization of a Smith - Waterman based database sequence comparison algorithm on CUDA platform, and gets a satisfactory result. The speed is better than the appeared results based on GPU implementation, and it is even better than the speeds of heuristic algorithms such as BLAST.

关 键 词：序列比对 Smith—Waterman算法 CUDA GPU计算 

分 类 号：TP37[自动化与计算机技术—计算机系统结构]