一种改进吉布斯采样算法寻找模体的研究.doc

《一种改进吉布斯采样算法寻找模体的研究.doc》由会员分享，可在线阅读，更多相关《一种改进吉布斯采样算法寻找模体的研究.doc（12页珍藏版）》请在三一文库上搜索。

1、精品论文大全一种改进吉布斯采样算法寻找模体的研究匡斌，饶妮妮1，韩凤君，袁祚勇电子科技大学生命科学与技术学院，四川成都 （610054）摘要：当前有许多用于预测模体的算法，但没有一种算法能有效地应用在所有场合。依 据位置权重矩阵的模体模型，我们提出了一种改进的吉布斯采样算法来识别模体。该算法 有效地克服了吉布斯采样算法的局部收敛性，并且可以直观地控制预测模体的保守度。同 时我们引入了模体库的概念，并通过分析模体库数据，提高了模体预测的灵活性和准确率。 我们设计了仿真数据，并选择了已被生物实验验证过的模体数据，证实本算法的可行性和 有效性。与当前常用的基于吉布斯采样改进的算法比较，本算法有效地提

2、高了模体预测的 准确性，灵活性和稳定性。关键词：吉布斯采样，模体，位置权重矩阵, 模体寻找1 引言识别调控元件是理解基因转录调控机制和表达模式的关键。传统上是通过生物学实验 方法来测定调控元件的，这种办法费时又代价高昂1-4。 随着计算机技术的飞速发展，科 学家们正尝试用计算机模拟来识别调控元件，以减少实验过程中的尝试性工作。共调控的基因很可能在启动子区域共享模体。这样，转录水平基因调控元件的计算方 法识别问题就转化为从一组已知的共调控基因上游启动子区域中寻找共同的模体1。通常， 从序列来预测调控元件是基于这样的假设：由于长期进化的结果，受相同调控机制作用的 基因（共调控基因）包含相对保守的启

3、动子和调控元件，正是这种保守性使从序列来预测 调控元件成为可能5。目前已有大量寻找共同模体的方法，如 Bailey 和 Elkan 提出的 MEME 算法6(1995)， Consensus 算法7(1999)、Gibbs 采样算法8-9 (1995)、AlignACE 算法10(2000)、BioProspector 算法2(2003)和 BioOptimizer 算法3(2004)等，其中 MEME 算法与 Gibbs 采样算法是具有代 表性的方法4 11。Gibbs Sampling 算法虽然具有简单，计算速度快的优点，但却是局部优 化算法，不能保证结果的全局最优性。从目前寻找模体的国际

4、商业流行算法来看，许多程 序都是基于吉布斯采样算法，然后作一定的算法改进使得它们更适合寻找模体，如 AlignACE8, BioProspector2 3等算法。常用的吉布斯采样算法的改进策略有：（1）控制背景噪声。主要采用高阶马尔可夫背景模型3，来减少噪声干扰。（2）灵活的参数设置。模体查找算法结合生物试验的验证证明，大部分模体预测算法的准 确性都难以令人满意。为此，大部分模体预测算法都给出了灵活的参数设置来改善算法性 能，比如模体丰度参数10、模体宽度参数2、两块模体之间的距离参数3和假计数百分比 参数等。这也是目前多种模体寻找算法和程序共存的主要原因之一。（3）迭代过程中的方向控制,以寻

5、求最佳的解。采用记分函数3 (scoring function)，最大后 验记分10 (MAP)等方法，力求找到最可能的预测模体或保守度最佳的预测模体。现有吉布斯采样算法的改进策略主要存在以下缺陷：（1）对模体保守度参数控制不够灵活直观；（2）在迭代控制中，可能会丧失实际生物模体保守度表现的灵活性，从而使模体预测不准1 通信作者-12-确。本文依据位置权重矩阵的模体描述模型提出了一种改进的具有直观灵活控制参数的吉 布斯采样算法, 将该方法应用于仿真数据和已被生物实验验证过的转录因子结合位点数据 的模体寻找上。通过仿真实验，证实改进方法的有效性和可行性；与现有其他算法比较， 改进方法的准确性得到

