蛋白質(zhì)網(wǎng)絡(luò)模體發(fā)現(xiàn)算法及其在關(guān)鍵蛋白質(zhì)識(shí)別中的應(yīng)用.pdf

1、隨著高通量蛋白質(zhì)組技術(shù)的快速發(fā)展，大量的蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)被收集整理在多個(gè)公開(kāi)的數(shù)據(jù)庫(kù)中，如何從這些大規(guī)模的蛋白質(zhì)網(wǎng)絡(luò)中識(shí)別出與功能相關(guān)的子結(jié)構(gòu)是當(dāng)前計(jì)算生物學(xué)的研究熱點(diǎn)之一。網(wǎng)絡(luò)模體代表著蛋白質(zhì)網(wǎng)絡(luò)中的進(jìn)化保守拓?fù)鋯卧芯烤W(wǎng)絡(luò)模體有助于理解蛋白質(zhì)網(wǎng)絡(luò)的結(jié)構(gòu)、功能以及進(jìn)化設(shè)計(jì)原理，同時(shí)為系統(tǒng)認(rèn)識(shí)細(xì)胞內(nèi)生命活動(dòng)的內(nèi)在組織及其過(guò)程提供有效方法。
　　網(wǎng)絡(luò)模體發(fā)現(xiàn)的過(guò)程涉及到子圖搜索和圖同構(gòu)兩大計(jì)算難題，模體的查找時(shí)間隨著網(wǎng)絡(luò)和模體規(guī)模的

2、增大呈指數(shù)級(jí)增長(zhǎng)，從而使其適用性受到限制。因此研究高效、可擴(kuò)展性的模體發(fā)現(xiàn)算法具有重要的理論意義和應(yīng)用價(jià)值。另一方面，從模體的生物意義角度出發(fā)，如何有效地去除生物網(wǎng)絡(luò)中的噪聲數(shù)據(jù)使查找出的模體更具有生物顯著性也是當(dāng)前存在的問(wèn)題之一。
　　本文以真實(shí)的蛋白質(zhì)網(wǎng)絡(luò)作為研究對(duì)象，分別從計(jì)算角度和生物角度研究了兩種類(lèi)型的網(wǎng)絡(luò)模體發(fā)現(xiàn)問(wèn)題，即結(jié)構(gòu)網(wǎng)絡(luò)模體和生物網(wǎng)絡(luò)模體。對(duì)于結(jié)構(gòu)網(wǎng)絡(luò)模體，考慮到高通量實(shí)驗(yàn)所得到的蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)存在假陰性和假陽(yáng)

3、性的特點(diǎn)，故以非導(dǎo)出子圖的方式來(lái)查找，而對(duì)于生物網(wǎng)絡(luò)模體，由于在查找子圖之前原網(wǎng)絡(luò)經(jīng)過(guò)了去噪預(yù)處理，則以導(dǎo)出子圖的方式來(lái)查找。此外，考慮到關(guān)鍵蛋白質(zhì)與網(wǎng)絡(luò)模體之間可能具有的內(nèi)在聯(lián)系，本文最后開(kāi)展了以網(wǎng)絡(luò)模體為中心的關(guān)鍵蛋白質(zhì)的識(shí)別研究，主要研究工作如下：
　?。?）鑒于任何非樹(shù)型連通子圖可以通過(guò)相應(yīng)的樹(shù)型子圖進(jìn)行邊的擴(kuò)展而得到，將整個(gè)子圖的查找過(guò)程分成樹(shù)型子圖查找與非樹(shù)型子圖查找兩個(gè)步驟進(jìn)行。首先對(duì)于樹(shù)型子圖，提出了一種基于整數(shù)組

