基于限长空位和onE-off约束的模式匹配求解模型研究

摘要

在模式识别问题中引入通配符这种特殊字符以匹配字母表中的任意字符，从而形成了带有通配符模式匹配这一新的研究方向，在计算生物学、信息检索等研究领域得到了广泛关注。然而，上述领域的大量研究表明，频繁共现在一段文本区域内的多个模式之间表现为某种模式形式。比如在DNA序列中，TATA序列作为内含子的起始标志常出现在CAATCT序列下游30-50 bp的位置，这两个子序列共同组成的模式可提高序列特异性，可以标记为“…CAATCT[30，50]TATA…”。
　　上述情况可进一步推广为子模式序列集，其中两个相邻子模式的间隔在一定长度范围内，为表示这种灵活的位置间隔，将通配符从指代单个字符扩展为指代一定长度的子串，称此通配符为限长空位（Bounded length gaps）。另外，通过引入one-off约束以保证子模式序列集的稳定性，避免了个别子模式异常的出现次数影响子模式集的匹配。由此而得到了带有限长空位和one-off约束的模式匹配(PMGO)问题。本文围绕PMGO问题，开展了一系列相关的研究工作，主要研究成果包括以下几个方面:
　　(1)借鉴约束可满足问题框架，对PMGO问题建立求解模型。模型由变量、值域和约束条件构成三元组，并运用形式化语言描述了问题的限长空位、约束条件和解空间等主要概念，同时说明了PMGO问题的基本性质，其中包括在特殊条件下的完备性和相邻匹配解在文本中的位置关系。另外，针对限长空位使得匹配问题形成了多分支的解结构，借助模型说明了在此解空间中搜索满足one-off约束的最优解为组合优化问题;
　　(2)提出一种求解PMGO问题的启发式搜索算法。首先，定义了解空间的划分边界，提出了采用分治策略的解空间划分算法SPLIT，将PMGO问题等价划分为若干独立的子问题，并从理论上说明了划分前后的解结构等价。实验结果表明了SPLIT算法可有效降低非线性匹配算法的时间消耗。其次，将划分后的子问题转化为图结构下的路径搜索问题，其中自顶层到底层的路径集合为解空间，而彼此独立的路径子集为匹配解集，并证明了问题转化前后求解的等价性。之后，提出一种启发式路径搜索算法GPM，根据one-off约束得到节点之间的约束关系，再迭代交互的进行剪枝与搜索，且GPM算法的输出即为PMGO问题的解。实验部分使用匹配解丢失率度量已有启发式算法和GPM算法的完备性，结果表明GPM算法可以与已有启发式算法形成互补，有效降低匹配解丢失率;
　　(3)给出了PMGO问题在特定条件下的完备性分析和求解算法。首先，将模式重复度作为一种模式特征，研究了以下两种情况的求解。一方面针对模式中无重复字符的情况，说明了使用贪心搜索策略可得到PMGO问题的完备解，该结论适用于GPM算法和已有启发式算法，实验部分以近似比为指标进一步说明了重复度对问题完备性的影响;另一方面，对于尾部带有重复字符模式串，提出了一种基于动态剪枝策略的小兵算法，实验结果表明小兵算法有效提高了匹配解的质量。

目录

声明

致谢

摘要

第一章 绪论

1．1 引言

1．2 本文主要研究内容

1．2．1 课题来源

1．2．2 主要概念

1．2．3 概念关系图

1．3 论文组织结构

第二章 带有通配符和约束条件模式匹配综述

2．1 经典模式匹配问题

2．2 基于通配符模式匹配问题的扩展

2．2．1 带有通配符模式匹配的研究背景

2．2．2 模式中通配符和约束条件的发展

2．2．3 扩展匹配问题的求解

2．3 带有限长空位和one-off约束的模式匹配(PMGO)

2．3．1 问题定义

2．3．2 启发式算法的求解思路

2．3．3 问题解结构的表示和分析

2．4 本章小结

第三章 PMGO问题的求解模型研究

3．1 PMGO问题的约束可满足问题模型

3．1．1 约束可满足问题框架

3．1．2 PMGO问题的求解模型

3．2 PMGO问题的基本性质

3．2．1 问题的特殊情况分析

3．2．2 问题的解空间及其性质分析

3．3 PMGO问题的图结构表示

3．3．1 one-off约束下的组合优化问题

3．3．2 PMGO问题的有向无环图表示

3．4 本章小结

第四章 PMGO问题的解空间划分

4．1 解空间划分

4．1．1 划分边界

4．1．2 划分完备性

4．2 PMGO问题解空间划分算法SPLIT

4．2．1 算法设计思路和流程

4．2．2 算法正确性证明

4．3 解空间划分实验

4．4 本章小结

第五章 图算法求解PMGO问题

5．1 图结构下的剪枝和匹配算法GPM

5．1．1 算法总体流程

5．1．2 构建有向无环图

5．1．3 搜索策略与剪枝策略

5．2 GPM算法实验

5．2．1 实验设计参数和流程

5．2．2 实验结果

5．3 总体求解算法

5．4 本章小结

第六章 特定条件下PMGO问题的分析和求解

6．1 特定模式特征下的完备性分析

6．1．1 相关定义

6．1．2 PMGO问题在特定条件下的完备性证明

6．1．3 完备性实验

6．2 特定模式特征下的算法求解

6．2．1 相关定义

6．2．2 算法规则和总体流程

6．2．3 实验设计

6．3 本章小结

第七章 结束语

7．1 主要研究工作

7．2 下一步工作计划

参考文献

攻读博士学位期间的学术活动及成果情况