DNA序列中弱信号基序查找算法比较与分析  

Comparison and Analysis on Subtle Motifs Discovery Algorithms in DNA Sequence

作　　者：王建新[1] 杨德[1] 黄元南[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机科学》2008年第8期188-194,共7页Computer Science

基　　金：国家自然科学基金重点项目:生物信息学中的相关组合理论和算法研究(60433020);新世纪优秀人才支持计划No.NCET-05-0683;长江学者和创新团队发展计划资助No.IRT0661

摘　　要：在DNA序列中查找基序是生物信息学中一个重要的计算问题,人们针对这一计算问题提出了多种模型和算法。由于DNA序列数据的复杂性,在其中有许多是比强信号基序更难提取的弱信号基序。而目前植入(l,d)基序问题(PMP)和扩展植入(l,d)基序问题(EMP)是较适合模拟弱信号基序查找的问题模型。本文归纳分析了基序查找的基本方法、策略和基序模型,指出了各种策略和模型的优势与不足。在此基础上对现有的基于植入基序查找问题模型的主要弱信号基序查找算法进行了分析和实验评估,为选择计算方法查找弱基序信号提供了参考,并讨论了该方向上尚未解决的问题和发展趋势。Finding motifs is a significant computational problem in bioinforrnatics, many models and algorithms have been proposed to solve this problem. By reason of the complexity of DNA sequence data, there exist lots of subtle motifs which are much more difficult to be found than strong signals. Up to now, the planted （l,d） motif problem and the extended planted （l,d） motif problem are two suitable models for finding subtle motifs. This paper generalizes and analyzes the methods and strategies of motif discovery and the motif model as well as points out their advantages and disadvantages. Based on the above work, this paper further assays some main present subtle motif discovery algorithms through experiments and make a reference for the users of motif discovery. This paper also provides discussion on some unresolved problems and development trend in this field.

关 键 词：弱信号 基序查找 植入(l d)问题 算法 一致序列 简图 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] Q523[自动化与计算机技术—计算机科学与技术]