基于對稱子圖和概率分層的網(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)系的整體表達(dá)，是研究生物系統(tǒng)進(jìn)化的關(guān)鍵。網(wǎng)絡(luò)模體作為相互作用網(wǎng)絡(luò)的基本組成單元，對蛋白質(zhì)進(jìn)化有重要影響。模體發(fā)現(xiàn)也逐漸成為蛋白質(zhì)組學(xué)研究的熱點(diǎn)問題。
　　由于網(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ò)進(jìn)行對稱壓縮，同時在子圖搜索的過程中，對部分具有相同拓?fù)浣Y(jié)構(gòu)的子圖歸類，減少了子圖同構(gòu)過程的時間消耗。通過在不同蛋白質(zhì)相互作用網(wǎng)絡(luò)的實(shí)驗表明，MDBS提高了模體發(fā)現(xiàn)的時間效率。
　　抽樣子圖搜索減少了模體發(fā)現(xiàn)過程中的計算量，但同時抽樣算法不可避免的抽樣誤差影響了結(jié)果的準(zhǔn)確性，是抽樣網(wǎng)絡(luò)模體發(fā)現(xiàn)中主要存在的問題。本文從提高抽樣方法的穩(wěn)定性和精確度出發(fā)，提出一種新型的基于節(jié)點(diǎn)概率分層的抽樣模體發(fā)現(xiàn)算法LaRand-ESU。實(shí)驗

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