利用计算机吉布斯采样寻找基因中的motif

李 琦

（香港中文大学，香港 999077）

1 算法描述

1.1 模序发现与贪婪算法[对照组]

我们试图使用了贪心算法，它最初叫motif_finder2.py。它在DNA的第一两个序列执行穷举搜索，以找到最好的升聚体基序[1]。然后反复从各剩余序列的添加一个1-聚体。在每次迭代中，我们试图每个L-mer的序列中，将它添加到配置文件矩阵来计算分数找到最好的1-聚体。贪婪算法的敏感地依赖序列在通过了订单上的结果。而且，如果失败的第一多个序列，这将是最有可能完全失败。因此，我们只将贪心算法作为对照组。

1.2 模序发现与Gibbs抽样[实验组]

限定ICPC作为每列信息内容，ml为基序长度，SC作为序列计数和SL作为序列长度。我们试图Gibbs抽样称为motif_finder.py其中找到从每个序列的最相互类似长度毫升子（可能基序）[2]。说穿了，它试图找到可能的主题的起始部位在每个最大化的结果位置权重矩阵的信息内容的分数序列。我们的算法如下课堂讲授的标准Gibbs抽样方法。我们首先挑选在每个序列的随机位置，说（S1，S2，…s_sc）。然后，对于每一次迭代，我们选择一个随机序列i到替换和计算所述序列中的位置权重矩阵中除了i以外。对于序列i各自候选部位X，我们计算Q_x和P_x，其中Q_x给出生成根据x到PWM的概率，和P_x给出了根据背景模型生成x的概率（均匀分布的，即0.25每个）。在所有候选网站，我们挑来更新序列我开始网站的最佳位置。

在每100次迭代结束时，我们比较ICPC与以前ICPC，如果ICPC没有太大变化，我们选择新的随机位置。我们设定的最大迭代是700和最大随机的起始位置为70（即，我们将运行Gibbs抽样的700倍最大每轮随机位置的，最大一轮的随机位置的是70），在所有这些，我们挑最好的结果的位置。

2 图形性能评价

我们的数据有三个变量我们的数据，每列的信息内容（ICPC），主题长度（毫升）和序列长度（SL）。对于每个变量，我们将有四个图来表示我们的算法评估性能。每组图表将显示熵的措施，重叠点，位置重叠率和运行时间。

2.1 信息内容变化（1，1.5，2），而其他参数在默认（毫升=8，SC=10，SL=500）

2.2 基序长度变化（6，7，8），而其它的参数是在默认（ICPC=2，SC=10，SL=500）

2.3 顺序计数变化（5，10，20），而其它的参数是在默认（ICPC=2，SL=10，SC=500）：变化，而其他参数在默认

3 评估阶段观察

3.1 对于各种ICPC值，我们有以下看法

相对熵ICPC的增加而降低。这是因为我们更加肯定对每个位置应该是什么，如果ICPC高。从而我们可以看到该图中，标准误差为1.5比1和2，因为对于ICPC=1.5的算法相对较大有时可能正确找到基序，但有时不能，不像ICPC=1或2，其中的算法要么大多无法找到在主题或大部分正确定位的主题。

运行时间为ICPC=1相对较小，并且ICPC=2比ICPC=1.5。这在一定程度上预期的，因为无论是对ICPC=1或ICPC=2，算法预计表现不佳或好，所以更少的时间中检查，如果数据“会聚”。由于差异比较小，它可能只是偶然。

3.2 对于各种序列数，我们有以下看法

相对熵作为序列数的增加而降低。如果给定的多个序列，该方案将能够找到一个更精确的中间体溶液，在相同数量的迭代。采取贪婪算法为例：当计算其第一中间溶液贪婪算法将采取只有前两个序列考虑。因此，它会卡死在局部最优容易，而将失败寻找全局最优的大部分时间。随着越来越多的序列，该计划将不太可能会卡在局部最优，即使是这样，它就能更快地跳出来。

运行时间是比较小了。我们可以观察到一个抵消一个类似于在3.2，但效果不是很明显。随着越来越多的序列，该程序将找到解决方案更快，并且因此将具有较少的迭代结束。这抵消了较重的每个迭代的工作。