生物概率網絡中頻繁模體高效挖掘的研究.pdf

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

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

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

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

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

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