论文部分内容阅读
进入21世纪以来，多核处理器的出现预示了CPU芯片行业未来的主要发展方向。多核处理器具有低主频，高性能，低功耗等优点，它解决了传统处理器体系结构技术所面临的瓶颈。
DNA序列模式匹配是生物信息学的一个基本问题。其目标是：寻找一个或一组基因片断在一个基因序列中的出现位置，用以比较基因的相似性和遗传关系；或者根据已知的蛋白质样本去匹配未知的蛋白质序列，从而确定其所属的蛋白质种类和功能。
DNA序列压缩模式匹配是DNA序列模式匹配的重要内容，它直接利用压缩后的DNA序列数据进行操作，不需要解压缩，在减少DNA序列存储空间的同时，极大地提高匹配搜索效率。本文致力于利用多核处理器的并行处理能力，开展DNA序列压缩模式匹配的研究，在原有的DNA序列压缩模式匹配算法基础上，以提高算法效率为目标，采用多核技术，设计并实现一系列新算法。
本文所做的主要工作包括：
(1)综述国内外DNA序列压缩模式匹配算法的研究进展。
(2)阐述多核技术的发展，分析其在改进DNA序列压缩模式匹配算法的可能性。
(3)采用Hash思想，改进Horspool算法，使其适应大规模字母表的串匹配问题。新算法引入阈值threshold表示字母表的大小，该阈值可以根据需要灵活设置，但不能超过实际的字母表大小或者是计算机主存能够分配的空间。
(4)采用多核技术，在d-BM算法基础上，设计并实现一系列新的DNA序列压缩模式匹配算法：MTD_U8Horspool、MTD_U16Horspool和MTD_U32Horspool。新算法首先采用01码压缩方法对DNA序列进行压缩处理，在保证25％的压缩率同时，加快匹配搜索的速度；接着结合OpenMP多线程编程技术，充分发挥多核处理器平台的优势。
(5)使用多核处理器平台对新算法进行实验，并与传统算法对比；实验结果表明，新算法运行效率更高。