子网树求解一般间隙和长度约束严格模式匹配
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家重点基础研究发展计划(973)(2013CB329604); 国家自然科学基金(61229301); 国家高技术研究发展计划(863)(2012AA011005); 河北省自然科学基金(H2012202035, F2013202138); 河北省教育厅重点项目(ZH2012038)


Subnettrees for Strict Pattern Matching with General Gaps and Length Constraints
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    具有通配符间隙约束的模式匹配问题在信息检索、计算生物学和序列模式挖掘等研究领域有重要的应用.提出了更一般性的模式匹配问题,即一般间隙和长度约束的严格模式匹配(strict pattern matching with generalgaps and length constraints,简称SPANGLO).该问题具有如下4 个特点:它是一种严格的精确模式匹配;允许序列中任意位置的字符被多次使用;模式串中可以包含多个一般间隙;对出现的总体长度进行了约束.最坏情况下,一个SPANGLO 实例将转换出指数个非负间隙的严格模式匹配实例.为了有效地解决该问题,提出了子网树及其相关概念和性质.在此基础上提出了求解算法Subnettree Spanglo(SETS),并给出算法的正确性和完备性证明,同时指出该算法的空间复杂度与时间复杂度分别为O(m×MaxLen×W)O(MaxLen×W×m2×n),其中,m,n,MaxLenW分别是模式和序列的长度、出现的最大长度约束和模式的最大间距.实验结果既验证了SPANGLO 问题转换方法的正确性,又验证了该算法的正确性和有效性.

    Abstract:

    Pattern matching with gap constraints has important applications in many fields such as information retrieval, computational biology, and sequential pattern mining etc. This paper proposes a pattern matching problem named Strict Pattern Matching with General Gaps and Length Constraints (SPANGLO) which has four characteristics: It is strict exact pattern matching; Any position in the given sequence can be used more than once; The pattern can have more than one general gap constraint; Each matching substring has length constraints. An instance of SPANGLO can be transformed into an exponential number of matching instances with non-negative gaps in the worst case. In order to solve the problem effectively, an algorithm named SubnettreeSpanglo (SETS) is proposed based on Subnettree and its special concepts and properties. The correctness and completeness of the algorithm are given, and the space and time complexities of the algorithm are O(m×MaxLen×W) and O(MaxLen×W×m2×n) respectively, where n, m, MaxLen and W are the sequence length, the pattern length, the maximum length of the occurrence and the maximum gap of the pattern respectively. Experimental results validate the correctness of the transforming method of SPANGLO and the efficientiveness and correctness of SETS.

    参考文献
    相似文献
    引证文献
引用本文

武优西,刘亚伟,郭磊,吴信东.子网树求解一般间隙和长度约束严格模式匹配.软件学报,2013,24(5):915-932

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2012-09-13
  • 最后修改日期:2013-02-05
  • 录用日期:
  • 在线发布日期: 2013-05-07
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号