基于位置相互关系的模体识别算法

Algorithm for Motif Discovery Based on Position Dependency

DNA序列中的模体发现是生物信息学中重要的问题。目前解决这一问题的算法,如Gibbs采样算法,都假设模体内部各个位置之间相互独立。但最近的生物实验证实,有些模体内部各个位置之间存在明显的依赖性。文中将内部依赖性引入得分函数,同时改进了Gibbs采样算法的收敛条件和相移方法,提出PIGS算法。实验结果表明,查找出的模体在准确度方面有较大提高。

Motif discovery in DNA sequences is an important problem in Bioinformatics. Available algorithms dealing with this problem, such as Gibbs, assume that positions within a motif are mutually independent. Recent biological experiments, however, suggest that there exists dependency among positions in some motifs. This article intro- duces dependency to scoring function and improves the convergence and phase shift condition of Gibbs to develop the algorithm of PIGS. The simulated results show great improvement in accuracy and sensitivity of finding true motifs