6、提高，在模体保守度上具有直观灵活控制的优点。2. 基于吉布斯采样算法的模体识别方法2.1 吉布斯采样算法512吉布斯采样算法是一种简单的 MCMC（马尔可夫链蒙特卡罗）方法1113-14，MCMC方法是与统计物理有关的一类重要随机方法，广泛使用在贝叶斯推断和机器学习中。吉布斯采样算法适用于条件分布 P( xi | x j : j i) 容易计算，或者变量 x 从很小的集合中选取的情况9。它依赖于所有其他变量的当前值，对其中每一个变量进行迭代采样。一种基本的吉布斯采样算法描述如下：算法 1：基本的吉布斯采样算法11ttt从 ( x1 , x2 ,K, xn ) 开始：tttt +11根据 p(

7、X 1 | x2 , x3 ,K, xn ) 选取 x1的值；tttt +12根据 p( X 2 | x1 , x3 ,K, xn ) 选取 x23，以此类推；的值；tttt +14根据 p( X n | x1 , x2 ,K, xn 1 ) 选取 xn的值，迭代后，最终得到一个平稳分布。应用吉布斯采样算法识别模体时，还需要建立调控元件模体模型、背景模型，引入扩展位置权重矩阵的概念。2.2 调控元件模体模型的建立首先引入计数矩阵与概率矩阵。 对于基因序列，我们假设实际观测各个模体的宽度为 M，则计数矩阵 Ci , j 定义为：c0, Ac0,CMc1, AMc1,Cc2, Ac2,CLcM ,

8、 A cLM ,C Ci , j= c0,GMc1,Gc2,GLcM ,G c0,TMc1,Tc2,TLcM ,T 其中，矩阵元素中，下标 i 表明各个碱基在模体中的不同位置，其中 0 号位置表明在背景中的计数； j 可取 A, C, G,T 中的任意一个。 概率矩阵 Qci , j 定义为：Qc0, AQc0,C|Qc1, A|Qc1,CQc2, AQc2,CLQcM , A QcLM ,C Qci , j= Qc0,G|Qc1,GQc2,GL QcM ,G Qc0,T|Qc1,TQc2,TLQcM ,T 其中， Qc=ci , j；概率矩阵 Qc描述了模体中每个位置上的各个碱基的占位情况，

9、i , j ci , jji , j下标参数 i 和 j 的意义同计数矩阵。为了避免在数值计算中异常错误的出现，同时也为了避免吉布斯采样运算中局部收敛的缺陷，进一步引入了假计数： bi ，( i 取 A, C, G, T)。假计数值与实际观测到的计数值相关。设假计数因子为 p pseu ，则假计数计算如式（1）：Mbi = cn,i p pseun =0总的假计数值如式（2）所示B = b jj（1）（2）其中， j 取 A,C,G,T。 最后，调控元件模体模型由位置权重矩阵515来描述，式（3）所示。1q2q AALq A CCC Qi , j= q1qTq Gq2Lq GqM MMq G

10、（3）1 12LM q2TLq T 假设总共有 N 条序列参与到吉布斯采样的算法中来，则位置权重矩阵的元素计算如下：q i =c j ,i+ b j（4）jN 1 + B其中，上下标 i 和 j 的意义同计数矩阵。2.3 背景模型的建立为了描述非模体区域的情况，需要建立背景模型。背景模型中的每个碱基都由离散分ACGT布q0 , q0 , q0 , q0 独立生成，则背景模型中的元素计算如式（5）：q i =c0,i+ bi0, j0 c+ B（5）j其中， i 可取碱基 A, C, G,T 中的任意一个，背景模型中的元素意义参见计数矩阵。2.4 扩展位置权重矩阵的建立将上述背景模型和模体模型组

