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

1、隨著高通量蛋白質(zhì)組技術(shù)的快速發(fā)展，大量的蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)被收集整理在多個(gè)公開的數(shù)據(jù)庫中，如何從這些大規(guī)模的蛋白質(zhì)網(wǎng)絡(luò)中識別出與功能相關(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)識細(xì)胞內(nèi)生命活動(dòng)的內(nèi)在組織及其過程提供有效方法。
　　網(wǎng)絡(luò)模體發(fā)現(xiàn)的過程涉及到子圖搜索和圖同構(gòu)兩大計(jì)算難題，模體的查找時(shí)間隨著網(wǎng)絡(luò)和模體規(guī)模的

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

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

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

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

6、量級。
　　（3）從模體的生物顯著性角度，提出了一種有效的算法用于生物網(wǎng)絡(luò)模體的發(fā)現(xiàn)。該算法通過整合邊聚集系數(shù)和GO短語的語義相似性來綜合評估相互作用的生物顯著性，然后根據(jù)該值的大小去掉生物上非顯著性的邊來減少查詢的子圖數(shù)目，以增加生物網(wǎng)絡(luò)模體的發(fā)現(xiàn)比例。本文所提算法在拓?fù)鋵傩院蜕锕δ軆煞矫娴玫搅艘粋€(gè)較好的融合，有效地克服了生物網(wǎng)絡(luò)中的假陽性數(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ì)識別算法。該算法依據(jù)每個(gè)蛋白質(zhì)所參與的所有模體的擴(kuò)展子圖的密度之和作為衡量蛋白質(zhì)的關(guān)鍵性指標(biāo)。進(jìn)一步，針對蛋白質(zhì)網(wǎng)絡(luò)中存在一定的假陽性信息，首先利用邊聚集系數(shù)對網(wǎng)絡(luò)進(jìn)行預(yù)處理，然后再結(jié)合模體擴(kuò)展的算法在預(yù)處理后的網(wǎng)絡(luò)中識別關(guān)