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

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

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

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

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

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

6、問(wèn)題實(shí)例，并且相對(duì)于主流的近似算法(MEME、AlignACE和VINE)具有更好的識(shí)別準(zhǔn)確率。
　　第三部分研究了大字符集(蛋白質(zhì)序列)上的模體發(fā)現(xiàn)問(wèn)題。針對(duì)現(xiàn)有的模體stem搜索算法存在的stem表示不精確、通配符冗余、搜索效率低等問(wèn)題，進(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)問(wèn)題。鑒于已有的模體發(fā)現(xiàn)算法難以高效地處理完整的ChIP-seq數(shù)據(jù)集，提出了一種新的基于詞頻統(tǒng)計(jì)的模體發(fā)現(xiàn)算法MCES：通過(guò)挖掘和合并出現(xiàn)頻率較高的子串進(jìn)行模體預(yù)測(cè)；為了處理更大的數(shù)據(jù)集，設(shè)計(jì)了挖掘子串的基于MapReduce的分布