11、合即可形成扩展位置权重矩阵，式（6）所示。利用该矩阵可以方便描述包含模体的基因序列模型。q A M q Aq ALq A 012M ACCC Qx= q0 M q1i , jq A Mq Gq2Lq GqM q G （6） 012LM q A M q Tq TLqT012M2.5 吉布斯采样算法寻找模体的方法10算法 2：基于吉布斯采样寻找模体的算法Begin:随机选取x 0 , x 0 ,K, x 0 记为 X 0 ，计算计数矩阵 C 0，位置权重矩阵 Q，利用设12Ni , ji , j定的假计数因子 p pseu 计算假计数 bi 和 B ；i , jWhile(计数矩阵 C 0不收敛)

12、For（依次扫描所有序列）i预备更新：选取 x n 第 1 次取 i = 1 ， n = 0 ，放回原序列重新计算计数矩阵 Ci , j，位置权重矩阵 Qi , j采样更新：计算模体块的适应度 Ax ， i = i + 1EndForn = n + 1EndWhile运行上述程序，可得到输出收敛的计数矩阵，计算出无假计算概率矩阵 Qci , j ，并输出 预测模体。3. 改进吉布斯采样算法寻找模体的方法本文提出的改进吉布斯采样寻找模体的方法是在原吉布斯采样算法寻找模体方法的基 础上，引入模体库来记录所有可能的预测模体，并在后选模体入库前，设置吉布斯采样算 法合理收敛性的成败检验、每个候选模体的

13、精确匹配计数和模糊匹配计数等三次验证，引 入命中精度来设置算法迭代收敛条件。新方法以克服原有算法局部收敛性、提高算法参数 设置灵活性和提高预测精度为设计目的。3.1 三次验证设计设待预测模体宽度为 M。吉布斯采样算法计数矩阵收敛后，在后选模体入库前要对其 进行三次验证，通过后才能入库。第一次验证：吉布斯采样算法的合理收敛性成败检验。 吉布斯采样收敛后，计数矩阵中各个位置上的碱基特异性各不相同。为了描述模体的保守性，希望各个位置上的碱基尽量在单值上集中，为此本文算法为吉布斯采样的成败设计了三项检验标准。1 平均特异性检验：检验是否存在一个非特异位。候选模体统计模型（用位置权重矩阵描 述的模体模型

14、）中至少存在一位，其上的 4 个碱基占位的可能性相等，即在概率矩阵的某 一列上的各个元素的出现概率大致相等。2 非特异位数检验：为保证保守性，收敛的模体模型中两个以上碱基表达的位数应尽可能 少。3 特定位特异性检验：为了对单值碱基收敛的特异性进行检验，对单值碱基收敛的情 况，也设置了检验条件。在概率矩阵中，表现为单列元素中的最大值必须大于特定位特异性域值 SingleSpec （本文取 0.8），才能达到单列特异收敛性。第二次验证：精确匹配验证。收敛模体元素与模体库中元素的精确匹配有关。通过上述吉布斯采样收敛性成败检验 的关卡后，需要进一步查看最后的收敛矩阵形成的待入库后选模体是否与现有模体库

15、中的 元素有精确匹配的情况。如果精确匹配，则表明在模体库中已有这个元素，不用重复添加 了。模体描述按照下列规则进行编码8：A = 1,0,0,0T ， C = 0,1,0,0TG = 0,0,1,0T ，T = 0,0,0,1T候选模体编码向量矩阵记为：（8）Vr1 ,Vr2 ,K,VrM 模体库中的每个元素均是按照式（8）的规则进行编码 10，设候选匹配模体为：CM i = Vr1 ,Vr2 ,K,VrM 模体库匹配模体编码矩阵为：则匹配度用二范数表示为：MCi = Vn1 ,Vn2 ,K,VnM Fiti =CM i MCi（9）如果式（9）等于零，则为精确匹配，并且在模体库精确匹配的模体

