圖論在生物學(xué)方面的有效應(yīng)用

摘要：本文介紹了最大連通子圖、最大團(tuán)和完美匹配等圖論知識(shí)在生物學(xué)尤其在研究蛋白質(zhì)結(jié)構(gòu)研究方面的應(yīng)用。在現(xiàn)實(shí)生活中， 這具有十分重要的意義和廣闊的應(yīng)用。

關(guān)鍵詞：最大連通子圖；最大團(tuán)；完美匹配

中圖分類號(hào)：TP18；O157 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)05-00ppp-0c

1 前言

圖論是組合數(shù)學(xué)和計(jì)算機(jī)理論科學(xué)的重要學(xué)科之一，也是數(shù)學(xué)和理論計(jì)算機(jī)中近年來發(fā)展最快的學(xué)科之一，其主要應(yīng)用除了在計(jì)算機(jī)領(lǐng)域外，還廣泛的應(yīng)用于其它學(xué)科，例如經(jīng)濟(jì)、生物、數(shù)學(xué)等等。這里我們主要介紹其在生物學(xué)中的有趣應(yīng)用。

2 圖論在生物學(xué)方面即研究蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)方面的有效應(yīng)用

我們知道蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)問題就是如何從蛋白質(zhì)的氨基酸序列出發(fā)預(yù)測(cè)它的功能、構(gòu)象折疊等問題。這是一個(gè)人類破譯生命奧秘的重大問題。這個(gè)問題一旦得到解決，科學(xué)家們就可以最終闡明遺傳信息傳遞的全過程，從而大大有助于了解蛋白質(zhì)空間結(jié)構(gòu)與其功能之間的關(guān)系。近年來，“圖”的概念已被應(yīng)用于蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)的相關(guān)研究之中，如：尋找圖的最大連通子圖研究蛋白質(zhì)的自折疊問題、圖的連接矩陣的特征矢量分析研究蛋白質(zhì)的活性位點(diǎn)和配體結(jié)合位點(diǎn)的問題、圖的完美匹配方法預(yù)測(cè)二硫鍵的問題等，取得了一定的成果，本文主要對(duì)這些圖論方法在蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)中取得的一些新的研究進(jìn)展作以綜述。

2.1 最大連通子圖

若有圖G（V，E），如果有另一圖G’（V’，E’），且V’和E’分別是V和E的子集，且E’中的一條邊e’（vi，vj）必須與E中的一條邊e（vi，vj）相對(duì)應(yīng)，稱G’為G的子圖。如果圖G’的任意兩個(gè)頂點(diǎn)之間均是連通的，則稱G’是一個(gè)連通圖。若G是不連通圖，它的每個(gè)連通的部分G’稱為G的一個(gè)連通子圖。

1997年我國(guó)學(xué)者彭征宇在‘蛋白質(zhì)中的自折疊單元’一文中，把一個(gè)蛋白質(zhì)的結(jié)構(gòu)用一個(gè)數(shù)學(xué)上的“圖”來表示。圖上的每一個(gè)頂點(diǎn)表示一個(gè)二級(jí)結(jié)構(gòu)，而每一條邊則表示兩個(gè)二級(jí)結(jié)構(gòu)單元之間的相互作用。那么，這些相互作用的強(qiáng)度將通過每?jī)蓚€(gè)二級(jí)結(jié)構(gòu)單元間有多少對(duì)重原子（指碳、氮、氧等）之間的距離在0.5nm（5埃）之內(nèi)來決定。兩個(gè)相鄰的或平行的二級(jí)結(jié)構(gòu)單元之間的相互作用將大于距離較遠(yuǎn)的或垂直的二級(jí)結(jié)構(gòu)之間的相互作用。然后，簡(jiǎn)化“圖”：只保留對(duì)于每一個(gè)頂點(diǎn)最強(qiáng)的相互作用及超過這個(gè)最大值60%的那些相互作用。對(duì)每一個(gè)頂點(diǎn)來說，它的鄰點(diǎn)對(duì)它的相互作用密度定義為它與鄰點(diǎn)的相互作用除以代表這個(gè)頂點(diǎn)的二級(jí)結(jié)構(gòu)的長(zhǎng)度。保留相互作用密度超過整個(gè)圖中最強(qiáng)相互作用密度20%的那一部分，其余的相互作用所對(duì)應(yīng)的那些邊將被舍棄。這樣所得到的圖將是非對(duì)稱的，即對(duì)某一頂點(diǎn)來說，它的鄰點(diǎn)對(duì)它來說可能是重要的，而同時(shí)這個(gè)頂點(diǎn)對(duì)它的鄰點(diǎn)來說卻是不重要的，因?yàn)樗泥忺c(diǎn)與其他頂點(diǎn)有更強(qiáng)的相互作用。在經(jīng)過簡(jiǎn)化的圖中，尋找具有自折疊能力的部分相當(dāng)于尋找這個(gè)圖的最大連通子圖。

