摘要
[目的]探索准确、高效、低成本、通用性并存的生物序列比对方法。[方法]将点阵图算法、启发式算法等各种序列比对算法中准确性最高的动态规划算法予以在计算机中实现,并通过流模型将其映射到图形硬件上以实现算法加速,通过数据库比对搜索实例进行比对时间和每秒百万次格点更新(MCUPS)性能值评测。[结果]与目前最快的启发式算法相比,该加速算法比对平均加速为18倍,最高加速可达28倍。[结论]该加速算法在保证比对准确性的同时,能较大地提高比对速度。
[Objective] To explore biological sequence alignment method with accuracy,efficiency,low-cost and universality.[Methods] We achieved dynamic programming algorithms with higher accuracy than the other 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(million cell updates per second,MCUPS)was used to evaluate the performance of the accelerated algorithm by an example of database alignment scanning.[Results] The alignment speed of the accelerat algorithm averagely was 18 times and maximally 28 times as fast as that of heuristic algorithm with highest speed at present.[Conclusion] The accelerated algorithm greatly improved the alignment speed and ensured the alignment accuracy at the same time.
出处
《浙江中医药大学学报》
CAS
2012年第4期411-416,共6页
Journal of Zhejiang Chinese Medical University
基金
浙江省大学生科技创新活动计划(新苗人才计划)资助项目(2011R410020)~~
关键词
生物分子
序列比对
动态规划算法
图形硬件
biological macromolecule
sequence alignment
dynamic programming algorithm
graphics hardware