16、元素的精确匹配计数Cexact 上加 1，式（10）所示。第三次验证：模糊匹配验证。Cexact = Cexact + 1（10）收敛模体在模体库中元素的模糊匹配，和第二次验证的算法基本相同，然而验证规则 更为严格，范数值小于 2 为不能入库元素。为了体现模体的保守性，规定模体库中的每个 元素不允许有四个以上的匹配，否则被认为是重复匹配，即：Fit =CM MC =1 + 1 + 1 + 1 = 2同时，在模体库模糊匹配的模体元素的模糊计数 C fuzzy 上加 1，式（11）所示。C fuzzy = C fuzzy + 1（11）3.2 迭代终止条件的设置经过上述三次验证检验后反复进行迭代，

17、可以得到一张表明保守模体预测的模体库表，同时记录库中每个元素通过第 2 次和第 3 次验证的情况，即随机采样收敛后的命中情况。本文提出用命中精度因子来控制迭代终止的条件。设模体库中的元素个数为 Cmotif ，则命中精度因子 hit 定义为: hit = CCmotifexact + Cfuzzy（12）从式（12）可以看出，当命中精度因子小于一定的数值时，表明随机采样收敛的模体 在模体库中有很高的命中精度。换句话说，模体库中的元素基本上能够涵盖当前参数设置 下的收敛预测模体。模体库中元素对应的 Cexact 和C fuzzy 的值比较高，说明预测到该模体元 素的可能性比较大。3.3 模体库数

18、据的灵活设置策略大量生物学实验已经表明，模体并不全依赖于保守性，故模体库中匹配计数值较低的 其他元素也有较大的参考价值。此外，当模体库内元素存在错位重复的情况时，如 TTACGT 和 TACGGC 都同时出现在模体库中的时候，说明模体宽度需要调整。一种调整策略是结 合收敛的位置信息，调整为错位模体的合并宽度。只有当模体宽度重新调整后，分析找出 的预测模体时，发现符合生物学意义的模体的可能性才很大。因此，模体库数据需要灵活 设置。改进的吉布斯采样算法模体寻找算法如下： 算法 3：改进的吉布斯采样算法Begin：设置算法各参数：各关设置开关，假计数因子 Ppseudo，命中精度因子 hit 域值，

19、平均特异性因子 Special ，特定位特异性因子While（Conditions= true）For 吉布斯采样（详见算法 2）SingleSpec ，模体库清空，过关初始条件 Conditions=trueEnd根据位置权重矩阵进行吉布斯采样过关检验，If 不成功, 则重新吉布斯采样；Else 精确匹配过关；If 不成功, 回到吉布斯采样，同时更新精确匹配计数 Cexact + 1 ；Else 模糊匹配过关If 不成功，则回到吉布斯采样，同时更新模糊匹配计数 C fuzzy + 1 ；Else 后选模体入库，计算命中精度If（命中精度小于域值）Conditions=false直到位置权重矩

20、阵收敛。对模体库数据进行分析，列出预测模体。4. 实验结果与分析RSAT（Regulatory Sequence Analysis Tools）网站 (http:/rsat.ulb.ac.be/rsat/) 提供了许多 有效的模体寻找算法，其中吉布斯采样算法是基于位置权重矩阵改进得到，由 Andrew Neuwald 编写的代码。AlignACE10( http:/atlas.med.harvard.edu/) 也是一种基于吉布斯采样算法改进的查找模体的流行算法，它是通过设置一些控制参数来改进基本吉布斯采样算法。本文用这两种算法与我们提出的算法在单块模体识别和双块模体识别上进行算法的准确度 比

