基于Hash建立索引和Kmp快速匹配算法的DNA序列查找方法  

DNA Sequence Search Based on Hash and Kmp Based Fast Matching Algorithm

作　　者：李云辉[1] 邓伟[2] 

机构地区：[1]上海海事大学信息工程学院,上海201306 [2]上海海事大学数学系,上海201306

出　　处：《数学的实践与认识》2016年第23期173-179,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金(51409157);上海海事大学校基金项目(20110011)

摘　　要：研究了DNA序列片段的查找问题,针对DNA数据量大和DNA序列碱基排列的特点提出了DNA序列检索的问题.在对DNA序列检索中,基于Hash建立了索引表以提高在大数据中检索的速度和效率,同时在平衡树的数据存储模型上使用了改进的Kmp快速匹配算法,提高了在索引上的检索效率.介绍了Hash索引的建立、Kmp的优化以及平衡树的再平衡.利用软件评估实验得出的实验结果表明了该算法的有效性.We have researched the way of finding DNA sequence fragment. According to the large volume of DNA data and the characteristics of the sequence of DNA bases, the question of DNA sequence retrival is raised. In the retrieval of DNA sequence, index table on the basis of Hash improves the speed and efficiency in the large data retrieval.At the same time, an improved Kmp fast matching algorithm used in the data storage model of balanced tree improves the retrieval efficiency of index. This article introduces the establishment of the Hash index, the optimization of Kmp and rebanlance of the balanced tree. The experiment evaluated by the software turns out this algorithm works effectively.

关 键 词：Hash索引 Kmp快速匹配 平衡树 折叠化 DNA检索 

分 类 号：Q811.4[生物学—生物工程]