• 基于FMD索引和快表的跨越式种子查找算法

    • 摘要:

      本发明公开了一种基于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是要查找的种子的长度.