21、较。实验中设待预测模体宽度为 6。4.1 单块模体识别（1）仿真数据实验 为了测试本算法的可行性和有效性，我们人为设计了一组共调控基因，在数据中随机插入 G_box3碱基序列 CACGTG，设本文算法的置命中精度为 0.003，结果中匹配系数较 大的元素如表 1 所示。表 1 仿真数据预测模体库元素简表模体库元素精确计数模糊计数CACGTG1140TTGTCG3540TGTCGA3130ACGTGG9030GTGGAA267534.从表 1 中可以看到, 预测期望模体 CACGTG 在基因库中准确出现。RSAT 的结果报告 为: CACGTG。AlignACE 的结论是: CACGTG 0 4

22、46 0 MAP Score: 48.9315。三种算法的预 测准确率比较如表 2 所示。表 2 三种算法准确率比较测试算法预测序列数准确预测率统计模体RSAT14/14100%CACGTGAlignACE14/14100%CACGTG本文算法14/14100%CACGTG从表 2 中我们可以看到，本文算法和其它两种算法的预测准确率均达到 100%，都能 准确找到期望模体 CACGTG。但是从表 1 中也可以看到，由于仿真数据的随机性很大，有 一些匹配计数比较大的预测模体也进入了模体库，形成一定的预测干扰。（2）生物数据实验Spo0A1是一种转录因子，已被生物试验验证过，期望模体表达是：TGT

23、CGAA，是一 种在生长期起转录调节作用的重要的双功能调控器，在磷酸化后它的亲合力能增强。用本 文算法寻找此模体时，将命中精度因子设为 0.001(即 1000 倍命中)，实验结果如表 3 所示。表 3 生物实验数据模体库元素简表模体库元素精确计数模糊计数TGTCGA13020TCGAAA10390GTCGAA9140CGAAAA8510TTGTCG18890通过观察表 3 可以看到，错位重复的碱基序列在模体库中出现，如 GTCGAA，TGTCGA就有 5 个碱基（GTCGA）错位重复。我们推断，模体元素很可能不是设想的 6 个碱基对的 宽度, 而是 7 个或者 8 个,即可能是 TTGTCG

24、A 或是 TGTCGAA 或是 TTGTCGAA, 因为这 些模体中都包含了期望预测的 TGTCGAA。进一步的结论需要生物学实验验证。RSAT 的结果报告为:TTGTCGA 或 CGTCGAA 或 TGACAAA 或 TTTGTCG 或CACGGTG 等，不能准确作出判断。AlignACE 的结论是: TGTCGAA MAP Score: 33.3046三种算法的预测准确率如表 4 所示。表 4 单块模体识别实验算法准确率比较测试算法预测序列数预测准确率统计模体RSAT11/1478%CGTCGAAAlignACE14/14100%TGTCGAA本文算法14/14100%TGTCGAA从表

25、4 中可以看到，本文算法和 AlignACE 算法都能准确定位预测模体，并且在统计 模体上能准确匹配预测值。RSAT 的预测准确率只有 78%，难以作出准确预测。综上所述，当前主要流行算法一般都能以较高准确率识别到单块模体。4.2 双块模体识别对于双块模体的识别，我们直接采用生物数据来测试本文的算法。实验数据为：SigA1， 这是一种 RNA 聚合酶，主要调控 Sigma-43 因子，实质上是一个基因。统计期望模体是： TTGACA(-35)-N14-tgnTATAAT(-10)。将本文算法中的命中精度因子设定为 0.005，耗时 426 秒，共进行了 11110 次迭代后收敛的结果如表 5

26、所示。对于同一个实验数据，将命中精度定位 0.003，则耗时 978 秒，共进行了 21656 次迭代 后收敛的结果如表 6 所示。表 5 精度设定为 0.005 的双块模体实验结果表 6 精度设定为 0.003 的双块模体实验结果模体库元素精确计数模糊计数模体库元素精确计数模糊计数CTTGAC193339CTTGAC9290TGACAA46389TGACAA281239GGCTTG1189142GGCTTG76454TATAAT6854TATAAT28108CCTTGA114455CCTTGA61458.从表 5 和表 6 中可以看到，最后模体库的统计收敛趋势相当一致, 期望中的模体元素TT

