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

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

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

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