首页> 中文会议>2014湖北省计算机学会学术年会 >一种带有通配符和长度约束模式匹配问题的动态剪枝算法

一种带有通配符和长度约束模式匹配问题的动态剪枝算法

页面导航

摘要
著录项
相似文献
相关主题

摘要

近年来,随着生物信息学、信息检索等领域的发展,串模式匹配问题被不断扩展.其中,具有代表性的是在模式中引入可变长度的通配符而形成带有通配符的模式匹配(PMWL).该问题定义的灵活性给用户提供了方便,却也造成了求解上的困难.因此,如何在多项式时间内得到更好的匹配解成为研究的焦点.提出了一种启发式的小兵算法.小兵算法通过将PMWL问题转化为路径搜索问题,并借鉴动态剪枝思想,在算法搜索的过程中动态地将不可能的匹配位置剪枝,从而提高解的质量.实验在真实DNA序列上进行,并人工生成了196个模式.结果表明,相比于目前最有效的SAIL算法,小兵算法在绝大多数的尾部有重复字符的模式中可以获得更好的匹配解.

著录项

来源
《2014湖北省计算机学会学术年会》|2014年|244-248|共5页
会议地点宜昌
作者
WANG Hai-ping; 王海平; DAI Wei; 戴玮; GUO Dan; 郭丹;
展开▼
作者单位

湖北省计算机学会;

展开▼
会议组织
正文语种
原文格式 PDF
中图分类算法理论;
关键词
模式匹配; 通配符; 长度约束; 动态剪枝算法;

相似文献

中文文献
外文文献
专利

1. 一种带有通配符和长度约束模式匹配问题的动态剪枝算法 [J] . 王海平 ,戴玮 ,郭丹 . 计算机科学 . 2015,第004期
2. 带有通配符和长度约束的模式匹配问题求解模型 [J] . 汪浩 ,王海平 ,吴信东 . 计算机科学 . 2016,第004期
3. 基于通配符和长度约束的近似模式匹配算法 [J] . 黄国林 ,郭丹 ,胡学钢 . 计算机应用 . 2013,第003期
4. 图算法求解带有限长空位和one-off约束的模式匹配问题 [J] . 胡学钢 ,王海平 ,郭丹 . 模式识别与人工智能 . 2016,第005期
5. 一种有效的带通配符约束的频繁序列模式挖掘算法 [J] . 毛洪 ,田卫东 . 微计算机信息 . 2010,第033期
6. 一种带有稳定约束的电力系统稳定平衡解的计算方法 [C] . 邓学华 ,周任军 ,童小娇 . 中国高等学校电力系统及其自动化专业第二十三届学术年会 . 2007
7. 基于模式特征的带有通配符和长度约束模式匹配问题研究 [A] . 王海平 . 2011

一种带有通配符和长度约束模式匹配问题的动态剪枝算法

摘要

著录项

相似文献

相关主题

期刊订阅