利用計算機吉布斯采樣尋找基因中的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，但效果不是很明顯。隨著越來越多的序列，該程序將找到解決方案更快，并且因此將具有較少的迭代結束。這抵消了較重的每個迭代的工作。