利用計算機吉布斯采樣尋找基因中的motif

李 琦

（香港中文大學(xué)，香港 999077）

1 算法描述

1.1 模序發(fā)現(xiàn)與貪婪算法[對照組]

我們試圖使用了貪心算法，它最初叫motif_finder2.py。它在DNA的第一兩個序列執(zhí)行窮舉搜索，以找到最好的升聚體基序[1]。然后反復(fù)從各剩余序列的添加一個1-聚體。在每次迭代中，我們試圖每個L-mer的序列中，將它添加到配置文件矩陣來計算分?jǐn)?shù)找到最好的1-聚體。貪婪算法的敏感地依賴序列在通過了訂單上的結(jié)果。而且，如果失敗的第一多個序列，這將是最有可能完全失敗。因此，我們只將貪心算法作為對照組。

1.2 模序發(fā)現(xiàn)與Gibbs抽樣[實驗組]

限定ICPC作為每列信息內(nèi)容，ml為基序長度，SC作為序列計數(shù)和SL作為序列長度。我們試圖Gibbs抽樣稱為motif_finder.py其中找到從每個序列的最相互類似長度毫升子（可能基序）[2]。說穿了，它試圖找到可能的主題的起始部位在每個最大化的結(jié)果位置權(quán)重矩陣的信息內(nèi)容的分?jǐn)?shù)序列。我們的算法如下課堂講授的標(biāo)準(zhǔn)Gibbs抽樣方法。我們首先挑選在每個序列的隨機位置，說（S1，S2，…s_sc）。然后，對于每一次迭代，我們選擇一個隨機序列i到替換和計算所述序列中的位置權(quán)重矩陣中除了i以外。對于序列i各自候選部位X，我們計算Q_x和P_x，其中Q_x給出生成根據(jù)x到PWM的概率，和P_x給出了根據(jù)背景模型生成x的概率（均勻分布的，即0.25每個）。在所有候選網(wǎng)站，我們挑來更新序列我開始網(wǎng)站的最佳位置。

在每100次迭代結(jié)束時，我們比較ICPC與以前ICPC，如果ICPC沒有太大變化，我們選擇新的隨機位置。我們設(shè)定的最大迭代是700和最大隨機的起始位置為70（即，我們將運行Gibbs抽樣的700倍最大每輪隨機位置的，最大一輪的隨機位置的是70），在所有這些，我們挑最好的結(jié)果的位置。

2 圖形性能評價

我們的數(shù)據(jù)有三個變量我們的數(shù)據(jù)，每列的信息內(nèi)容（ICPC），主題長度（毫升）和序列長度（SL）。對于每個變量，我們將有四個圖來表示我們的算法評估性能。每組圖表將顯示熵的措施，重疊點，位置重疊率和運行時間。

2.1 信息內(nèi)容變化（1，1.5，2），而其他參數(shù)在默認(rèn)（毫升=8，SC=10，SL=500）

2.2 基序長度變化（6，7，8），而其它的參數(shù)是在默認(rèn)（ICPC=2，SC=10，SL=500）

2.3 順序計數(shù)變化（5，10，20），而其它的參數(shù)是在默認(rèn)（ICPC=2，SL=10，SC=500）：變化，而其他參數(shù)在默認(rèn)

3 評估階段觀察

3.1 對于各種ICPC值，我們有以下看法

相對熵ICPC的增加而降低。這是因為我們更加肯定對每個位置應(yīng)該是什么，如果ICPC高。從而我們可以看到該圖中，標(biāo)準(zhǔn)誤差為1.5比1和2，因為對于ICPC=1.5的算法相對較大有時可能正確找到基序，但有時不能，不像ICPC=1或2，其中的算法要么大多無法找到在主題或大部分正確定位的主題。

運行時間為ICPC=1相對較小，并且ICPC=2比ICPC=1.5。這在一定程度上預(yù)期的，因為無論是對ICPC=1或ICPC=2，算法預(yù)計表現(xiàn)不佳或好，所以更少的時間中檢查，如果數(shù)據(jù)“會聚”。由于差異比較小，它可能只是偶然。

3.2 對于各種序列數(shù)，我們有以下看法

相對熵作為序列數(shù)的增加而降低。如果給定的多個序列，該方案將能夠找到一個更精確的中間體溶液，在相同數(shù)量的迭代。采取貪婪算法為例：當(dāng)計算其第一中間溶液貪婪算法將采取只有前兩個序列考慮。因此，它會卡死在局部最優(yōu)容易，而將失敗尋找全局最優(yōu)的大部分時間。隨著越來越多的序列，該計劃將不太可能會卡在局部最優(yōu)，即使是這樣，它就能更快地跳出來。

運行時間是比較小了。我們可以觀察到一個抵消一個類似于在3.2，但效果不是很明顯。隨著越來越多的序列，該程序?qū)⒄业浇鉀Q方案更快，并且因此將具有較少的迭代結(jié)束。這抵消了較重的每個迭代的工作。