论文部分内容阅读
基本局部匹配查询工具BLAST是用来快速比较序列的生物信息学工具,它是一种启发式的算法。最大可能地找出序列匹配中出现的相似性序列是该算法的本质目的,即找出Maximum-length Sequence Pairs (MSP),将相似度最高的分数记录下来,要求在匹配的区域不能出现空位。PSI-BLAST,位点特异迭代BLAST,将选中的字串长度标准进行了延伸,而且在匹配中对空位没有要求,相比对BLAST,比对速度提高了三倍。基于BLAST解决大规模序列匹配时耗费了大量的时间,而又无法做到实时性,结合GPU的高速并行性,本文提出了一种基于GPU(Graphics Processing Unit,GPU)并行加速的BLAST程序。该并行程序主要借助了英伟达于2007年6月推出的CUDA(Compute Unified Device Architecture,CUDA)统一架构,将实现过程转化成CUDA线程块并行计算过程,使得BLAST子程序BLASTx在GPU中加速执行,不仅达到了较好的优化效果,而且还提高了程序的运行速度。设计并实现了采用并行化方法来优化BLAST程序,主要是基于GPU的并行计算平台,将BLAST程序中的串行过程转化为CUDA线程的并行执行过程。基于GPU的BLAST子程序BLASTx的并行计算研究,由于BLASTx特殊比对的情况,本文从GPU并行运算的角度,将六条氨基酸序列分布到GPU的六个block中,在Grid中实现block之间的并行操作。同时,由于一个内核函数中还存在另一个层次的并行,即thread间并行,因此,在将六条氨基酸序列分配到六个block后,在每个block中,每条氨基酸序列与蛋白质数据库的比对操作仍然可以并行化执行,对氨基酸序列比对的各种情况进行分配,将各个氨基酸序列窗口分配到各个thread上,各个线程同时执行查询蛋白质数据库的任务,从而在两个层次上实现了并行化操作。同时,由于block中共享存储器的容量无法满足庞大的蛋白质数据库的存储要求,因此需要对蛋白质数据库进行化分,每次只读取部分蛋白质序列。基于以上几点,整个比对过程的时间和内存的消耗都有了大大的减少。使用GPU对BLAST程序进行并行化操作执行是解决高性能BLAST需求的有效方案。文章还分析了并行优化后的BLAST程序的并行加速比和并行效率等性能,最后给出了测试仿真结果。最后,对本文的研究工作进行了总结,并指出了下一步的研究内容和方向。