基于改進(jìn)粒子群算法的蛋白質(zhì)結(jié)構(gòu)預(yù)測

李明珠

（黑龍江中醫(yī)藥大學(xué)基礎(chǔ)醫(yī)學(xué)院，黑龍江 哈爾濱 150040）

0 引言

生物信息學(xué)運用計算機軟、硬件技術(shù)對生物學(xué)數(shù)據(jù)進(jìn)行計算、分析和數(shù)據(jù)挖掘，極大地提升了生物數(shù)據(jù)信息解算的效率，對更準(zhǔn)確地掌握生物體結(jié)構(gòu)運行規(guī)律具有十分重要的意義[1]。蛋白質(zhì)分子構(gòu)成了人體的組織和器官，蛋白質(zhì)的空間結(jié)構(gòu)決定了蛋白質(zhì)的生命功能，進(jìn)而也影響甚至決定著人體的生命活動。許多疾病的出現(xiàn)就是因為蛋白質(zhì)分子的結(jié)構(gòu)遭到破壞或者發(fā)生變異，使蛋白質(zhì)失去了穩(wěn)定狀態(tài)[2]。蛋白質(zhì)結(jié)構(gòu)預(yù)測的分析方法可以分為3類：比較建模法、反向折疊法和從頭預(yù)測法。比較建模法和反向折疊法需要已知的蛋白質(zhì)結(jié)構(gòu)作為模板，而從頭預(yù)測法不需要。因此，從頭預(yù)測法可以對未知信息的蛋白質(zhì)結(jié)構(gòu)進(jìn)行預(yù)測，前提是構(gòu)建出一個具有針對性的能量函數(shù)模型[3]。蛋白質(zhì)結(jié)構(gòu)預(yù)測領(lǐng)域已經(jīng)出現(xiàn)了很多方法，但蛋白質(zhì)穩(wěn)定結(jié)構(gòu)對應(yīng)的最低勢能值點的準(zhǔn)確預(yù)測依然是一個難點。加之蛋白質(zhì)對應(yīng)的數(shù)據(jù)量龐大，對算法的收斂速度和精度都有較高的要求。為此，該文在粒子群算法的基礎(chǔ)上進(jìn)行改進(jìn)，融入禁忌搜索策略，以提升其在蛋白質(zhì)結(jié)構(gòu)預(yù)測時的性能。

1 蛋白質(zhì)結(jié)構(gòu)模型

蛋白質(zhì)結(jié)構(gòu)預(yù)測問題其實是一個復(fù)雜多項式的非確定性問題，即NP完全問題。該文選擇從頭預(yù)測法作為解決蛋白質(zhì)結(jié)構(gòu)預(yù)測問題的方法。因此，首先需要確定蛋白質(zhì)結(jié)構(gòu)的簡化模型。通過構(gòu)建簡化模型，將蛋白質(zhì)結(jié)構(gòu)和能量的關(guān)系模擬為一個勢能函數(shù)。然后利用熱力學(xué)假說，蛋白質(zhì)勢能函數(shù)值最低時即為蛋白質(zhì)最穩(wěn)定的結(jié)構(gòu)。

目前，主要有2種較為常用的簡化的蛋白質(zhì)結(jié)構(gòu)模型，一種是HP格點模型，另一種是AB非格點模型。

在二維平面上，模擬蛋白質(zhì)折疊結(jié)構(gòu)的二維HP格點模型和二維AB非格點模型的結(jié)構(gòu)如圖1所示。

圖1（a）表示二維HP格點模型。在HP模型中，將氨基酸分成疏水性氨基酸和親水性氨基酸，分別用英文字母H和P表示。黑色方塊為疏水性氨基酸H，白色方塊為親水性氨基酸P，每個互相連接的氨基酸之間的距離都為1。而且每個格點都必須放在二維平面的整數(shù)點上，即互相連接的氨基酸殘基之間的角度不能改變。黑色方塊聚集在一起，即疏水性氨基酸集中在親水性氨基酸的內(nèi)部，形成一個疏水核心，疏水鍵用來維持蛋白質(zhì)結(jié)構(gòu)的穩(wěn)定。

圖1（b）表示二維AB非格點模型。與HP格點模型一樣，AB非格點模型也將常見的20種氨基酸分成2類，一類為疏水性氨基酸，用英文字母A表示；另一類為親水性氨基酸，用英文字母B表示。不過，和二維HP格點模型相比，AB非格點模型中相鄰氨基酸之間的角度是可變的，而不是固定在二維平面的整數(shù)點上。這種結(jié)構(gòu)跟真實的蛋白質(zhì)空間結(jié)構(gòu)更相似，用來作為蛋白質(zhì)的模擬結(jié)構(gòu)更合適。圖1（b）中帶有數(shù)字的白色方塊代表氨基酸，相鄰2個氨基酸的殘基之間會形成夾角，用α1、α2、α3……表示。

