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

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

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

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

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

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