一种改进的基因序列匹配算法

摘要

提出了一种基于BM算法的改进字符串精确匹配算法.该算法采用双向匹配,充分考虑文本串中当前失匹字符、模式串尾字符与文本串对应的字符、模式串尾字符与文本串对应字符的下一个字符三者之间的关系,同时,在失匹时先不进行跳跃,而是根据当前失匹字符或模式串尾字符对应文本字符的下一个字符预先判断下一次跳跃后文本窗口的尾字符与模式串尾字符是否相同,然后再决定模式串的跳跃距离.从实验结果可知,当改进的算法用于DNA比对时,改进的算法比BM算法、BMHS算法性能更优.%In this paper,an improved pattern string mactching algorithm based on BM algorithm is proposed.The algorithm adopts bidirectional matching,considering the current mismatching character in a text string and the last character of the pattern string corresponds to the character of the main string and the next character of the relationship between the three,at the same time,the jumping is not carried out in the case of losing a match,but the next character of the text character corresponding to the current mismatched character or pattern string character is preliminarily judged whether the tail character of the text window is the same as the pattern string character after the next jump,and then determine the jump distance of the pattern string.The experimental result show that the improved algorithm is better than the BM algorithm and BMHS algorithm when the improved algorithm is used for DNA alignment.