新型图形硬件支持下的动态规划局部比对算法加速研张林(浙江中医药大学生命科学学院，浙江杭州310053)摘要:为探索准确、高效、低成本、通用性并存的生物序列局部比对方法。将点阵图算法、启发式算法等各种序列局部比对算法中准确性最高的动态规划局部比对算法在计算机中实现，并通过流式模型将其映射到图形硬件上以实现算法加速，再通过实例比对搜索数据库完成比对时间和每秒百万次格点更新(MCUPS)性能值评测。结果表明，该加速算法在保证比对准确性的同时，能显著提升比对速度。与目前最快的启发式算法相比，比对平均加速为14．5倍，最高加速可达22．9倍。关键词:生物分子;序列局部比对;动态规划局部比对算法;图形硬中图分类号:Q－332，Ｒ318文献标志码:A文章编号:1672－5565(2014)－03－179－06ＲesearchofdynamicprogramminglocalalignmentalgorithmaccelerationbasedonanewtypeofgraphicshardwareAbstract:Thispaperisaimedtoexplorebiologicalsequencelocalalignmentmethodwithaccuracy，efficiency，low－costanduniversality．Wepresenteddynamicprogramminglocalalignmentalgorithmswithhigheraccuracythantheotherlocalalignmentalgorithms，suchaslatticediagramalgorithmandheuristicalgorithm，incomputerandmappedittothegraphicshardwarebystreammodeltospeedupthealgorithm．Thealignmenttimeandmillioncellupdatespersecond(MCUPS)wereusedtoevaluatetheperformanceoftheacceleratedalgorithmbyanexampleofdatabasealignmentscanning．Theresultshowedthattheacceleratedalgorithmgreatlyimprovedthealignmentspeedandensuredthealignmentaccuracyatthesametime．Thealignmentspeedaveragelywas14．5timesandmaximally22．9timesasfastasthatofheuristicalgorithmwithhighestspeedatpresent．Keywords:Biologicalmacromolecule;Sequencelocalalignment;Dynamicprogramminglocal生物序列分析是生物信息学研究的一个重要手段，它是了解基因组结构和功能的基本途径［1］。而在生物序列分析中，生物序列比对是最常用和最经典的研究手段［2］。基于真核表达的剪接特点和蛋白质的模块性质，目前，序列局部比对已成为生物序列比对中的主要分析方式。其通过将查询序列与整个生物数据库的所有序列进行局部比对，来完成一系列的生物学分析，探索生命起源和存在的内因此，在保证比对准确的同时如何提高其效率，已成为序列局部比对的瓶颈。现在比较重要的是动态规划局部比对算法［3］，准确性高是其最大优点，但存在着效率问题。为了增加动态规划局部比对算法的效率，最早提出的解决方案是加入启发式算法，例如现在常见的FASTA和BLAST算法［4］，但其准确性受到影响。现在的思路是采用专门的生物信息处理机器和专有硬件提高动态规划局部比对算法的比对速度，但其缺点是投入太大，实现困难。近年来，图形硬件(计算机显卡)发展迅速，主收稿日期:2014－05－04;修回日期:2014－06－09.基金项目:浙江省医药卫生科技计划项目(2013KYA137);浙江省自然科学基金项目(LY13H020007);浙江省中医药科学研究基金计划(2011ZB027)资助。作者简介:张林，男，硕士，讲师，研究方向:生物信息学医药分析、生物信息数据挖掘与分析;E－mail:shibailezlzl@sina．com．---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---180生物信息学第12卷要具有以下优点。第一，浮点运算能力强，显存与位宽大，非常适合高密度的运算，也非常适合流式处理［5］。第二，并行度很高，具有统一渲染构架，非常适合并行运算。第三，可编程，具备了通用计算能力［6－7］，在图像处理［8］、计算几何［9］、科学计算［10］、生物数据分析等领域已有多处应用［11－12］。第四，价格便宜，性价比非常高。鉴于上述背景，本文拟以动态规划局部比对算启发式算法加速，比对速度快，但准确性受到影响。对照组其他比对条件、电脑配置均与实验组一致(见实验材料)。评价参数:时间性能(执行时间)、MCUPS(MillionCellUpdatesPerSecond)性能值。其中MCUPS为“每秒百万次格点更新”，在生物序列比对中，其代表了每秒能...