有關(guān)網(wǎng)絡(luò)模糊motif及其精確化算法的研究.pdf

1、隨著生物信息學(xué)研究進(jìn)入后基因組時(shí)代，產(chǎn)生了大量富有生物意義的復(fù)雜網(wǎng)絡(luò)，這促使許多研究者從系統(tǒng)生物學(xué)的角度研究該類網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特點(diǎn)和網(wǎng)絡(luò)中局部結(jié)構(gòu)與整體功能之間的關(guān)系等，因此，網(wǎng)絡(luò) motif的概念應(yīng)運(yùn)而生。從提出到現(xiàn)在有關(guān)網(wǎng)絡(luò)motif的識(shí)別算法層出不窮，這些算法大多都需要窮舉網(wǎng)絡(luò)中的子圖、生成一定數(shù)目的隨機(jī)網(wǎng)絡(luò)以及進(jìn)行圖的同構(gòu)性判斷，這使得它們識(shí)別頂點(diǎn)數(shù)和連邊數(shù)較小的網(wǎng)絡(luò)中存在的motif時(shí)能夠得出有效解，但隨著待識(shí)別的網(wǎng)絡(luò)moti

2、f和網(wǎng)絡(luò)規(guī)模的增加，大多數(shù)的算法都面臨時(shí)間復(fù)雜度呈指數(shù)上升的問題，進(jìn)而無法完成預(yù)期任務(wù)。所以，當(dāng)務(wù)之急是如何通過深入地了解網(wǎng)絡(luò) motif識(shí)別問題來設(shè)計(jì)出時(shí)間復(fù)雜度更低的算法。
　　基于構(gòu)建頂點(diǎn)的K-hop特征向量的網(wǎng)絡(luò)motif識(shí)別算法FCMD的算法時(shí)間基本獨(dú)立于motif的規(guī)模，但仍然存在頂點(diǎn)的特征向量不能很好的表達(dá)Bi-fan型motif的局限性和motif聚類中兩個(gè)子圖是否重疊的判定準(zhǔn)則過于嚴(yán)格的問題，本文從這兩方面對(duì)FC

3、MD算法提出改進(jìn)：
　　(1)我們將頂點(diǎn)的特征向量表示的局部子圖進(jìn)行擴(kuò)大，使之由一個(gè)相對(duì)封閉的范圍擴(kuò)展成了一個(gè)“帶刺的”范圍；
　　(2)判斷兩個(gè)圖是否重疊的條件不再是以前的它們之間不允許有重疊的頂點(diǎn)，而是允許兩個(gè)子圖有一定量的重疊頂點(diǎn)，其數(shù)目小于某個(gè)閾值，該閾值隨著兩個(gè)子圖的頂點(diǎn)總數(shù)而變化，如此一來，當(dāng)兩個(gè)圖的頂點(diǎn)數(shù)都很少時(shí)，允許重疊的頂點(diǎn)數(shù)也較少，反之，允許重疊的頂點(diǎn)數(shù)較多。另外，經(jīng)過仔細(xì)分析，我們認(rèn)為FCMD算法識(shí)別出

4、的motif相對(duì)現(xiàn)有的大部分算法而言是模糊的，因此，提出了兩種模糊motif精確化的算法：一種基于連續(xù)型Hopfield網(wǎng)絡(luò)，另一種基于子圖窮舉motif識(shí)別算法EEA。
　　本文的實(shí)驗(yàn)部分以多種真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)為基礎(chǔ)，通過合理的實(shí)驗(yàn)設(shè)計(jì)與詳細(xì)的結(jié)果分析我們得出：
　　(1)改進(jìn)的FCMD算法識(shí)別到的網(wǎng)絡(luò)motif在數(shù)量和質(zhì)量上均與算法改進(jìn)前基本相當(dāng)，而且改進(jìn)之后算法還能有效識(shí)別網(wǎng)絡(luò)中的Bi-fan型motif；
　　(