27、GACA(-35)-N14-tgnTATAAT(-10)出现在模体库中。AlignACE 算法的结果是：TTCAAGTCAA 0 62 0TTTTTGTCAA 0 184 0TTTCTGTCAA 0 229 0MAP Score: 5.46077RSAT 的结果报告为: gttgacttga AAAGCC gacatgacaa表 7 是三种算法的统计准确率。表 7 双块模体实验准确率测试算法1 块预测2 块预测统计模体RSAT2518.75AAAGAC-CAAGTCAlignACE37.531.25TTATTA- ATTATA本文算法7556.25CTTGAC- CCTTGA提高双块模体识别的

28、准确率通常比较困难，当前流行算法（在假阳性较低的参数控制 情况下）的双块预测准确率一般不超过 50。从表 7 中我们可以看到，与 AlignACE 算法 和 RSAT 软件比较，本文算法寻找双块模体的准确度最高。本文算法依靠引入模体库来提 高命中率，在双块模体识别的准确率上有明显的改进，并且模体库的模体宽度数据设置灵 活。5. 讨论与结论（1）本文算法的随机收敛稳定性好2500200015001000系列1 系列2500012345图 1 算法稳定性示意图吉布斯采样算法是一个随机统计算法,最大的缺点是局部收敛。本算法将随机算法与统计特性结合起来，大大增强了算法的随机收敛稳定性，有效克服了基本算

29、法局部收敛的特 性。观察模体库可以看到，不仅收敛模体元素完全匹配相同，其匹配命中趋势也大致相当。 如图 1 中所示，这是对同一数据用本文算法两次实验精确匹配计数的结果，横轴表示对应 的每个模体元素。两色的柱状图显示两次实验后模体库中对应模体元素的精确匹配数据。 从图中可以看到其匹配趋势大致相当。（2）本文算法参数设置直观、灵活可控1）吉布斯采样过关参数的设置 用户可以用平均特异性验证、非特异位数验证和特定位特异性验证分别设置预测模体保守度在入库前验证的期望域值。在收敛的计数矩阵上描述预测模体的期望域值，使用比 较直观。2）采用命中过关测试控制模体库大小 本算法设置了精确匹配命中和模糊匹配命中两

30、种命中过关验证方式，使模体库中的元素不会出现海量增长的现象，并且通过命中计数可以为模体库元素提供定量分析的依据。 一般来说，命中数越大的模体在序列中的保守度越好。3）用命中精度控制迭代终止参数命中精度定量描述了模体库的整体命中情况，命中精度越高(即命中精度因子 hit 越小)，表明预测模体的模体库整体命中的可能性越大，模体库元素越能代表预测模体的整体情况。本算法用命中精度因子作为控制迭代终止的参数，可以灵活设置。4）参数开关设置 算法中所有参数设置都可以随时开启或关闭，对实验预测的灵活性有较大改进，同时也增强了算法的性能。（3）算法准确度较高本文算法与 RSAT 网站和 AlignACE 网站

31、的吉布斯采样算法比较，单块模体识别的准 确率相当，在双块模体的识别上准确率有较大的提高。综上所述，本文算法的识别精度较高，遗漏的预测数据较少，但自身也存在缺陷，如 模体库中数据冗余较大,预测假阳性较高，计算效率较低。未来的工作可以考虑进一步通过 改进数值计算方法来提高计算效率，通过对模体库数据进行二次挖掘优化，来减少冗余， 降低假阳性率。致谢本文研究工作得到国家自然科学基金面上项目（No. 60571047）、四川省学术与技术带 头人培养基金（No. 901008）、四川省应用基础项目（No. J13_75）和电子科技大学中青年 人才培养计划 (No. 601016) 资助，在此表示感谢。参考

