生物概率網(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)是目前的一個(gè)研究熱點(diǎn)。模體是指在某個(gè)網(wǎng)絡(luò)的多個(gè)不同部分出現(xiàn)的某一相互連接的子結(jié)構(gòu)，其表達(dá)程度明顯高于在隨機(jī)網(wǎng)絡(luò)中的表達(dá)。如何從生物網(wǎng)絡(luò)中挖掘出模體是研究生物體進(jìn)化和生物網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)鍵一步。目前的模體識(shí)別方法主要是針對(duì)確定圖，但是研究得到的生物網(wǎng)絡(luò)數(shù)據(jù)通常帶有不可避免的

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

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

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

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

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