具有间隙约束的模式匹配能够用来计算模式的支持度,是序列模式挖掘的重点与基础,在生物信息检索、市场营销、时间序列预测等领域具有重要的意义。模式匹配包括精确模式匹配和近似模式匹配,在现实生活中,相对精确模式匹配,近似模式匹配允许存在一定的数据噪音,更具一般意义。具有间隙约束的模式匹配往往建立在各种约束条件下,其中无重叠约束在精简计算的同时,保留了有价值信息,具有更强的表达能力。无重叠约束允许任何两个出现能够多次使用序列中的同一个字符,但不能在相同位置使用。目前,无重叠条件下的近似模式匹配采用的是Hamming距离,但Hamming距离无法度量子序列与模式之间的局部近似度,导致匹配的结果存在大的偏差。为此,本文采用（δ,γ）-距离,研究一种局部距离不超过δ且整体距离不超过γ的无重叠近似模式匹配。本文的主要研究内容如下:1、本文提出了无重叠（δ,γ）-近似模式匹配（Non-overlapping Delta and gamma approximate Pattern matching,NDP）问题,并给出问题的相关定义。2、构建了一种高效的求解算法（local approximation Nettree for NDP,Net NDP）。该算法首先将NDP问题转化为一棵局部近似网树;然后提出了最小树根距离（Minimal Root Distance,MRD）的概念,用来表示结点到达树根层的最短γ-距离,通过MRD,不仅能够判断是否存在满足整体约束的树根路径,而且能够预先删除无效的结点和双亲关系,避免无效访问,提高了时间效率;最后,该算法通过MRD寻找最右（δ,γ）-近似出现,得到最大无重叠（δ,γ）-近似出现集。3、理论上分析了Net NDP算法的空间复杂度为O（n*m*W）,时间复杂度为O（n*m2*W）,其中,n是序列S的长度,m是模式P的长度,W为最大的间隙长度。4、在真实蛋白质数据集中,通过设置阈值为0,验证了Net NDP算法的正确性;通过对比运行时间和求解质量,验证了Net NDP算法的有效性。在真实的时间序列数据集上,证明了（δ,γ）-距离比Hamming距离具有更好的匹配效果。