摘 要 本文研究了DNA序列的k-mer index 问题，通过对大量基因组数据的考察，我们改进了由暴力算法延伸的Donald Knuth的算法，即KMP算法，在原来的算法上我们嵌入了一个循环算法，并且使用java设计出算法程序来达到快速检索的目的，并将数据以数组形式存储，再将数组在二维坐标系里投影，再利用信息熵的计算将问题简化成关于K值和fm的函数问题。
　　关键词 k-mer k-mer 计数 频次统计 逆向遍历
　　主要原因是 k-长 DNA 子序列关键字不能完全存放在内存中，运行的大部分时间用在频繁的内外存交换上。所以，我们以算法将结果用二维数组存储于内存中就可以达到加快查询结果以及存储内存的节省问题。
　　定义：函数（[…]） = （[]）
　　其中，[]， […]。称（[…]）为[…]的关键字，由经映射成的关键字多重集记为。
　　然后将数据映射到二维空间上，形成二维数组，其坐标表示如下：
　　我们还可以利用KPM模式匹配的算法来处理序列拼接中的重复序列屏蔽问题。核心思想就是通过失效函数得到在当前位置匹配失效后，下一次开始进行匹配的位置，充分利了序列的已知信息，减少了无谓的序列比对，使得算法达到了线性时间复杂度。大大减少了所需CPU时间。经试验验证该算法对重复序列的屏蔽具有线性时间复杂度。
　　具体的失效链接值以及KPM匹配算法实现过程如下：
　　索引的计算复杂度和空间复杂度分析如下：
　　KMP的算法流程：
　　我们发现如果某个字符匹配成功，模式串首字符的位置保持不动，仅仅是 ++、 ++；如果匹配失配，不变（即不回溯），模式串会跳过匹配过的next []个字符。整个算法最坏的情况是，当模式串首字符位于的位置时才匹配成功，算法结束。
　　因此可知整个算法的计算量
　　（ + / ∣∣ + / ∣∣2…+ / ∣）
　　由于 ≤ ，且 ≥ 2，所以整个算法的时间复杂度为 （），所以，如果文本串的长度为，模式串的长度为，那么匹配过程的计算复杂度为（），算上计算next的（）时间，KMP的整体计算复杂度为（ + ）。
　　参考文献：
　　[1]朱赟.Snort 入侵检测系统的警报日志分析[D].上海：上海交通大学，2007.
　　[2]胡鹏.入侵检测系统中高效模式匹配算法的研究[D].上海：上海大学，2006.
　　[3]刘威，郭渊博，黄鹏.基于 Bloom filter 的多模式匹配引擎[J].电子学报，2010.
　　[4]刘红梅，刘国庆.基于K-mer组分信息的系统发生树构建方法[J].2013.
　　（张琴单位：吉林建筑大学基础科学部；朱颖莉单位：长春市第二实验中学）