| 本文已被：浏览 6322次 下载 4857次 |
码上扫一扫！ |
|
|
| 子网树求解一般间隙和长度约束严格模式匹配 |
|
武优西1, 刘亚伟1, 郭磊2, 吴信东3,4
|
|
1.河北工业大学计算机科学与软件学院, 天津 300401;2.河北工业大学电磁场与电器可靠性省部共建重点实验室, 天津 300130;3.合肥工业大学计算机科学与信息工程学院, 安徽 合肥 230009;4.Department of Computer Science, University of Vermont, Burlington, USA
|
|
| 摘要: |
| 具有通配符间隙约束的模式匹配问题在信息检索、计算生物学和序列模式挖掘等研究领域有重要的应用.提出了更一般性的模式匹配问题,即一般间隙和长度约束的严格模式匹配(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,MaxLen和W分别是模式和序列的长度、出现的最大长度约束和模式的最大间距.实验结果既验证了SPANGLO 问题转换方法的正确性,又验证了该算法的正确性和有效性. |
| 关键词: 模式匹配 一般间隙 长度约束 子网树 |
| DOI：10.3724/SP.J.1001.2013.04381 |
| 分类号: |
| 基金项目:国家重点基础研究发展计划(973)(2013CB329604); 国家自然科学基金(61229301); 国家高技术研究发展计划(863)(2012AA011005); 河北省自然科学基金(H2012202035, F2013202138); 河北省教育厅重点项目(ZH2012038) |
|
| Subnettrees for Strict Pattern Matching with General Gaps and Length Constraints |
|
WU You-Xi1, LIU Ya-Wei1, GUO Lei2, WU Xin-Dong3,4
|
|
1.School of Computer Science and Software, Hebei University of Technology, Tianjin 300401, China;2.Province-Ministry Joint Key Laboratory of Electromagnetic Field and Electrical Apparatus Reliability, Hebei University of Technology, Tianjin 300401, China;3.School of Computer Science and Information Engineering, Hefei University of Technology, Hefei 230009, China;4.Department of Computer Science, University of Vermont, Burlington, USA
|
| 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. |
| Key words: pattern matching general gap length constraint Subnettree |
