基于對稱子圖和概率分層的網(wǎng)絡(luò)模體發(fā)現(xiàn)算法研究.pdf

1、隨著人類基因組學(xué)的研究已經(jīng)取得巨大成就，生命科學(xué)研究重心已經(jīng)從揭示生命遺傳信息轉(zhuǎn)移到分子整體水平對功能的影響，大量的生物網(wǎng)絡(luò)數(shù)據(jù)也隨之涌現(xiàn)。蛋白質(zhì)相互作用網(wǎng)絡(luò)是蛋白質(zhì)相互作用關(guān)系的整體表達，是研究生物系統(tǒng)進化的關(guān)鍵。網(wǎng)絡(luò)模體作為相互作用網(wǎng)絡(luò)的基本組成單元，對蛋白質(zhì)進化有重要影響。模體發(fā)現(xiàn)也逐漸成為蛋白質(zhì)組學(xué)研究的熱點問題。
　　由于網(wǎng)絡(luò)模體發(fā)現(xiàn)計算非常復(fù)雜，關(guān)于網(wǎng)絡(luò)模體發(fā)現(xiàn)算法的研究大多是基于提高時間效率。本文在基于蛋白質(zhì)相互作用

2、網(wǎng)絡(luò)的精確網(wǎng)絡(luò)模體發(fā)現(xiàn)算法的研究中，提出了旨在改善算法時間效率和抽樣算法精確度的模體發(fā)現(xiàn)新方法。
　　研究表明，網(wǎng)絡(luò)中存在的對稱結(jié)構(gòu)會造成計算的冗余。因此本文提出了模體發(fā)現(xiàn)方法MDBS(MotifDetectionbasedonBasicSymmetricSubgraphs)，該方法利用基本對稱子圖BSS(BasicSymmetricSubgraph)性質(zhì)來減少模體發(fā)現(xiàn)過程的冗余計算。MDBS根據(jù)BSS性質(zhì)挖掘網(wǎng)絡(luò)中的基本對稱子圖

3、，對網(wǎng)絡(luò)進行對稱壓縮，同時在子圖搜索的過程中，對部分具有相同拓撲結(jié)構(gòu)的子圖歸類，減少了子圖同構(gòu)過程的時間消耗。通過在不同蛋白質(zhì)相互作用網(wǎng)絡(luò)的實驗表明，MDBS提高了模體發(fā)現(xiàn)的時間效率。
　　抽樣子圖搜索減少了模體發(fā)現(xiàn)過程中的計算量，但同時抽樣算法不可避免的抽樣誤差影響了結(jié)果的準(zhǔn)確性，是抽樣網(wǎng)絡(luò)模體發(fā)現(xiàn)中主要存在的問題。本文從提高抽樣方法的穩(wěn)定性和精確度出發(fā)，提出一種新型的基于節(jié)點概率分層的抽樣模體發(fā)現(xiàn)算法LaRand-ESU。實驗

4、分析發(fā)現(xiàn)子圖搜索結(jié)果集中節(jié)點頻率跟節(jié)點的鄰居節(jié)點度數(shù)之和(SumofNeighbors'Degrees，SoNDS)和節(jié)點的邊聚集系數(shù)之和(SumofEdgeClusteringCoefficient，SoECC)相關(guān)。結(jié)合節(jié)點這兩個特征，LaRand-ESU對網(wǎng)絡(luò)中所有節(jié)點進行分層，對不同層次的節(jié)點賦不同的抽樣概率，在子圖搜索過程中通過比較隨機概率和節(jié)點的層次概率值進行節(jié)點擴充。最后通過在真實蛋白質(zhì)相互作用網(wǎng)絡(luò)的實驗表明，這種方法提高