论文部分内容阅读
序列比对是生物信息学中最基础的一种实验过程，这对于根据序列进行深入的生物学意义的研究，如保守区或者功能基序的判定与评价、遗传疾病的分析、系统发育分析和功能预测，具有十分重要的意义。MUSCLE软件作为序列比对软件中运行效率较高、处理规模较大的代表，被人们广泛使用。但是MUSCLE在处理较大规模的比对时同样面临着耗时多的缺点。
本文通过对MUSCLE软件的并行化研究主要做了以下两个方面的工作：
(1)通过对运行效率的分析，确定其最耗时部分为比对过程的第三步。而通过研究其算法，得知这部分可以被划分成相对独立的子序列间的并行比对。而不同子序列间的比对天然具有可并行的特点，而且便于用OpenMP实现数据级的并行加速。通过使用OpenMP实现这部分的加速，实测数据显示，一般能够达到40％～100％的加速比。
(2)对MUSCLE软件最耗时的核心比对算法——Needleman-Wunsch算法进行了详细深入的研究，并用CUDA技术在GPU上面实现了MUSCLE软件中的NWSmall算法函数。同时针对CUDA技术的特点进行了一系列的优化与改写措施，包含类到结构体的转换、AOS到SOA的转换、优化设计新的TB矩阵的存储方法等。后续的性能测试显示，对上万bp长度的两两基因组序列比对的加速效果比较明显，最多能够达到10倍的加速比。
总之，本文对MUSCLE软件的加速实现了模块化加速（OpenMP版本）和关键耗时函数加速（CUDA版本）两个类型的加速。这两个加速版本有不同的适用对象，前者普遍适用于蛋白质序列的比对，而后者适用于较长序列比对的加速。同时本文的并行优化的思想对于序列比对领域的并行化研究具有一般性参考价值。