他們通過對(duì)牛胰蛋白酶抑制蛋白（PDB5PTI 58amino acidsresidues）和嗜熱菌蛋白酶（thermolysin）用圖論的方法進(jìn)行了預(yù)測(cè)，這個(gè)預(yù)測(cè)與實(shí)驗(yàn)結(jié)果相符合。他們認(rèn)為，總體上，這種方法對(duì)于預(yù)測(cè)已知結(jié)構(gòu)蛋白中的自折疊單元有大約70%的成功率。與以前的方法相比較，他們的方法的最大優(yōu)點(diǎn)是所預(yù)測(cè)的自折疊單元不需要由連續(xù)的氨基酸序列所組成。強(qiáng)調(diào)了理論與實(shí)驗(yàn)的比較，以及盡可能少地引入能量參數(shù)等優(yōu)勢(shì)。

2.2 最大團(tuán)

若簡(jiǎn)單圖G（V，E）的子圖S是完全圖，即滿足其任意兩個(gè)頂點(diǎn)之間均有且只有一條邊相連，則稱S是G的團(tuán)。1998年Samudrala R和Moult J，把一個(gè)蛋白質(zhì)的同源模建中的3D結(jié)構(gòu)預(yù)測(cè)問題成功地轉(zhuǎn)換為一個(gè)圖論中的尋找最大團(tuán)的問題。

在同源模建中，主鏈構(gòu)像的大部分可以從一個(gè)或多個(gè)相關(guān)的母板結(jié)構(gòu)獲得，僅僅是那些被認(rèn)為與母板結(jié)構(gòu)有明顯不同的主鏈和側(cè)鏈構(gòu)像，才用于轉(zhuǎn)換為尋找最大團(tuán)的問題。

在氨基酸序列中的一個(gè)殘基，它的每一個(gè)可能的構(gòu)象代表圖中的一個(gè)頂點(diǎn)。邊連接兩個(gè)頂點(diǎn)（殘基）。頂點(diǎn)和邊根據(jù)一些安排好的標(biāo)準(zhǔn)賦權(quán)。一旦這個(gè)圖被構(gòu)造出來，所有的團(tuán)中的極大團(tuán)就可用Bron Kerbosch提出的CF（clique-finding）算法找到。那些權(quán)值最好的團(tuán)被認(rèn)為與天然結(jié)構(gòu)最相似。

一個(gè)殘基的每個(gè)可能的構(gòu)象在圖中表示一個(gè)頂點(diǎn)。頂點(diǎn)的權(quán)根據(jù)側(cè)鏈的原子與局部主鏈原子之間的相互作用程度賦權(quán)。要一直考慮到在代表頂點(diǎn)的殘基位置兩側(cè)的任意四個(gè)殘基的主鏈的原子和這個(gè)殘基的主鏈原子，被用來計(jì)算權(quán)值。邊連接一對(duì)頂點(diǎn)，邊的權(quán)根據(jù)代表頂點(diǎn)的殘基之間的相互作用程度賦權(quán)。對(duì)于空間彼此碰撞的頂點(diǎn)之間不連邊同一殘基具有不同的構(gòu)象之間不連邊。頂點(diǎn)和邊的權(quán)值通過一個(gè)全原子距離條件概率賦權(quán)。簡(jiǎn)單地說，要求的概率通過在一個(gè)265個(gè)高清晰的X-射線測(cè)出的非同源蛋白質(zhì)結(jié)構(gòu)數(shù)據(jù)庫(kù)中，計(jì)算原子類型對(duì)的距離的頻數(shù)而得到。計(jì)算公式如下：

給定一個(gè)具有n個(gè)頂點(diǎn)和m個(gè)邊的團(tuán)，對(duì)應(yīng)構(gòu)像的分值用這個(gè)團(tuán)上面的邊和頂點(diǎn)的和來表示：

他們的方法與傳統(tǒng)的方法相比，不合適的構(gòu)像被提前舍棄，具有搜索適應(yīng)性構(gòu)像速度快的優(yōu)點(diǎn)，團(tuán)的方法克服了連續(xù)能量函數(shù)搜索方法遇到能量勢(shì)壘和過早掉入局部能量最小的

勢(shì)阱里的缺點(diǎn)。他們用這種圖論的方法對(duì)同源蛋白質(zhì)進(jìn)行了預(yù)測(cè)取得了令人鼓舞的結(jié)果，同時(shí)證明，這種方法應(yīng)用于同源模建的loop區(qū)域的預(yù)測(cè)具有較好的前景。

2.3 完美匹配

在無向圖G（V，E）中，對(duì)邊集E的任一子集MAE，如果M中任意兩條邊都不相鄰，則稱M為圖G的一個(gè)匹配。若G的每個(gè)頂點(diǎn)都是M飽和點(diǎn)，則稱M是G的完美匹配。2001年P(guān)iero Fariselli和Rita Casadio把預(yù)測(cè)二硫鍵連接問題等價(jià)為一個(gè)尋找圖的最大權(quán)的完美匹配問題。

在蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)中，一個(gè)主要的問題是在富含半胱氨酸的蛋白質(zhì)中準(zhǔn)確確定二硫鍵的位置。在組成蛋白質(zhì)的20個(gè)氨基酸中，半胱氨酸惟一的具有一種屬性，即它們之間可以形成二硫鍵有助于蛋白質(zhì)三維結(jié)構(gòu)的穩(wěn)定。它使多肽鏈的兩個(gè)不同的區(qū)域之間能夠緊密地靠攏起來。在蛋白質(zhì)折疊預(yù)測(cè)中，確定二硫鍵可以大大地減少搜索構(gòu)像空間。氨基酸序列中每一個(gè)半胱氨酸殘基代表圖中的一個(gè)頂點(diǎn)V，邊E連接一對(duì)頂點(diǎn)（Cys-Cys），邊依據(jù)相應(yīng)規(guī)定賦權(quán)W，構(gòu)成一個(gè)賦權(quán)的完全圖G，應(yīng)用Edmonds-Gabow的算法，找到G中具有

最大權(quán)的完美匹配。則這個(gè)完美匹配對(duì)應(yīng)正確的二硫鍵的連接方式。權(quán)值的獲得考慮一級(jí)結(jié)構(gòu)中半胱氨酸殘基位置前后的各5個(gè)殘基賦權(quán)，數(shù)據(jù)來源于PDB蛋白質(zhì)結(jié)構(gòu)數(shù)據(jù)庫(kù)中的726個(gè)高分辨率蛋白質(zhì)中二硫鍵的連接模式的統(tǒng)計(jì)結(jié)果。他們利用這種方法對(duì)蛋白質(zhì)折疊中的二硫鍵連接進(jìn)行了預(yù)測(cè)研究，結(jié)果說明二硫鍵的形成與其序列模式有這重要的聯(lián)系，通過研究半胱氨酸殘基在序列中局部環(huán)境因素，可以預(yù)測(cè)二硫鍵的結(jié)構(gòu)。對(duì)于具有4個(gè)二硫鍵的蛋白質(zhì)結(jié)構(gòu)，這種方法的預(yù)測(cè)正確率高于隨機(jī)預(yù)測(cè)的17倍。

3 總結(jié)以及其他研究（other researches）

圖論的方法較早的文獻(xiàn)是應(yīng)用于二級(jí)結(jié)構(gòu)的模體比較和折疊片層的拓?fù)浣Y(jié)構(gòu)的分析；最近二十年，蛋白質(zhì)折疊問題已經(jīng)成為了許多理論學(xué)家和實(shí)驗(yàn)學(xué)家極大關(guān)注的課題。圖論還應(yīng)用在蛋白質(zhì)折疊的酶動(dòng)力學(xué)的表達(dá)分析上；Bahar等應(yīng)用Kirchoff’s矩陣去描述在蛋白質(zhì)中的空間相鄰殘基并且闡明了幾個(gè)屬性，比如：振動(dòng)力學(xué)和蛋白質(zhì)中的熱波動(dòng)等。PatraSM和Vishveshwara S用圖論的特征參數(shù)尋找蛋白質(zhì)中的主鏈團(tuán)，同時(shí)發(fā)現(xiàn)在團(tuán)的相似區(qū)域蛋白質(zhì)結(jié)構(gòu)也相似。我們相信，隨著研究的深入，圖論在生物學(xué)中的應(yīng)用會(huì)越來越來廣泛和實(shí)際。讓我們翹首以待！

參考文獻(xiàn)：

[1]郝柏林，張淑譽(yù).生物信息學(xué)手冊(cè)[M].上海科學(xué)技術(shù)出版社，2000.

[2]Krane D E ， Raymer M L. 孫嘯，陸祖宏，謝建明，譯.生物信息學(xué)概論[M].北京:清華大學(xué)出版社，2004.

[3]彭征宇.蛋白質(zhì)中的自折疊單元[A].見:郝柏林劉寄星.理論物理與生命科學(xué)[M] .上海:上海科學(xué)技術(shù)出版社，1997.

[4]蘭家隆，劉軍.應(yīng)用圖論及算法[M].成都:電子科技大學(xué)出版社，1995.

[5]肖位樞.圖論及其算法[M].北京:航空工業(yè)出版社，1993.

[6]來魯華，等.蛋白質(zhì)的結(jié)構(gòu)預(yù)測(cè)與分子設(shè)計(jì)[M].北京:北京大學(xué)出版社，1993.

收稿日期：2007-12-10

作者簡(jiǎn)介：孫琪（1981-），女，助教，碩士，主要研究方向：人工智能，網(wǎng)絡(luò)等。

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”