圖論在生物學方面的有效應用

摘要：本文介紹了最大連通子圖、最大團和完美匹配等圖論知識在生物學尤其在研究蛋白質結構研究方面的應用。在現實生活中， 這具有十分重要的意義和廣闊的應用。

關鍵詞：最大連通子圖；最大團；完美匹配

中圖分類號：TP18；O157 文獻標識碼：A文章編號：1009-3044(2008)05-00ppp-0c

1 前言

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

2 圖論在生物學方面即研究蛋白質結構預測方面的有效應用

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

2.1 最大連通子圖

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

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

他們通過對牛胰蛋白酶抑制蛋白（PDB5PTI 58amino acidsresidues）和嗜熱菌蛋白酶（thermolysin）用圖論的方法進行了預測，這個預測與實驗結果相符合。他們認為，總體上，這種方法對于預測已知結構蛋白中的自折疊單元有大約70%的成功率。與以前的方法相比較，他們的方法的最大優點是所預測的自折疊單元不需要由連續的氨基酸序列所組成。強調了理論與實驗的比較，以及盡可能少地引入能量參數等優勢。

2.2 最大團

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

在同源模建中，主鏈構像的大部分可以從一個或多個相關的母板結構獲得，僅僅是那些被認為與母板結構有明顯不同的主鏈和側鏈構像，才用于轉換為尋找最大團的問題。

在氨基酸序列中的一個殘基，它的每一個可能的構象代表圖中的一個頂點。邊連接兩個頂點（殘基）。頂點和邊根據一些安排好的標準賦權。一旦這個圖被構造出來，所有的團中的極大團就可用Bron Kerbosch提出的CF（clique-finding）算法找到。那些權值最好的團被認為與天然結構最相似。

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

給定一個具有n個頂點和m個邊的團，對應構像的分值用這個團上面的邊和頂點的和來表示：

他們的方法與傳統的方法相比，不合適的構像被提前舍棄，具有搜索適應性構像速度快的優點，團的方法克服了連續能量函數搜索方法遇到能量勢壘和過早掉入局部能量最小的

勢阱里的缺點。他們用這種圖論的方法對同源蛋白質進行了預測取得了令人鼓舞的結果，同時證明，這種方法應用于同源模建的loop區域的預測具有較好的前景。

2.3 完美匹配

在無向圖G（V，E）中，對邊集E的任一子集MAE，如果M中任意兩條邊都不相鄰，則稱M為圖G的一個匹配。若G的每個頂點都是M飽和點，則稱M是G的完美匹配。2001年Piero Fariselli和Rita Casadio把預測二硫鍵連接問題等價為一個尋找圖的最大權的完美匹配問題。

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

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

3 總結以及其他研究（other researches）

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

參考文獻：

[1]郝柏林，張淑譽.生物信息學手冊[M].上海科學技術出版社，2000.

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

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

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

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

[6]來魯華，等.蛋白質的結構預測與分子設計[M].北京:北京大學出版社，1993.

收稿日期：2007-12-10

作者簡介：孫琪（1981-），女，助教，碩士，主要研究方向：人工智能，網絡等。

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”