32、文献：1 Thijs G, Marchal K, Lescot M, et al. A Gibbs Sampling method to detect over-represented motifs in upstream regions of coexpressed genes J. Journal of Computational Biology, 9(2), 2002, 447.2 Mark Robinson. Improving Computational Predictions of Cis-Regulatory Binding SitesC. PacificSymposium on

33、 Biocomputing, 11,2006, 391- 4023 Shane T. Jensen. BioOptimizer: a Bayesian scoring function approach to motif discoveryJ. Bioinfomatics ,20(10) , 2004, 1557-15644 谢雪英，孙啸，谢建明，陆祖宏. 基于信息量的调控元件预测方法J. 生物物理学报，19（4）, 2003,424-4305 Lawrence, C. E., Altschul, S. F., Boguski, M. S., Liu, J. S., Neuwald, A. F

34、. and Wootton, J. C. Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignmentJ. Science 262, 1993, 208-214.6 Bailey T L, Elkan C P. Fitting a mixture model by expectation maximization to discover motifs in biopolymersC.Proceedings of the Second International Conference on

35、Intelligent Systems for Molecular Biology. Menlo Park,California:AAAI Press, 1994, 28-367 Hertz G, Stormo G. Identifying DNA and protein patterns with statistically significant alignments of multiple sequences.JBioinformatics, 15(7), (1999), 5635778 Liu, J.S., Neuwald, A.F., and Lawrence, C.E. Bayes

36、ian Models for Multiple Local Sequence Alignment andGibbs Sampling StrategiesJ. Journal of the American Statistical Association, 90, 1995, 1156-1170.9 Neuwald, A.F., Liu, J.S. and Lawrence, C. E. Gibbs motif sampling: Detection of bacterial outer membrane protein repeatsJ. Protein Science, 4, 1995,

37、1618-1632,10Hughes J.D., Estep P.W., Tavazoie S, Church G.M. Computational identification of cis-regulatory elements associated with groups of functionally related genes in Sacchaomyces cerevisiae J. J. Mol. Biol, 296(5),2000, 1205-1214.11 Zhang, Y., Liu, X. S., Liu, Q. R. and Wei, L. Genome-wide in

38、 silico identification and analysis of cis natural antisense transcripts (cis-NATs) in ten speciesJ. Nucleic Acids Res., 34(12), 2006, 3465 - 347512 吴 昕等. 基因调控元件的计算机识别和基因调控网络构件C. 北京:中国科协第 81 次青年科学家论坛，生物信息学若干前沿问题的探讨，2003，92 - 10813 Cyntbia Gibas & PerJambeck 著，孙超等译.生物信息学中的计算机技术M. 北京: 中国电力出版社,2002 年14

39、 Keich, U., Pevzner, P.A. Finding motifs in the twilight zoneJ. Bioinformatics, 18(10), 2002, 13741381 15 Gordon L., Chervonenkis A., Gammerman A., et al. Sequence alignment kernel for recognition of promoterregionsJ. Bioinformatics, 19(15), 2003, 1964 - 1971.An improved Gibbs Sampling Method for Mo

40、tif DiscoveryKuang Bin，Rao Nini，Han Fengjun，Yuan ZuoyongUniversity of Electronic Science and Technology of China School of Life Science andTechnology （610054）AbstractMany motif-finding programs have been developed but no program is clearly superior in all situations. In this paper, an improved Gibbs

41、 sample algorithm is proposed to discover motif according to the motif model of PWM (Position Weight Matrix). The improved approach can overcome the local convergence of Gibbs sample algorithm and can control intuitively the conservation for motif discovery. The motif base concept is adapted to incr

42、ease the flexibility and the accuracy for motif discovery by analysing motif data base. The simulated data and the verified biologcal data are used to test the feasibility and effectiveness of improved approach. Compared with other common algorithms, our algorithm raise effectively the accuracy, flexibility and stability for the motif discovery.Keywords: Gibbs sampling; motif; PWM; Motif discovery