资源描述：
《gpu加速的生物序列比对》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、GPU加速的生物序列比对第22卷第3期2010年3月计算机辅助设计与图形学JournalofComputer—AidedDesign&ComputerGraphicsV01.22No.3Mar.2O1OGPU加速的生物序列比对林江,唐敏,童若锋(浙江大学计算机科学与技术学院杭州310027)(tang—rn@zju.edu.cn)摘要:为了精确高效地进行生物序列比对,提出一种GPU加速的Smith—Waterman算法.该算法使用菱形数据布局以更充分地利用GPU的并行处理能力;使用查询串分批处理技术来支持上百兆规模的序列比对;同时引入树形算法,以优
2、化最大匹配值的计算.将该算法在一块NVIDIAGeForceGTX285显卡上实现,并使用多组不同规模的生物序列进行了比对实验.实验结果表明,与CPU上的串行算法相比,采用文中算法最高可获得120倍以上的性能提升.关键词:Smith—Waterman算法;序列比对;CUDA中图法分类号:Q811.4;TP391GPUAcceleratedBiologicalSequenceAlignmentLinJiang,TangMin,andTongRuofeng(CollegeofComputerScienceandTechnology,ZhejiangUniver
3、sity,Hangzhou310027)Abstract:Toimprovethebiologicalsequencealignmentinaccuracyandefficiency,aGPUacceleratedSmith—Watermanalgorithmisproposed.Thealgorithmusesdiamond—shapeddatalayouttofullyutilizetheparallelprocessingcapabilityofcommodityGPUs.Withabatchedquerytechnique,biologicalse
4、quenceswithhundredsofmillionsunitscanbeprocessed.ThemaximummatchscorecomputationiSoptimizedwithtree—basedreduction.ThealgorithmhasbeenimplementedonanNVIDIAGeForceGTX285GPU,andtestedwithmultiplesequencesundervariouslength.Experimentresultsshowthat,incomparisonwiththeCPUbasedseriala
5、lgorithms,theproposedalgorithmimprovestheoverallperformanceupto120times.Keywords:Smith—Watermanalgorithm;sequencealignment;CUDA序列比对是生物信息学中最基本的运算,Needleman等_1最早将动态规划方法引入到生物序列比对中,提出了Needleman—Wunsch算法,实现序列的全局比对.Smith等改进了Needleman-Wunsch算法,提出了着名的SmithWaterman(SW)算法,实现序列的局部比对.虽然Sw算法能良
6、好地表示2个比对序列的相似性,但计算速度非常慢,其时间复杂度为O(mn),其中m,分别表示进行比对的2条序列字符串的长度.为了降低SW算法的复杂性,Altschul等和Rearson等l4]提出了一系列启发式算法,这些算法虽然在速度上有很大改进,然而却是以牺牲比对结果的质量为代价.随着越来越多的基因组序列被测定,生物序列变得越来越庞大,对比对算法性能的提高,效率的改善提出了更高的要求.与此同时,多核/众核体系架构的引入使得计算机的计算能力成倍增长.GPU的并行处理能力越来收稿日期:20091014;修回日期:2010—01—22.基金项目:国家自然科学基金
7、(60803054).林江(1986一),男,硕士研究生,主要研究方向为并行计算,计算机图形学;唐敏(1974),男,博士,副教授,硕士生导师,论文通讯作者,主要研究方向为碰撞检测,多核计算;童若锋(1969),男,博士,教授,博士生导师,主要研究方向为计算机图形学,图形与视频处理.第3期林江,等:GPU加速的生物序列比对421越强大,而且不再拘泥于传统的图形处理,开始辅助CPU完成图形计算以外的运算.如果能充分利用GPU的并行处理能力,与单纯的CPU计算相比,计算性能可得到很大的提升.此外,NVIDIA公司推出的CuDA开发工具使程序员能在c语言环境下完
8、成对GPU的并行处理架构的调用,大大方便了对GPU的使用.本文在C