圖1 二維HP模型和AB模型

二維AB非格點模型的能量函數(shù)的表達(dá)如公式（1）所示。

式中：E為能量函數(shù)；n為氨基酸數(shù)目；E1為第一部分勢能函數(shù)，表達(dá)的是氨基酸骨架折疊所蘊藏的能量，與各個折疊角度有關(guān)；E2為第二部分勢能函數(shù)，表達(dá)的是不相鄰氨基酸殘基之間的能量，與殘基之間的距離和極性有關(guān)。

綜合對比HP格點模型和AB非格點模型的優(yōu)缺點，該文的算法中均采用AB非格點模型對蛋白質(zhì)結(jié)構(gòu)進(jìn)行表達(dá)。

2 蛋白質(zhì)結(jié)構(gòu)預(yù)測算法設(shè)計

2.1 蛋白質(zhì)結(jié)構(gòu)預(yù)測算法的總體構(gòu)思

蛋白質(zhì)的穩(wěn)定結(jié)構(gòu)對應(yīng)于蛋白質(zhì)勢能函數(shù)的最低能量值，這就使蛋白質(zhì)穩(wěn)定結(jié)構(gòu)的預(yù)測轉(zhuǎn)變?yōu)槟芰亢瘮?shù)的尋優(yōu)問題。在這一領(lǐng)域，禁忌搜索法和粒子群算法都是比較常見的方法。

因其具有的良好的記憶功能，禁忌搜索算法對局部搜索的能力很強。通過使用禁忌表記錄已經(jīng)搜索過的局部最優(yōu)解，禁忌搜索算法可以避免迂回搜索、跳出局部最優(yōu)。同時，通過藐視準(zhǔn)則激勵某些較好的解，禁忌搜索算法也可避免錯失優(yōu)良個體。

但是禁忌搜索算法對初始解有一定的依賴性。較好的初始解能夠讓禁忌搜索算法搜索到較優(yōu)的值，較差的初始解將導(dǎo)致禁忌搜索算法的收斂速度降低。

粒子群算法能夠得到較好的解。因此，該文將粒子群算法得到的較好解作為禁忌捜索算法的初始解，然后利用禁忌搜索算法的禁忌策略和藐視準(zhǔn)則形成一個既有全局捜索能力又有局部搜索能力的優(yōu)化算法。

2.2 蛋白質(zhì)結(jié)構(gòu)預(yù)測算法的詳細(xì)設(shè)計

2.2.1 初始值的生成

運行粒子群算法進(jìn)行全局搜索。待收斂到一定程度后，將得到的較好的解作為禁忌搜索算法的初始值，進(jìn)而提高算法的搜索精度和效率。

每個粒子的速度和位置更新方式如公式（2）和公式（3）所示。

式中：?為慣性權(quán)重；λ1和λ2分別為2個學(xué)習(xí)因子；rand（）為隨機函數(shù)；pid為第i個粒子的歷史最優(yōu)位置；pgd為整個粒子群的歷史最優(yōu)位置。

2.2.2 鄰域函數(shù)

禁忌搜索算法的鄰域解通過單點變異實現(xiàn)。該文采用擾動變異的絲線來產(chǎn)生鄰域解，以便保證鄰域解的多樣性。此處設(shè)計的鄰域函數(shù)如公式（4）、公式（5）所示。

式中：q和Q分別為隨機數(shù)；K為比例因子；i為鄰域解的生成次數(shù)。如果鄰域解的個數(shù)為L，那么i在[0，L-1]取值。此處設(shè)定K=0.93，L=40。

2.2.3 候選解集

候選解集是鄰域解的一個子集。在算法中，通過計算L個鄰域解中每個解的適應(yīng)值，選擇適應(yīng)值最低的前LC個鄰域解作為候選解集。此處設(shè)定LC=6。

2.2.4 禁忌表

禁忌表用來存儲近期搜索過的解，其長度為LT。每次算法經(jīng)過迭代后，新的禁忌對象會進(jìn)入禁忌表。與此同時，每個禁忌對象的任期應(yīng)該減1。只有當(dāng)禁忌對象的任期為0時才能夠被解禁，先進(jìn)入禁忌表的對象可以先被禁忌出去。禁忌表的長度對算法的搜索精度也有一定影響。如果禁忌表的長度較大，則算法的搜索范圍相對較廣，能夠搜索到較好的解。但是這也會使算法的搜索時間變長，收斂速度變慢。如果禁忌表長度過小，就不能發(fā)揮禁忌表的作用，容易使算法陷入迂回搜索。所以，禁忌表長度的設(shè)置是否合理將對算法的結(jié)果有很大影響。此處設(shè)定LT=8。

