![](https://csdnimg.cn/release/download_crawler_static/85788728/bga.jpg)
第一章 绪论 3
很难确定,这就决定了精确算法对真实数据难以适用且无法处理弱保守模体问题。
另一种基于概率的方法属于近似模体发现算法,这种方法通过建立统计模型,
如采用结合位点的贝叶斯模型
[12][13]
,隐马尔科夫模型
[14]
等。通过不断迭代训练得
到最优模体。这些方法通常使用位置权重矩阵(Position Weight Matrix, PWM)或位
置频率矩阵(Position Frequency Matrix, PFM)来表示每个位置上碱基概率,通过不
断迭代获得最佳的 PFM。EM (Expectation Maximization)算法采用期望最大化的方
法估计序列的位点参数
[15]
。Gibbs Sample 和 MEME 是两个经典的基于概率算法。
Gibbs Sample
[16]
在各条序列中随机地选取起始位置来产生初始状态,然后开始执
行包含如下两个步骤的迭代:预更新和采样。MEME 算法
[17]
,是对 EM 算法的扩
展,用于在未经比对的一簇序列中查找模体。
但由于统计方法是根据建立的模型对 TFBSs 的位置进行采样的,所以可能需
要花费较长时间才能收敛和趋于稳定。并且这种方法对于起始点非常敏感,很可
能会陷入局部最优。在真实 TFBSs 问题中,局部最优的问题会因为大量背景序列
的存在变得更加显著。
近年来,遗传算法(Genetic Algorithms, GA)也被广泛应用于模体发现领域。如
Wei 和 Jensen
[18]
提出的 GAME,使用基于贝叶斯的后验分布作为适应度函数。另
一个基于 GA 的算法 GALF-P
[19]
是在搜索阶段和自适应模型后处理时使用了一个
局部的过滤操作。Huo 等人
[20]
提出的算法 GOBMD 则是通过随机投影为遗传算
法提供良好的初始种群进行求精。GARPS 算法
[21]
, 采用一个高效的基于哈希的随
机投影策略对输入数据进行处理,减少了搜索空间,然后采用遗传算法进行求精。
遗传算法在一个大搜索空间内可以找到 v 一个全局最优的结果,但是其过程是随
机的,每次运行结果不同,故需要较大的种群空间和较长的运行时间。
从上面的分析可以看到,每种模体发现算法都有一定的缺陷,再加上生物体
中 DNA 或蛋白质序列的复杂性,模体实例的分布更加分散,特别是基因变异的
存在,导致模体发现问题变得非常复杂,单纯通过一种手段来解决模体发现问题
已经很难在取得性能上的提升。本文的研究工作正式基于这种背景,通过结合多
种途径的技术和方法来对模体发现算法的性能进行优化和改进。
1.4 本文主要工作
本文所提出的模体发现算法将基于穷举搜索的精确算法和基于概率矩阵的非
精确算法结合起来。首先,为了缩小解空间,获得性能上的提升,本文提出了一
种基于后缀树和压缩后缀数组思想的子类划分算法来完成聚类过程,同时采用阈
值确保子类的大小和数目在合适范围内。这一阶段是通过基于穷举的聚类算法获
得保守的子序列集,属于精确算法的应用。其次,对不同的序列类型,采用混合
万方数据