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

摘要：

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

关键词：模式发现、判据、剪枝规则、深度优先搜索、层次图

所属期刊栏目：18

分类号：TP391.4(计算技术、计算机技术)

资助基金：中国科学院项目（非规范项目）60471003

在线出版日期：2006-06-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1169-1177