基于改進遺傳算法的蛋白質(zhì)三維折疊模擬

基于改良遺傳算法的蛋白質(zhì)三維折疊模擬【摘要】根據(jù)氨基酸的序列預(yù)測蛋白質(zhì)的空間構(gòu)造在基因治療藥物分子設(shè)計等方面有宏大的潛在應(yīng)用價值。本研究基于hp格子模型利用改良的遺傳算法預(yù)測了蛋白質(zhì)的三維空間構(gòu)造。改良的遺傳算法引入了克隆體數(shù)量限制策略、巢穴競爭選擇策略及部分優(yōu)化策略等。實驗結(jié)果說明，改良的遺傳算法顯著地進步了蛋白質(zhì)構(gòu)造的預(yù)測效率，模擬的蛋白質(zhì)構(gòu)造緊湊，更接近真實蛋白質(zhì)的構(gòu)型?！娟P(guān)鍵詞】遺傳算法蛋白質(zhì)折疊三維hp模型1引言蛋白質(zhì)是生命活動的重要承當者，蛋白質(zhì)所具有的功能在很大程度上取決于其空間構(gòu)造，掌握蛋白質(zhì)的空間構(gòu)造在基因治療和藥物分子設(shè)計方面有極大的潛在應(yīng)用價值[1]。目前,測定蛋白質(zhì)空間構(gòu)造的方法主要是核磁共振和x射線衍射技術(shù)，這些技術(shù)消耗宏大，測定效率低下，遠遠滿足不了日益增加的待測定海量蛋白質(zhì)的需要[2]。根據(jù)氨基酸的序列,從理論上預(yù)測蛋白質(zhì)的空間構(gòu)造有助于進步測定蛋白質(zhì)構(gòu)造的效率，對生物醫(yī)學的開展有重要的意義[3]。蛋白質(zhì)構(gòu)造預(yù)測是個典型的“np問題〞〔算法的復(fù)雜性隨著規(guī)模的增長成指數(shù)增長〕，也就是蛋白質(zhì)的構(gòu)造不能用一個多項式來明確表示，其能量的最小值必須通過啟發(fā)式算法來搜索[4]。目前開展的啟發(fā)式算法主要有蒙特卡羅模擬算法、禁忌算法、蟻群算法、鏈增長算法、模擬退火算法和遺傳算法等[5～8]。其中遺傳算法由于高效地搜索效率得到了廣泛的應(yīng)用。本研究針對hp模型〔疏水性和親水性格子模型〕采用改良遺傳算法模擬了蛋白質(zhì)的三維空間折疊行為，改良的遺傳算法主要引入了克隆體數(shù)量限制策略、巢穴競爭選擇策略和部分優(yōu)化策略等。2原理和方法2.13dhp模型最簡單的蛋白質(zhì)分子模型是hp格子模型，該模型把所有的氨基酸殘基按疏水性和親水性分成兩類：疏水性殘基〔h〕和親水性殘基〔p〕。因此，蛋白質(zhì)序列被抽象為一個由h和p組成的序列[9]。hp格子模型在三維空間中的折疊簡稱3dhp模型，每個殘基的折疊方向可以向左、向右、向上、向下90°或者向前,折疊的殘基不能重疊在其它殘基上，整個蛋白質(zhì)序列在一個三維方格上折疊。3dhp模型的理論根底是氨基酸的疏水性是球蛋白形成的主要驅(qū)動力[2]。該模型忽略了側(cè)鏈的影響，符合真實蛋白的根本特征。疏水性的氨基酸為了減小與水分子的接觸面積而彼此靠近并進入分子的內(nèi)部，形成了疏水互相作用；親水性氨基酸那么形成了分子的外表，形成嚴密的團狀構(gòu)象。3dhp模型雖然過于粗糙，與真實蛋白分子相差甚遠，但是它能模擬真實蛋白的折疊行為，且計算簡單，有利于比照不同折疊搜索算法。hp格子模型中，一個構(gòu)象的能量計算規(guī)那么如下：當兩個在序列上不相鄰的節(jié)點在空間上相鄰時，便提供應(yīng)構(gòu)象一個互相作用能量.對于一個特定的序列構(gòu)造，它的總能量e為：ｅ＝∑i＜n,j＜ni=1,j=i+1δreij，式中n為蛋白質(zhì)序列的長度。假如i與j在空間中拓撲相鄰但序列不相鄰，那么δr等于1，否那么等于0。eij表示在序列中第i個氨基酸與第j個氨基酸之間的能量。三維空間中拓撲相鄰的殘基有３種情形：hh、hp、pp，３種拓撲關(guān)系的能量規(guī)定如下[5]：ｅｈｈ＝－１．０，ｅｈｐ＝０．０，ｅｐｐ＝０．０〔1〕由此，蛋白質(zhì)三維折疊模擬的命題表述為：搜索蛋白質(zhì)序列在空間中的構(gòu)造，使該構(gòu)造中拓撲相鄰的hh數(shù)量最多。上述的模型得到了廣泛的應(yīng)用，然而這種模型只考慮hh間的互相作用，而未考慮hp間的互相作用。實際的蛋白質(zhì)構(gòu)造是親水性殘基包裹疏水性殘基形成球狀構(gòu)造，忽略hp間的互相作用將導(dǎo)致雖然找到了最多的hh接觸數(shù)量，但是末端的疏水性分子p沒有任何約束而隨意折疊，蛋白質(zhì)空間構(gòu)造的自由度太大，甚至形成與真實蛋白質(zhì)構(gòu)造相差太遠的構(gòu)造。實際３種拓撲關(guān)系的能量大小關(guān)系為：ｅｈｈ＜ｅｈｐ＜ｅｐｐ，本研究對３種拓撲關(guān)系做如下修正：ｅｈｈ＝１．０，ｅｈｐ＝－０．４，ｅｐｐ＝０．０〔2〕這種修正考慮了氨基酸殘基應(yīng)滿足的物理制約條件，不同類型的氨基酸殘基趨向于別離，滿足關(guān)系式[1１]：２ｅηρ＞ｅηη＋ｅｐｐ〔３〕本研究中，個體適應(yīng)度規(guī)定為：ｆi＝－ei＋０．０１〔4〕分析化學第37卷第1期李紹新等：基于改良遺傳算法的蛋白質(zhì)三維折疊模擬該規(guī)定保證了適應(yīng)度總為正數(shù)，個體能量越低，適應(yīng)度越大。增加的常量〔0.01〕保證了個別個體能量為零時適應(yīng)度不為零，也有時機參與遺傳操作。修正后的蛋白質(zhì)三維折疊模擬命題表述為：尋求給定蛋白質(zhì)序列具有最大適應(yīng)度的三維空間構(gòu)造。2.2遺傳算法遺傳算法首先是由美國的hlland教授提出來的啟發(fā)式優(yōu)化組合方法[1２]。它基于達爾文進化論和孟德爾遺傳學說，仿效生物的進化與遺傳，根據(jù)“生存競爭〞和“優(yōu)勝劣汰〞的原那么，借助復(fù)制、交換、突變等操作，使所要解決的問題從初始解一步步逼近最優(yōu)解。與其他搜索方法相比，ga具有隨機性、魯棒性、并行性、全局搜索等優(yōu)越性[1３]。遺傳算法運行時首先編碼建立解的初始群體，編碼一般采用二進制或浮點，每個解用特定的基因串表示，突變算子獨立作用在串上，在最初的方案中，突變算子就是改變串上的一個位。在執(zhí)行完一定數(shù)量的突變后，由穿插操作產(chǎn)生新的串：選擇集團中的兩個串，并確定串中的斷點，兩個新的集團成員由一個串的左邊部分連接到另一個串的右邊而形成。這樣的操作進展到一個由可承受串組成的新的群體形成為止。接著進展下一階段的循環(huán)。這個步驟重復(fù)進展直到集團收斂于一個串，適應(yīng)值函數(shù)那么用來評估突變和穿插所產(chǎn)生新串的質(zhì)量。〔１〕隨機產(chǎn)生初始群體，計算每個個體的適應(yīng)度；〔２〕生存選擇：根據(jù)個體適應(yīng)度大小選擇生存?zhèn)€體，一般采用輪盤賭選擇，適應(yīng)度越大的個體被選中的概率越大；〔３〕穿插：采用單點或兩點穿插。根據(jù)穿插概率隨機選擇一對穿插個體，在選中的個體上隨機選擇穿插位點，形成兩個新個體；〔４〕變異：根據(jù)變異概率隨機選擇變異位點施行基因突變，一般采用均勻變異；〔５〕適應(yīng)度評價：根據(jù)能量法那么計算每個個體的適應(yīng)度大??；〔６〕群體更新：假如子代個體中最優(yōu)個體的適應(yīng)度大于父代最優(yōu)個體，那么保存子代的最優(yōu)個體，通過遺傳操作后的所有個體代替父代個體，重復(fù)步驟2～6直到產(chǎn)生滿足要求的最優(yōu)個體?！并　嘲垂健玻础秤嬎氵m應(yīng)度，該計算方法可以保證所有個體都有時機參與遺傳操作；當群體中出現(xiàn)無效個體〔幾個氨基酸殘基重疊在同一位置〕，對該個體給予懲罰扣分，不是簡單的丟棄該個體；〔ⅱ〕生存選擇階段引進克隆體數(shù)量限制策略。在用輪盤賭選擇個體時候，個別個體的競爭力很強，會被大量的繁殖，群體逐漸同質(zhì)化。該策略限制了在進化中個別個體被克隆的數(shù)量，保持了群體的多樣性，防止群體的早熟收斂；〔?！炒┎咫A段引進多點穿插，巢穴競爭選擇策略。一般的進化算法是兩個親代個體穿插后產(chǎn)生兩個子代個體。巢穴選擇策略是兩個親代個體雜交后產(chǎn)生多個子代個體，子代個體與親代個體競爭選擇最好的兩個個體遺傳進化。根據(jù)氨基酸的長度，采取3點穿插，每對隨機選擇的親代個體隨機穿插2次產(chǎn)生4個后代個體；〔ⅳ〕部分優(yōu)化策略。當算法搜索到一定階段后，染色體進化速度驟然降低，最優(yōu)個體往往停頓進化。因此，對最優(yōu)個體進展部分優(yōu)化有利于算法跳出‘部分陷阱’。部分優(yōu)化策略操作如下：首先選擇群體中最優(yōu)個體；再從第二個位開場，對最優(yōu)個體進展隨機變異操作；再計算變異個體的適應(yīng)度。假如變異后個體的適應(yīng)度f2大于等于變異前的適應(yīng)度f1，承受變異后的新個體，最后對新個體的下一位繼續(xù)進展變異操作，重復(fù)步驟〔?！澈汀并ぁ持钡絺€體的所有位變異操作完畢。3結(jié)果與討論３．１改良的遺傳算法的性能比擬利用改良的遺傳算法對含27個殘基的標準hp序列進展了三維折疊模擬，序列如表1所示。該序列在許多文獻中屢次應(yīng)用[1４～1６]。程序采用atlab語言編寫，優(yōu)化后的參數(shù)為群體規(guī)模200，穿插概率0.75，變異概率0.05。對每個序列折疊模擬20次。實驗結(jié)果發(fā)現(xiàn)，改良后的算法性能得到了顯著的進步，不僅能以較小的代價搜索到最低能量構(gòu)型，而且搜索到的構(gòu)型緊湊，更接近真實蛋白的構(gòu)造。表1測試的蛋白質(zhì)序列〔略〕table1peptidelengthtestases為了便于比擬，對最后搜索到的最優(yōu)個體采用公式〔1〕重新計算能量。表2是改良算法后的結(jié)果與其它標準算法結(jié)果比擬。由２表可以看出，搜索到最低能量時，unger需要的能量評價函數(shù)較多，pattn需要的能量評價函數(shù)大為減少，本研究需要的函數(shù)評價數(shù)目比pattn算法有所減少，但是個別序列有所增多。表2測試能量評價數(shù)結(jié)果比擬〔略〕table2resultparisnfenergyevaluatinunger采用的遺傳算法在初始階段所有個體從一條直線開場變異[15]，變異后的個體用蒙特卡羅方法過濾。在穿插階段算法實行單點穿插，穿插后的個體也用蒙特卡羅方法過濾。當產(chǎn)生的后代個體出現(xiàn)無效個體時拋棄該個體，重新產(chǎn)生新的個體。這種算法類似于模擬退火算法，抑制了遺傳算法的搜索性能，所以該算法的能量評價數(shù)目非常多。pattn的遺傳算法采用相對編碼，兩點穿插，當出現(xiàn)無效個體時候，對每個重疊位置采取懲罰性扣分[1４]。pattn的算法性能得到了較大的進步，但是pattn的格子模型沒有考慮hp的互相作用。3.2改良策略的影響本研究中的克隆體數(shù)量限制策略對維持種群的多樣性起了很重要的作用。實驗發(fā)現(xiàn)，當群體遺傳一定代數(shù)后，群體進化陷入停滯，群體中的個別個體大量繁殖，甚至占了近群體20%～50%，這樣的群體很難有新的進化。采用克隆體數(shù)量限制策略有效地解決了過度繁殖的問題，該策略規(guī)定群體中一樣個體不能超過一定數(shù)量，超過的部分用隨機產(chǎn)生新的個體來代替。該策略不必頻繁使用，每遺傳10代使用一次比擬節(jié)約資源。實驗發(fā)現(xiàn)克隆體限制數(shù)量設(shè)定為3～6比擬適宜，本研究將克隆體數(shù)量限定為4。本研究中的多點穿插策略也有利于保持個體的有效性。對于一個染色體，改變其中一個氨基酸的折疊方向?qū)φ麄€個體產(chǎn)生宏大的影響，而多點交換策略只改變其中一段染色體的構(gòu)造，降低了單點穿插帶來的壓力。巢穴競爭選擇策略使得新的個體不僅面臨與同輩個體間的競爭，也面臨與父輩個體的競爭，進步了繁殖優(yōu)秀個體的才能。本研究采用的部分優(yōu)化策略是系統(tǒng)變異，類似于ntearl搜索方法[17]。本策略對最優(yōu)染色體進展二次尋優(yōu)，在算法的初期階段爬山才能較強，但是在后期根本上失去了對染色體的改造才能，產(chǎn)生有效個體數(shù)不多。3.3改良能量關(guān)系的影響本研究的適應(yīng)度的規(guī)定與其它文獻有所差異[5,7,9]，一般的適應(yīng)度都是直接用hh間的接觸數(shù)量表示適應(yīng)度的上下，沒有hh接觸的個體適應(yīng)度為0，沒有時機參與遺傳，這種個體中也存在優(yōu)秀基因。本實驗增加了一個常量0.01，個體適應(yīng)度都不為零，所有的個體都有被選中的時機，這種策略不僅保持了群體的多樣性，也使更多的優(yōu)秀基因有時機參與遺傳。圖1序列27.０9的兩種不同構(gòu)造〔a〕為未改良算法得到的構(gòu)造，〔b〕為改良算法后的構(gòu)造，兩種構(gòu)造的hh鍵數(shù)量都是7，圖中黑球表示非極性分子h，白球表示極性分子p〔略〕圖2序列p8h8p8的兩種不同構(gòu)造a為未改良算法得到的構(gòu)造，b為改良算法后的構(gòu)造，兩種構(gòu)造的hh鍵數(shù)量都是5，圖中黑球表示非極性分子h，白球表示極性分子p〔略〕結(jié)果說明，改良的遺傳算法維持了種群的多樣性，增強了算法尋優(yōu)才能，進步了搜索效率，模擬的蛋白質(zhì)構(gòu)造緊湊，更接近真實蛋白質(zhì)的構(gòu)型?！緟⒖嘉墨I】1bakerdsalia.siene,2001,294(5540):93～962anfinsen．siene,1973,181(96):223～2303hrist,alenas,hlgerhh.bbiinfratis,2022,8:342～3624harte,istrails.jurnalfputatinalbilgy,1997,4(1):1～226