基于分步查找的高效复合模式查找算法

《基于分步查找的高效复合模式查找算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、创新性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工

2、作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。(保密的论文在解密后遵守此规定)本学位论文属于保密，在年解密后适用本授权书。本人签名：导师签名：—吵翟乏乙上-日期纠0。乡．y日期加f。’多一彦一●一．～摘要复合模式查找是生物信息学中模式发现问题的一个新的研究领域，而寻求效率更高，精度更高的复合模式查找算法将是复合

3、模式研究领域的长期热点与目标。本文对此进行了深入的研究和探讨。本文深入研究了当今国际上的各种复合模式查找算法，系统地阐述了最具代表性的MITRA．Dyad算法和RISO算法。同时，由于本文实现的算法需要用到单分体模式查找算法，故对当今流行的单分体模式查找算法进行了简要的介绍，分析了各算法的优缺点，并对本文使用到的MITRA。Count单分体模式查找算法进行了系统阐述。ECOMP算法是一种使用错配树数据结构的复合模式分步查找算法。本文针对复合模式的一种简单形式一二分体模式的特点进行研究，通过对ECOMP算法的

4、理论分析和实验测试，证明ECOMP算法可以应用于实际的复合模式查找问题。同时，由于ECOMP算法的第一部分MITRA．Count算法的设计机制，导致其运行速度和空间占用方面都存在低效性的特点，本文将对错配树的递归遍历方式改进为基于栈式节点存储的非递归遍历方式，从而提高了MITRA—Count的运行速度，减少了空间占用。另一方面，本文还对ECOMP算法的第二部分，即将单分体模式组合为复合模式的部分进行了空间优化，减少了算法实现时的内存开销，并通过模拟数据和真实数据的测试证明了本文对ECOMP算法改进的有效性。

5、关键词：复合模式错配树二分体分步查找栈式节点存储AbstractIIICompositepaRemdiscoveryisanewresearchfieldofpatterndiscoveryprobleminBioinformatics．AnditwillbeapopularissueandtargetincompositepatterndiscoveryfieldinalongfuturetoseekmoreefficientandmoreaccuratecompositepaRemdiscoveryal

6、gorithm．Inthispaper,wemadeanintensivestudyanddiscussion．Inthispaper,wemadeanintensivestudyofkindsofcompositepattemdiscoveryalgorithmsintheworld，systematicallyillustratedMITRA-DyadandR／SO，whicharethemosttworepresentativealgorithms．Andbecausethealgorithmwere

7、alizedinthispaperhadusedamonadpatterndiscoveryalgorithm，wemadeabriefintroductiontothepopularmonadpatterndiscoveryalgorithmsnowadays，analyzedtheadvantagesanddisadvantagesofeachalgorithm，andsystematicallyillustratedMITRA-Count，whichisacompositepaRemdiscovery

8、algorithmweusedinthepaper．ECOMPisaasynchronouscompositepaUemdiscoveryalgorithmbasedonmismatchtreedatastructure．Weresearchedcharacteristicofdyadpattern，whichisasimpleformofcompositepaRem．ByanalysisandtestofECO