基因序列比对的Smith-Waterman多级并行算法研究

摘要

在基因测序和粗略的序列相似性比对中,广泛采用以BLAST为代表的启示性算法，但该算法损失了敏感性,以Smith-Waterman为代表的动态规划算法是提高序列相似性的有效途径，其时间复杂度为O(N2),其中N为序列的长度。rn 本文提出了面向机群体系结构的Smith-Waterman多级并行算法。所谓多级并行是指细粒度并行(指令级)、较粗粒度并行(程序内部)、粗粒度并行(程序级)。仿真模拟和试验验证表明，采用多级并行算法可以充分发挥系统在各个层次上的并行性，获得高性能。