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

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