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

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

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

3、性的特點，故以非導(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)的樹型子圖進行邊的擴展而得到，將整個子圖的查找過程分成樹型子圖查找與非樹型子圖查找兩個步驟進行。首先對于樹型子圖，提出了一種基于整數(shù)組

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

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

6、量級。
　　（3）從模體的生物顯著性角度，提出了一種有效的算法用于生物網(wǎng)絡(luò)模體的發(fā)現(xiàn)。該算法通過整合邊聚集系數(shù)和GO短語的語義相似性來綜合評估相互作用的生物顯著性，然后根據(jù)該值的大小去掉生物上非顯著性的邊來減少查詢的子圖數(shù)目，以增加生物網(wǎng)絡(luò)模體的發(fā)現(xiàn)比例。本文所提算法在拓撲屬性和生物功能兩方面得到了一個較好的融合，有效地克服了生物網(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ò)中的進化保守拓撲單元，且有研究指出，相比于非關(guān)鍵蛋白質(zhì)，關(guān)鍵蛋白質(zhì)在進化上是更加保守的，以此為理論基礎(chǔ)，提出了一種新的基于網(wǎng)絡(luò)模體擴展的子圖密度的關(guān)鍵蛋白質(zhì)識別算法。該算法依據(jù)每個蛋白質(zhì)所參與的所有模體的擴展子圖的密度之和作為衡量蛋白質(zhì)的關(guān)鍵性指標。進一步，針對蛋白質(zhì)網(wǎng)絡(luò)中存在一定的假陽性信息，首先利用邊聚集系數(shù)對網(wǎng)絡(luò)進行預(yù)處理，然后再結(jié)合模體擴展的算法在預(yù)處理后的網(wǎng)絡(luò)中識別關(guān)