判据搜索算法及其在DNA序列模式发现中的应用

• 作者: 李冬冬 杜耀华 王正志
• 来源期刊: 系统仿真学报
• 学科: 工学
• 关键词: 模式发现 判据 剪枝规则 深度优先搜索 层次图
• 年，卷（期）: 2006,（5）
• 所属期刊栏目: 仿真建模与仿真算法
• 页码范围: 1169-1177
• 页数: 9页
• 分类号: TP391.4
• 字数: 696字
• 语种: 中文
• DOI: 10.3969/j.issn.1004-731X.2006.05.022

摘要

模式发现是计算生物学一个重要的研究方向,但目前的大部分算法还不能保证获得最优的模式.将模式发现问题转化成层次图的路径搜索问题,推导了针对三个序列片段相似性关系的判据,以其作为剪枝规则提出并实现了一种深度优先的穷举搜索算法:判据搜索算法(Criterion Search Algorithm, CRISA).理论分析表明,对于绝大多数模式发现问题,CRISA具有多项式的计算时间复杂度和线性的空间复杂度.对仿真的和实际的DNA序列数据的测试表明,CRISA能够快速而完全地识别出序列中所有的模式,并且获得了优于其它算法的总体评价.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王正志	国防科技大学机电工程与自动化学院	85	629	13.0	20.0
2	李冬冬	国防科技大学机电工程与自动化学院	10	55	5.0	7.0
3	杜耀华	国防科技大学机电工程与自动化学院	19	110	7.0	10.0