頻繁子圖挖掘算法及其在生物網(wǎng)絡(luò)中的應(yīng)用.pdf

1、人類(lèi)基因組計(jì)劃的基本完成表明后基因組時(shí)代的到來(lái)。人類(lèi)積累的大量的生物信息數(shù)據(jù)為揭開(kāi)生命奧秘提供了數(shù)據(jù)基礎(chǔ)，生物學(xué)研究的熱點(diǎn)由對(duì)細(xì)胞內(nèi)個(gè)別基因或蛋白質(zhì)功能的局部性研究，轉(zhuǎn)移到以細(xì)胞內(nèi)全部的基因、蛋白質(zhì)及代謝產(chǎn)物為整體對(duì)象的系統(tǒng)研究。對(duì)基因調(diào)控網(wǎng)絡(luò)、蛋白質(zhì)相互作用網(wǎng)絡(luò)、代謝路徑網(wǎng)絡(luò)等結(jié)構(gòu)及功能模塊的檢測(cè)技術(shù)的研究，逐步把分子生物學(xué)推入系統(tǒng)生物學(xué)時(shí)代?；蚺c蛋白質(zhì)通過(guò)網(wǎng)狀的相互作用產(chǎn)生更高一級(jí)的功能模塊，所以，通過(guò)數(shù)學(xué)建模來(lái)設(shè)計(jì)有效的算法，在

2、生物網(wǎng)絡(luò)中進(jìn)行功能模塊的挖掘和分析，將有助于更好地研究生物體自身的功能和不同生物體之間的進(jìn)化關(guān)系，為分析理解生命基本規(guī)律提供依據(jù)。 本文對(duì)基于圖論的經(jīng)典頻繁子圖挖掘算法進(jìn)行了系統(tǒng)的研究和全面的總結(jié)，在此基礎(chǔ)上提出了一種新的挖掘頻繁子圖的算法，該算法包含子圖的搜索算法及同構(gòu)分類(lèi)算法。對(duì)子圖搜索問(wèn)題，提出了環(huán)分布的概念，并構(gòu)造了基于環(huán)分布的子圖搜索算法ESR(EnumerateSubgraphs based on Ring)；對(duì)子圖

3、同構(gòu)問(wèn)題，利用度序列和特征值構(gòu)造了兩種算法，分別用于對(duì)有向圖和無(wú)向圖的同構(gòu)判別；利用同構(gòu)算法對(duì)搜索出的子圖進(jìn)行同構(gòu)分類(lèi)，根據(jù)分類(lèi)結(jié)果得到頻繁子圖。當(dāng)網(wǎng)絡(luò)規(guī)模比較大時(shí)，子圖數(shù)量非常龐大，同構(gòu)分類(lèi)的工作量很大，為此又提出了隨機(jī)歸類(lèi)算法和Hamilton子圖的挖掘算法，以減少同構(gòu)分類(lèi)的運(yùn)算量。隨機(jī)歸類(lèi)算法是通過(guò)從子圖集中隨機(jī)地抽取一定數(shù)量的子圖進(jìn)行同構(gòu)分類(lèi)，是一種近似的算法；Hamilton子圖的挖掘算法旨在挖掘特定類(lèi)型(具有Hamilton