李明珠

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

0 引言

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

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

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

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

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

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

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

圖1 二維HP模型和AB模型

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

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

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

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

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

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

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

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

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

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

2.2.1 初始值的生成

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

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

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

2.2.2 鄰域函數(shù)

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

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

2.2.3 候選解集

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

2.2.4 禁忌表

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

2.2.5 禁忌準(zhǔn)則

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

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

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

3.1 試驗(yàn)配置

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

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

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

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

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

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

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

表1 3種方法得出的最低勢(shì)能值

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

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

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

4 結(jié)論

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