生物網(wǎng)絡(luò)中大模體識(shí)別算法的研究.pdf

1、近年來，隨著生物技術(shù)，尤其是高通量技術(shù)的發(fā)展，生物網(wǎng)絡(luò)數(shù)據(jù)有了顯著的增長(zhǎng)，出現(xiàn)了很多的生物網(wǎng)絡(luò)數(shù)據(jù)庫(kù)，包括蛋白質(zhì)反應(yīng)網(wǎng)絡(luò)，新陳代謝網(wǎng)絡(luò)，基因調(diào)控網(wǎng)絡(luò)，神經(jīng)網(wǎng)絡(luò)等，如何從這些浩瀚的生物網(wǎng)絡(luò)中識(shí)別出與功能相關(guān)的結(jié)構(gòu)是當(dāng)前的一個(gè)研究熱點(diǎn)，而如何從生物網(wǎng)絡(luò)識(shí)別出模體是研究生物網(wǎng)絡(luò)結(jié)構(gòu)和功能的關(guān)鍵一步。模體是指在某個(gè)網(wǎng)絡(luò)的多個(gè)不同部分出現(xiàn)的某一相互連接的子結(jié)構(gòu)，其表達(dá)程度明顯高于在隨機(jī)網(wǎng)絡(luò)中的表達(dá)。
　　 目前的模體識(shí)別方法主要有窮舉法和

2、抽樣法，前者試圖找出給定真實(shí)生物網(wǎng)絡(luò)中指定大小的所有模體，然而隨著子圖的增大，候選子圖的數(shù)量呈爆炸性增長(zhǎng)，識(shí)別模體所需的時(shí)間急劇增長(zhǎng)，同時(shí)，內(nèi)存空間也呈爆炸性增長(zhǎng)，程序很快因內(nèi)存空間耗盡而崩潰，所以窮舉模體識(shí)別方法只能識(shí)別小規(guī)模和中等規(guī)模的模體，面對(duì)稍大規(guī)模的模體無能為力。針對(duì)此問題，抽樣模體識(shí)別方法應(yīng)運(yùn)而生，抽樣法降低了窮舉法因?yàn)楸闅v訪問子圖空間而產(chǎn)生的高復(fù)雜度，該類方法部分訪問子圖空間，顯著地降低了時(shí)間復(fù)雜度和空間復(fù)雜度，但由于難以

3、等比例抽樣，產(chǎn)生了抽樣偏置，以及調(diào)整該偏置而產(chǎn)生的額外計(jì)算復(fù)雜度，同時(shí)抽樣模體識(shí)別方法還存在抽樣概率難以精確分配的缺陷。
　　 針對(duì)這些問題，本文在傳統(tǒng)的模體識(shí)別方法上進(jìn)行了研究和拓展，首先提出了一種基于劃分的子圖搜索算法（Partition based SubGraph Finder，PSGF），該算法能夠唯一，不遺漏，高效地搜索給定真實(shí)生物網(wǎng)絡(luò)中指定大小的所有子圖，PSGF基于劃分的思想，即任意兩顆搜索樹中的子圖通過全局劃分

4、頂點(diǎn)來加以區(qū)分，同一棵搜索樹中不同子樹中的子圖通過局部劃分頂點(diǎn)來加以區(qū)分，從而能夠?qū)崿F(xiàn)不重復(fù)性。PSGF在運(yùn)行過程中僅僅在內(nèi)存中維持一條搜索樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑，所以具有較小的內(nèi)存使用量。本文將PSGF應(yīng)用到模體識(shí)別框架中，產(chǎn)生了一種新的窮舉模體識(shí)別方法--基于劃分的模體識(shí)別算法（Partiton basedNetwork Motif Finder，PNMF），在LIETZ數(shù)據(jù)集上成功識(shí)別了中等規(guī)模的模體，與同類方法相比，具有較小

5、的時(shí)間復(fù)雜度和空間復(fù)雜度。針對(duì)抽樣模體識(shí)別方法概率值難以精確分配的缺陷，本文還提出了一種基于度的概率分配算法（Degree based Probability AssignAlgorithm，DPAA）。相比于目前的隨機(jī)分配方法，DPAA基于真實(shí)網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)的本質(zhì)特征，具有較小的抽樣偏置。
　　 UETZ數(shù)據(jù)集和E.COLI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的兩種模體識(shí)別方法能有效地識(shí)別真實(shí)生物網(wǎng)絡(luò)中的模體，相比于目前的方法，具