2.2.5 禁忌準(zhǔn)則

設(shè)候選解z（α1，α2，…，αn-2）的適應(yīng)值為E（z），禁忌表中存在一個解向量y（α′1，α′2，…，），其適應(yīng)值為E（y），如果滿足公式（6）和公式（7），那么候選解z滿足禁忌準(zhǔn)則，候選解被禁忌。

此處，根據(jù)多次試驗的結(jié)果，設(shè)E0=0.10，r0=0.005。

3 試驗結(jié)果與分析

3.1 試驗配置

為了驗證該文提出的蛋白質(zhì)結(jié)構(gòu)預(yù)測方法的有效性，接下來進(jìn)行試驗研究。試驗中所用的計算機CPU為Intel雙核，單核主頻3.60 GHz，內(nèi)存大小為16 GB。計算機的操作系統(tǒng)為windows 10。

試驗中，該文算法參數(shù)的配置如下：粒子群算法的粒子總數(shù)為260個，迭代次數(shù)上限為800，2個學(xué)習(xí)因子λ1=λ2=2.0，比例因子K=0.93，鄰域解個數(shù)L=40，候選解個數(shù)LC=6。

試驗中，為了和該文算法形成對比，還選擇了粒子群算法和禁忌搜索法作為試驗中的對照方法。

試驗中，試驗對象選擇了試驗標(biāo)準(zhǔn)常用的人工蛋白質(zhì)序列，共分為4組。4組人工蛋白質(zhì)序列都采用AB非格點模型表示，第一組人工蛋白質(zhì)序列的長度為13，包括5個親水性氨基酸（A），8個疏水性氨基酸（B）；第二組人工蛋白質(zhì)序列的長度為21，包括8個親水性氨基酸（A），13個疏水性氨基酸（B）；第三組人工蛋白質(zhì)序列的長度為34，包括13個親水性氨基酸（A），21個疏水性氨基酸（B）；第四組人工蛋白質(zhì)序列的長度為55，包括21個親水性氨基酸（A），34個疏水性氨基酸（B）。4組人工蛋白質(zhì)序列的氨基酸配置如圖2所示。

3.2 蛋白質(zhì)結(jié)構(gòu)預(yù)測結(jié)果

根據(jù)上述4組人工蛋白質(zhì)序列，分別按照禁忌搜索法、粒子群算法和該文算法構(gòu)建數(shù)學(xué)模型，并執(zhí)行最低勢能值預(yù)測，結(jié)果見表1。

從表1中的試驗結(jié)果可以看出，該文算法得到的4組人工蛋白質(zhì)序列的最低勢能值，都要明顯低于禁忌搜索法和粒子群算法得到的最低勢能值。這也表明，利用該文算法可以得到更穩(wěn)定的蛋白質(zhì)結(jié)構(gòu)。

表1 3種方法得出的最低勢能值

進(jìn)一步，對上述4組人工蛋白質(zhì)序列的穩(wěn)定結(jié)構(gòu)進(jìn)行預(yù)測，第二組和第三組蛋白質(zhì)結(jié)構(gòu)的預(yù)測結(jié)果如圖3和圖4所示。

圖3 第二組人工蛋白質(zhì)序列穩(wěn)定結(jié)構(gòu)的預(yù)測結(jié)果

圖4 第三組人工蛋白質(zhì)序列穩(wěn)定結(jié)構(gòu)的預(yù)測結(jié)果

4 結(jié)論

蛋白質(zhì)序列結(jié)構(gòu)穩(wěn)定性的研究是生物信息學(xué)領(lǐng)域的重要研究內(nèi)容。該文針對這一問題，將禁忌搜索法和粒子群算法結(jié)合起來，提出了一種新的蛋白質(zhì)結(jié)構(gòu)的預(yù)測方法。該方法充分考慮了禁忌搜索法對初始解具有依賴性的問題，先運用粒子群算法求取初始解，然后再運用禁忌搜索法構(gòu)建鄰域函數(shù)、候選解集、禁忌表和禁忌準(zhǔn)則，通過2種算法的融合完成蛋白質(zhì)結(jié)構(gòu)的預(yù)測。試驗中，選取了4組人工蛋白質(zhì)序列，先按照AB非格點模型建模，進(jìn)而分別采用3種方法求取最低勢能值。試驗結(jié)果表明，和禁忌搜索法、粒子群算法相比，該文算法得到的蛋白質(zhì)序列的勢能值更低，預(yù)測出的蛋白質(zhì)穩(wěn)定結(jié)構(gòu)更合理。