生物序列模體發(fā)現(xiàn)算法研究.pdf

1、模體發(fā)現(xiàn)是在給定的序列集合中找到過表達(dá)的序列模式，對生物序列中定位有意義的序列片斷起著非常重要的作用，比如在DNA序列中識別轉(zhuǎn)錄因子結(jié)合位點(diǎn)和在蛋白質(zhì)序列中識別短的線性模體。轉(zhuǎn)錄因子控制著靶基因的轉(zhuǎn)錄起始和轉(zhuǎn)錄效率?；蛏嫌闻c轉(zhuǎn)錄因子相結(jié)合的特定DNA序列稱為轉(zhuǎn)錄因子結(jié)合位點(diǎn)，對它的精確定位有助于理解基因的表達(dá)調(diào)控機(jī)制。線性模體是蛋白質(zhì)序列中具有特定功能的序列片斷，負(fù)責(zé)著蛋白質(zhì)交互的調(diào)節(jié)，對許多調(diào)控過程都起著重要的作用，比如信號傳導(dǎo)、蛋

2、白質(zhì)運(yùn)輸和翻譯后修飾。
　　植入(l,d)模體發(fā)現(xiàn)(Planted(l,d)motif search,PMS)是模體發(fā)現(xiàn)領(lǐng)域中一個廣為接受的問題模型，求解PMS是計算機(jī)科學(xué)和生物信息學(xué)中的挑戰(zhàn)問題。模體是未知的，并以退化的形式出現(xiàn)在序列中，也即模體實(shí)例(模體的出現(xiàn))并不是模體的一份精確拷貝，而是與模體在某些位置上存在著差異。相對于DNA啟動子序列，蛋白質(zhì)序列和染色質(zhì)免疫共沉淀測序(Chromatin Immunoprecipita

3、tion-Sequencing，ChIP-seq)序列又分別從大字符集和大數(shù)據(jù)集方面對求解PMS帶來了新的挑戰(zhàn)。本論文針對不同類型生物序列數(shù)據(jù)集的特點(diǎn)以及現(xiàn)有算法的不足，提出新的模體發(fā)現(xiàn)算法，以進(jìn)一步提高模體發(fā)現(xiàn)的時間性能和識別準(zhǔn)確率。具體工作概括為以下四個部分：
　　第一部分研究了DNA啟動子序列中(l，d)模體發(fā)現(xiàn)的精確算法。針對現(xiàn)有識別(l，d)模體的精確算法存在的計算量大或存儲空間高、難以識別微弱信號模體等問題，提出了一種

4、新的基于模式驅(qū)動的精確算法PairMotif：分析和描述了如何由一對l-mer(長為l的字符串)生成候選模體；通過估計候選模體的數(shù)量，從輸入序列集中選擇參考序列，能有效地減少候選模體的數(shù)量；設(shè)計了兩種過濾待掃描l-mer的規(guī)則，有助于加速模體驗(yàn)證。相對于之前的幾個精確算法，PairMotif需要更少的存儲空間，能夠更快速地求解大多數(shù)PMS問題實(shí)例，而且能夠在10個小時內(nèi)求解其它算法難以求解的(27,9)問題實(shí)例。
　　第二部分研究

5、了DNA啟動子序列中(l，d)模體發(fā)現(xiàn)的近似算法。鑒于現(xiàn)有的模體發(fā)現(xiàn)算法要么花費(fèi)巨量的時間輸出最優(yōu)的結(jié)果，要么在短時間內(nèi)完成計算但常常陷入局部最優(yōu)，提出了一種新的基于模式驅(qū)動的近似算法PairMotif+：依據(jù)概率分析和統(tǒng)計的方法，從輸入序列中獲取了若干l-mer對，使得其中含有一個或多個模體實(shí)例對；設(shè)計了一種高準(zhǔn)確率的近似求精l-mer對的策略，避免了大部分候選模體的驗(yàn)證。PairMotif+能夠在普通PC機(jī)上于1小時內(nèi)求解各種PMS

6、問題實(shí)例，并且相對于主流的近似算法(MEME、AlignACE和VINE)具有更好的識別準(zhǔn)確率。
　　第三部分研究了大字符集(蛋白質(zhì)序列)上的模體發(fā)現(xiàn)問題。針對現(xiàn)有的模體stem搜索算法存在的stem表示不精確、通配符冗余、搜索效率低等問題，進(jìn)行了如下工作：建立了一種基于正則表達(dá)式的stem表示方式，使stem的表示更為精確；提出了一種生成候選stem的方法，使得stem中不含冗余的通配符；結(jié)合stem表示和stem生成方法，提出

7、了一種高效的stem搜索算法StemFinder，比現(xiàn)有算法具有更高的搜索效率，并且輸出了更少的能夠覆蓋所有(l,d)模體的stem。
　　第四部分研究了大數(shù)據(jù)集(ChIP-seq數(shù)據(jù)集)上的模體發(fā)現(xiàn)問題。鑒于已有的模體發(fā)現(xiàn)算法難以高效地處理完整的ChIP-seq數(shù)據(jù)集，提出了一種新的基于詞頻統(tǒng)計的模體發(fā)現(xiàn)算法MCES：通過挖掘和合并出現(xiàn)頻率較高的子串進(jìn)行模體預(yù)測；為了處理更大的數(shù)據(jù)集，設(shè)計了挖掘子串的基于MapReduce的分布