4、合的子樹(shù)枚舉和統(tǒng)計(jì)算法。該算法利用整數(shù)的組合操作設(shè)計(jì)一種有效的子樹(shù)枚舉算法，并通過(guò)在子樹(shù)枚舉的過(guò)程中同時(shí)搜索一個(gè)根樹(shù)的方式來(lái)有效減少子樹(shù)同構(gòu)的判斷數(shù)目，此外，通過(guò)把所查找子樹(shù)的規(guī)范化標(biāo)記存儲(chǔ)在內(nèi)存中的方法來(lái)簡(jiǎn)化子樹(shù)的計(jì)數(shù)方式。最后，在查找出的樹(shù)型子圖的基礎(chǔ)上，通過(guò)深度優(yōu)先搜索擴(kuò)展樹(shù)的層次結(jié)構(gòu)進(jìn)行非樹(shù)型子圖的查找。實(shí)驗(yàn)結(jié)果表明，相比于現(xiàn)存算法，本文所提方法在運(yùn)行時(shí)間上具有較明顯的性能加速。
　?。?）為了去除模體發(fā)現(xiàn)過(guò)程中圖同構(gòu)的判

5、斷，提出了一種基于組合技術(shù)的子樹(shù)統(tǒng)計(jì)算法。該算法采用組合技術(shù)來(lái)直接計(jì)算每種同構(gòu)模式的數(shù)目，而不需要完整枚舉出子樹(shù)，從而避免了圖同構(gòu)的測(cè)試。而且，根據(jù)不同子樹(shù)擁有相同子結(jié)構(gòu)的特點(diǎn)，實(shí)現(xiàn)從一個(gè)子結(jié)構(gòu)統(tǒng)計(jì)多種子樹(shù)的同構(gòu)模式數(shù)目的方式，可以減少子結(jié)構(gòu)的重復(fù)搜索。最后，本文利用循環(huán)門(mén)排序“revolving door ordering”算法來(lái)有效地生成頂點(diǎn)的組合以實(shí)現(xiàn)子結(jié)構(gòu)的枚舉。實(shí)驗(yàn)結(jié)果表明，相比于現(xiàn)存算法，本文所提算法在運(yùn)行時(shí)間上至少快一個(gè)數(shù)

6、量級(jí)。
　?。?）從模體的生物顯著性角度，提出了一種有效的算法用于生物網(wǎng)絡(luò)模體的發(fā)現(xiàn)。該算法通過(guò)整合邊聚集系數(shù)和GO短語(yǔ)的語(yǔ)義相似性來(lái)綜合評(píng)估相互作用的生物顯著性，然后根據(jù)該值的大小去掉生物上非顯著性的邊來(lái)減少查詢(xún)的子圖數(shù)目，以增加生物網(wǎng)絡(luò)模體的發(fā)現(xiàn)比例。本文所提算法在拓?fù)鋵傩院蜕锕δ軆煞矫娴玫搅艘粋€(gè)較好的融合，有效地克服了生物網(wǎng)絡(luò)中的假陽(yáng)性數(shù)據(jù)，使查找到的子圖在復(fù)合物與功能模塊中都具有較高的比例。同樣，所提算法也適用于傳統(tǒng)結(jié)構(gòu)

7、網(wǎng)絡(luò)模體的發(fā)現(xiàn)。
　?。?）考慮到網(wǎng)絡(luò)模體是蛋白質(zhì)網(wǎng)絡(luò)中的進(jìn)化保守拓?fù)鋯卧?，且有研究指出，相比于非關(guān)鍵蛋白質(zhì)，關(guān)鍵蛋白質(zhì)在進(jìn)化上是更加保守的，以此為理論基礎(chǔ)，提出了一種新的基于網(wǎng)絡(luò)模體擴(kuò)展的子圖密度的關(guān)鍵蛋白質(zhì)識(shí)別算法。該算法依據(jù)每個(gè)蛋白質(zhì)所參與的所有模體的擴(kuò)展子圖的密度之和作為衡量蛋白質(zhì)的關(guān)鍵性指標(biāo)。進(jìn)一步，針對(duì)蛋白質(zhì)網(wǎng)絡(luò)中存在一定的假陽(yáng)性信息，首先利用邊聚集系數(shù)對(duì)網(wǎng)絡(luò)進(jìn)行預(yù)處理，然后再結(jié)合模體擴(kuò)展的算法在預(yù)處理后的網(wǎng)絡(luò)中識(shí)別關(guān)