本发明公开了一种基于FMD索引和快表的跨越式种子查找算法,包括下述步骤:S0、构建数据库的FMD索引以及快表;S1、从快表中取出查询序列中长度为k的子序列的双区间;S2、这个步骤通过向后搜索算法,逐步找出k种子左边的匹配区域;S3、对步骤S2中缩小前的区间执行向前搜索算法,以找出k种子右边的匹配区域;S4、检查当前检测位置是否位于查询序列的尾部,如果是,则算法终止,否则,执行步骤S5;S5、将当前检测位置向前跳跃w-k+1个位置,重复执行步骤S2-S5,其中w是要查找的种子的长度.本发明提出的快表具有占用空间少、访问效率高的特点;在快表和FMD索引的基础上,本发明提出的种子查找算法能够快速地找出所有w种子的双区间.
发明专利
CN201510373462.2
2015.06.29
CN105138534A
2015-12-09
许跃生 陈颖 叶纬材
中山大学
G06F17/30(2006.01)I,G,G06,G06F,G06F17
G06F17/30(2006.01)I,G06F19/00(2011.01)I,G,G06,G06F,G06F17,G06F19,G06F17/30,G06F19/00
基于FMD索引和快表的跨越式种子查找算法,包括下述步骤:S0、构建数据库FMD索引的快表,这个快表是一个Hash表,每一个表项对应一个长度为k的短序列,保存的是在FMD索引中搜索这个短序列所得到的双区间;S1、计算查询序列中k子序列的Hash值,并从快表中取出其相应的长度为k的种子的双区间;S2、这个步骤通过向后搜索算法,逐步扩大k种子左边的匹配区域;S3、对步骤S2中缩小前的区间执行向前搜索算法,以找出k种子右边的匹配区域;S4、检查当前检测位置是否位于查询序列的尾部,如果是,则算法终止,否则,执行步骤S5;S5、将当前检测位置向前跳跃w?k+1个位置,重复执行步骤S2?S5,其中w是要查找的种子的长度.