一種新的基于特征聚類的網(wǎng)絡(luò)motif識別算法.pdf

1、隨著大規(guī)?；蚪M測序、基因預(yù)測以及注釋工作的完成，生物信息學(xué)研究進(jìn)入了后基因組時代，系統(tǒng)生物學(xué)作為其中一個新興的研究領(lǐng)域，受到了越來越多的關(guān)注。與此同時，motif識別問題的研究也由僅僅針對生物序列數(shù)據(jù)(DNA序列、蛋白質(zhì)序列)拓展到了復(fù)雜生物網(wǎng)絡(luò)的層面上。網(wǎng)絡(luò)motif識別技術(shù)作為研究生物網(wǎng)絡(luò)的結(jié)構(gòu)設(shè)計(jì)規(guī)則及網(wǎng)絡(luò)發(fā)展規(guī)律和趨勢的有力工具，已成為當(dāng)前系統(tǒng)生物學(xué)領(lǐng)域的研究熱點(diǎn)之一。近年來，在網(wǎng)絡(luò)motif識別算法研究方面，人們已經(jīng)探索出一

2、些有效的算法，這些算法在解決較小規(guī)模的網(wǎng)絡(luò)motif識別問題時表現(xiàn)出了良好的性能。但是，隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大，很多算法已無法適應(yīng)問題的需要。所以，積極探索更加有效的網(wǎng)絡(luò)motif識別算法已成為當(dāng)今網(wǎng)絡(luò)motif識別研究中的一項(xiàng)重要課題。
　　 本文首先對網(wǎng)絡(luò)motif識別技術(shù)的基本思想進(jìn)行了分析，并詳細(xì)研究了現(xiàn)有的各種網(wǎng)絡(luò)motif識別算法。在此基礎(chǔ)上，我們提出了一種新的基于特征聚類的網(wǎng)絡(luò)motif識別算法--FCMD算法。該

3、算法與以往識別算法不同的是它通過構(gòu)造基于頂點(diǎn)的局部結(jié)構(gòu)表達(dá)形式來描述網(wǎng)絡(luò)motif的拓?fù)浣Y(jié)構(gòu)特征，從而有效地降低了算法復(fù)雜度。FCMD算法還引入了聚類的思想，通過在特征空間中進(jìn)行聚類分析來識別網(wǎng)絡(luò)motif，在保證識別質(zhì)量的同時大大縮短了算法運(yùn)行時間。通過在生物化學(xué)網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、電子電路網(wǎng)絡(luò)等六種真實(shí)網(wǎng)絡(luò)數(shù)據(jù)中進(jìn)行實(shí)驗(yàn)的結(jié)果表明，F(xiàn)CMD算法不僅能夠準(zhǔn)確的識別出網(wǎng)絡(luò)中蘊(yùn)含的motif結(jié)構(gòu)，并且算法的時間復(fù)雜度基本獨(dú)立于網(wǎng)絡(luò)motif的