Subnettrees for Strict Pattern Matching with General Gaps and Length Constraints

Youxi Wu, Ya-Wei Liu, Leifeng Guo, Xindong WuJournal of Software 2013 · DOI

Abstract

具有通配符间隙约束的模式匹配问题在信息检索、计算生物学和序列模式挖掘等研究领域有重要的应用.提出了更一般性的模式匹配问题,即一般间隙和长度约束的严格模式匹配(strict pattern matching with generalgaps and length constraints,简称SPANGLO).该问题具有如下4 个特点:它是一种严格的精确模式匹配;允许序列中任意位置的字符被多次使用;模式串中可以包含多个一般间隙;对出现的总体长度进行了约束.最坏情况下,一个SPANGLO 实例将转换出指数个非负间隙的严格模式匹配实例.为了有效地解决该问题,提出了子网树及其相关概念和性质.在此基础上提出了求解算法Subnettree Spanglo(SETS),并给出算法的正确性和完备性证明,同时指出该算法的空间复杂度与时间复杂度分别为O(m×MaxLen×W)和O(MaxLen×W×m<SUP>2</SUP>×n),其中,m,n,MaxLen和W分别是模式和序列的长度、出现的最大长度约束和模式的最大间距.实验结果既验证了SPANGLO 问题转换方法的正确性,又验证了该算法的正确性和有效性.
BibTeX
@article{wu2013subnettrees,
  author = {Youxi Wu and Ya-Wei LIU and Leifeng Guo and Xindong Wu},
  title = {{Subnettrees for Strict Pattern Matching with General Gaps and Length Constraints}},
  journal = {Journal of Software},
  year = {2013},
  doi = {10.3724/sp.j.1001.2013.04381},
}

Loading related content...

Figure