带有通配符模式匹配是模式识别领域中重要的研究方向之一,在计算生物学、信息检索、网络安全等研究领域中都得到了广泛关注。它是通过在模式识别问题中引入通配符这种特殊字符,来匹配字母表中的任意字符,这样带来更多灵活性的匹配结果,但也使得问题求解变得更为复杂。当频繁共现在一段文本区域内的多个模式之间表现为某种模式形式。例如在DNA序列中,启动子TATTA序列常常出现在CAATCT序列下游中间间隔30-50个通配符,其中也不是简单的重复。由这两个子序列共同组成的模式可提高序列特异性,可以标记“CAATCT[30-50]TATA...”。将其特点推广为子模式序列集间隔,其中两个相邻子模式的间隔在一定长度范围内,为表示这种灵活的位置间隔,将通配符从指代单个字符扩展为指代一定长度的子串,此通配符称作限长空位(Bounded length gaps)。同时通过引入one-off约束限制条件来保证匹配子串模式序列集的稳定性。研究带有通配符可变长度约束的模式匹配问题。本文围绕带通配符和长度约束的模式匹配问题中解结构的复杂性特征,从设计求解算法以及相似性度量模型应用等问题,展开一些研究工作,主要内容概括为以下三个方面:(1)结合带通配符和长度约束的精确模式匹配问题中求解的复杂性、精确性与完备性等特征,针对目前已有研究成果中还缺少针对性的模型建立求解策略。为此,借鉴约束可满足问题框架(CSPs),首先对带通配符和长度约束的精确模式匹配问题构建三元组求解模型。模型对该问题的约束条件和解空间等基本概念给出形式化的描述,并将该问题已知的8条特殊情况统一表述为问题的基本性质,其中包括在特殊条件下的完备性和相邻匹配解在文本中的位置关系。同时提出一种求解带通配符的模式串精确匹配问题的FIN算法。首先在定义了解空间的划分边界中,提出了采用分治策略的解空间划分算法,将带通配符的模式串精确匹配问题等价划分为若干独立的子问题,并从理论上说明了划分前后解结构等价性。实验结果表明FIN算法与解决相同问题的算法(PAIG)对比,该算法不仅可以得到匹配数目,而且可以得到完备的匹配解位置。(2)针对处理带通配符的近似模式匹配问题中,使用传统算法求解存在匹配子串结果质量不高、易丢解等问题,提出一种启发式的算法W-DPBI。该算法采取文本倒置搜索策略与流程的优化。与同类DP和SAIL-APPROX算法进行实验对比,结果表明该算法获取解的平均增长率可达21.9%,最高可达57%,匹配结果具有良好的优势,在特定情况下可以明显提高求解近似匹配结果的质量和能力,具有较好的运用灵活性和启发性。(3)结合模式匹配及其相关求解算法在计算生物学领域中应用以及相关实验方法研究的成果,针对药物基因和疾病基因序列中的相似度结构等特征,对所收集的数据信息源,采用近似匹配协同过滤算法并与相关算法组合求解搜索的策略,着重从已知疾病信息与基因信息角度来计算药物与疾病之间的相似度,应用于药物重定位与构建模型研究。实验结果表明,该方法能够明显提高潜在治疗关系的药物-疾病的富集程度。相比于已有分类模型和随机抽样结果,可以有效降低了预测的假阳性率,其模型参数可作为药物研发试验的参照。