生物概率網(wǎng)絡(luò)中頻繁模體高效挖掘的研究.pdf

1、近年來，隨著生物技術(shù)的發(fā)展，出現(xiàn)了很多生物網(wǎng)絡(luò)數(shù)據(jù)，生物網(wǎng)絡(luò)數(shù)據(jù)規(guī)模有了顯著地增加，包括蛋白質(zhì)作用網(wǎng)絡(luò)，新陳代謝網(wǎng)絡(luò)，基因調(diào)控網(wǎng)絡(luò)等。如何從這些數(shù)據(jù)中挖掘出與功能相關(guān)的結(jié)構(gòu)是目前的一個研究熱點。模體是指在某個網(wǎng)絡(luò)的多個不同部分出現(xiàn)的某一相互連接的子結(jié)構(gòu)，其表達程度明顯高于在隨機網(wǎng)絡(luò)中的表達。如何從生物網(wǎng)絡(luò)中挖掘出模體是研究生物體進化和生物網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)鍵一步。目前的模體識別方法主要是針對確定圖，但是研究得到的生物網(wǎng)絡(luò)數(shù)據(jù)通常帶有不可避免的

2、實驗誤差或噪聲數(shù)據(jù)，同時，生物進化過程本身也是一種動態(tài)變化的過程。因此生物概率網(wǎng)絡(luò)的研究更具生物意義。
　　在目前已有研究中，主要采用可能世界模型，即將每個概率予圖映射為2n個可能的圖實例，其中n為子圖邊數(shù)。隨著模體規(guī)模的增大，枚舉的圖規(guī)模將急劇增加，算法的復(fù)雜度呈指數(shù)級增長?；陔娐纺M法判別概率子圖同構(gòu)算法，避免了使用傳統(tǒng)算法中的可能世界模型，將子圖同構(gòu)的拓撲比對轉(zhuǎn)化成節(jié)點電壓序列的比較。但是因需要對每個節(jié)點進行全激勵，效率較

3、低。生物概率網(wǎng)絡(luò)模體識別分為三部分，概率子圖搜索、概率頻繁模式識別和模體統(tǒng)計意義計算。但隨著模體節(jié)點數(shù)的增加，對應(yīng)的子圖數(shù)量也急劇增加，從而使模體識別在時間和空間消耗上都超出了單機的處理能力。
　　針對這些問題，本文的主要工作如下:
　　在電路模擬法的概率子圖同構(gòu)算法(Probability Subgraph Isomorphic based on CircuitSimulation，PSI-CS)基礎(chǔ)上，基于在兩個概率同構(gòu)

4、子圖對應(yīng)的伴隨電路中，對應(yīng)節(jié)點在相同全激勵下會產(chǎn)生對應(yīng)相似的節(jié)點電壓序列的思想，提出單節(jié)點全激勵的概率子圖同構(gòu)算法(Probability Subgraph Isomorphic based on Single Node with Complete Excitation, PSI-SNCE),該算法通過添加一個參考節(jié)點并施加全激勵，不需要對子圖中的每個節(jié)點進行全激勵計算節(jié)點電壓序列，從而使求解方程組的次數(shù)減少約n倍（n為子圖的頂點數(shù)），

5、效率得到大大提高。
　　在非樹形子圖枚舉算法(Enumerate Non-tree Subgraph，ESN)和基于劃分的非樹形子圖搜索算法（Partition-based Non-tree Subgraph Search，PNSS）基礎(chǔ)上，提出一種適合于并行化環(huán)境的非樹形子圖搜索算法:基于序號的非樹形子圖搜索算法(Order-based Non-treeSubgraph Search，ONSS)，能夠在保證子圖搜索的唯一性、不遺

6、漏性及不重復(fù)性的基礎(chǔ)上，將任務(wù)均衡分布到并行計算節(jié)點上，效率得到顯著提高。
　　聚類過程是概率頻繁模式識別算法中計算復(fù)雜度最高的部分，為此提出聚類過程的并行化方案，在迭代運算較優(yōu)的Spark集群環(huán)境中并行化實現(xiàn)。在概率頻繁模式識別的聚類過程中，采用PSI-SNCE算法計算兩概率子圖是否同構(gòu)，若同構(gòu)，則聚成一類，若不同構(gòu)，則保持不變。最后將滿足要求的少量概率頻繁模式進行模體統(tǒng)計意義計算，得出P-Value值，即可得出概率模體。