SIMD指令在生物序列串匹配里的应用.pdf

《SIMD指令在生物序列串匹配里的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、SIMD指令在生物序列串匹配里的应用王力2014年12月中图分类号：TP319UDC分类号：004.78SIMD指令在生物序列串匹配里的应用作者姓名王力学院名称计算机学院指导教师戴林副教授答辩委员会主席李侃教授申请学位工学硕士学科专业计算机科学与技术学位授予单位北京理工大学论文答辩日期2015年1月20日SIMDBasedStringMatchingAlgorithmForBiologicalSequenceCandidateName：LiWangSchoolorDepartment:ComputerScienceandTe

2、chnologyFacultyMentor:Prof.LinDaiChair,ThesisCommittee：Prof.KanLiDegreeApplied:MasterofComputerScienceMajor：ComputerScienceandTechnologyDegreeby:BeijingInstituteofTechnologyTheDateofDefence：January20，2015研究成果声明本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进行的研究工作获得的研究成果。尽我所知，文中除特别标注

3、和致谢的地方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京理工大学或其它教育机构的学位或证书所使用过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在学位论文中作了明确的说明并表示了谢意。特此申明。签名：日期：北京理工大学硕士学位论文摘要串匹配算法是一个在计算机科学里被广泛研究的问题，它在生物信息学、自然语言处理、信息检索里有着广泛的应用等。例如，串匹配算法常用来在基因序列中检索相似串或定位某一基因片段。截止目前，已经有一些专门针对生物序列的串匹配算法被提出，如tvsbs，graspm等。

4、在高通量序列检测技术的快速发展下，获取生物基因序列变得越来越容易和便宜。同时也带来了海量基因序列匹配查询的巨大挑战。因此，设计更有效的生物序列匹配算法去应对这种挑战是及其重要的。采用并行ram模型能加速串匹配算法。计算机操作长度为ω的字，使得能一次性读入块字符。这意味着许多算法中的一些对字的操作步骤能在一个CPU单位时间内完成。许多使用字并行ram模型的算法都基于以下两种技术，位并行技术和块字符技术。其中，有一个叫SSECP的算法使用块字符技术取得了不错的效果。块字符就是将多个字符组合成一个字符块，即一个128位的数值，存储

5、在SIMD指令集的128位寄存器里，该寄存器内的值能在有限个机器时间内完成以前需要多条指令完成的计算，使得该字符块能单独进行运算而不用逐字符匹配。在本文中我们针对生物序列提出了一个使用块字符的精确字符串匹配算法，ImprovedExactPackedStringMatching(IEPSM)。该算法首先通过选取并组合一些SSE指令来形成新的模拟指令，然后使用这些模拟指令去实现算法。由于采用的SSE指令的输入参数为128位的值，所以该算法根据串长16字符分为两种不同的情况进行讨论。对于长串的情况，IEPSM通过计算CRC码的硬

6、件指令去获得采样串的哈希值，并通过优化的块字符大小和指纹值去减少全匹配的调用。其中对于优化的块字符大小，我们是通过一组实验得出来的。该算法较其他串匹配算法最大的不同在于指针按常量累加，这个特性在编程实现中有很大优势。另外对于短串的情形，本文通过硬件指令直接就能获取前四个字符的匹配次数和位置，通过这样来进行采样判断。最后本文进行了一系列的比对实验，实验结果表明该算法性能比其他算法有明显的优势。本文后面的多个算法在不同生物序列的比较实验中显示出IEPSM获取了比其他算法更好的效率。因此在检索海量生物数据里，IEPSM将是一个广泛

7、运用的工具。关键词：串匹配；生物信息学；IntelSSE指令I北京理工大学硕士学位论文AbstractStringmatchingisanimportantproblemthathasbeenthoroughlystudiedincomputerscience,withbroadapplicationsinbioinformaticsaswellasnaturallanguageprocessing,informationretrieval,etc.Forexample,itisusedtofindsimilarsequen

8、ceorlocateasegmentinalongsequence.Currently,severalstringmatchingalgorithmsareusedonbiologicalsequences,suchastvsbs,graspmetc.Withtherapiddevelop