新型图形硬件支持下的动态规划局部比对算法加速研究  

Research of dynamic programming local alignment algorithm acceleration based on a new type of graphics hardware

作　　者：张林[1] 

机构地区：[1]浙江中医药大学生命科学学院,浙江杭州310053

出　　处：《生物信息学》2014年第3期179-184,共6页Chinese Journal of Bioinformatics

基　　金：浙江省医药卫生科技计划项目(2013KYA137);浙江省自然科学基金项目(LY13H020007);浙江省中医药科学研究基金计划(2011ZB027)资助

摘　　要：为探索准确、高效、低成本、通用性并存的生物序列局部比对方法。将点阵图算法、启发式算法等各种序列局部比对算法中准确性最高的动态规划局部比对算法在计算机中实现,并通过流式模型将其映射到图形硬件上以实现算法加速,再通过实例比对搜索数据库完成比对时间和每秒百万次格点更新(MCUPS)性能值评测。结果表明,该加速算法在保证比对准确性的同时,能显著提升比对速度。与目前最快的启发式算法相比,比对平均加速为14.5倍,最高加速可达22.9倍。This paper is aimed to explore biological sequence local alignment method with accuracy, efficiency, low-cost and universality. We presented dynamic programming local alignment algorithms with higher accuracy than the other local alignment algorithms, such as lattice diagram algorithm and heuristic algorithm, in computer and mapped it to the graphics hardware by stream model to speed up the algorithm. The alignment time and million cell updates per second （ MCUPS） were used to evaluate the performance of the accelerated algorithm by an example of database alignment scanning. The result showed that the accelerated algorithm greatly improved the alignment speed and ensured the alignment accuracy at the same time. The alignment speed averagely was 14.5 times and maximally 22.9 times as fast as that of heuristic algorithm with highest speed at present.

关 键 词：生物分子 序列局部比对 动态规划局部比对算法 图形硬件 

分 类 号：Q332[生物学—遗传学] R318[医药卫生—生物医学工程]