張 菁，郭 丹,2

擬蛇算法在蛋白質(zhì)折疊模擬中的應(yīng)用可行性研究

張 菁1，郭 丹1,2

(1. 哈爾濱工程大學(xué)，計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001；2. 哈爾濱商業(yè)大學(xué)，計算機(jī)與信息工程學(xué)院，黑龍江 哈爾濱 150028)

本文以計算分子生物學(xué)中的蛋白質(zhì)折疊模擬為研究對象，通過對一種新算法的可行性研究，意旨為領(lǐng)域內(nèi)的算法研究提供一種可驗證性的算法。本文從收斂性和穩(wěn)定性的角度，分析了擬蛇算法的核心函數(shù)，驗證該算法在蛋白質(zhì)折疊模擬中的應(yīng)用具有全局最優(yōu)值的收斂性，并且進(jìn)一步研究了這種仿生算法的運動穩(wěn)定性，驗證了擬蛇算法的運動軌跡會達(dá)到一個穩(wěn)定狀態(tài)，這與蛋白質(zhì)折疊最后形成能量最小的穩(wěn)定狀態(tài)的理論相吻合，驗證結(jié)果表明，擬蛇算法在蛋白質(zhì)折疊模擬中應(yīng)用具有可行性。

擬蛇算法；蛋白質(zhì)折疊；可行性研究；擺

0 引言

計算分子生物學(xué)[1]是運用計算機(jī)軟件理論和技術(shù)，以分子生物學(xué)數(shù)據(jù)為研究對象的交叉研究領(lǐng)域。分子生物學(xué)的海量數(shù)據(jù)需要計算機(jī)學(xué)科的高效處理方法作為實驗前數(shù)據(jù)預(yù)處理、數(shù)據(jù)篩選、數(shù)據(jù)預(yù)測，以及實驗后的數(shù)據(jù)分析處理的重要技術(shù)支撐；另一方面，計算機(jī)對復(fù)雜大數(shù)據(jù)的處理研究，需要真實的有意義的訓(xùn)練數(shù)據(jù)集，分子生物學(xué)的迅速發(fā)展，產(chǎn)生了大量的數(shù)據(jù)，而其間的關(guān)系也日趨復(fù)雜，這些龐大的復(fù)雜數(shù)據(jù)集合正是一個好的算法研究的數(shù)據(jù)驗證對象。

計算機(jī)模擬技術(shù)運用高速計算算法可以有效的對真實實驗中的復(fù)雜大數(shù)據(jù)集進(jìn)行分析和處理，并且通過對不同實驗環(huán)境和實驗因素的計算機(jī)模擬可控性，得到更多實驗的可能性和更精確的理想化結(jié)論，也可以清晰的通過構(gòu)象的變化來分析被模擬過程中哪些因素的影響格外重要，從而對功能關(guān)系的相互作用得出預(yù)測性的實驗依據(jù)幫助研究人員理解。

蛋白質(zhì)折疊是分子生物學(xué)上生物自我組織的一個典型實證。計算分子生物學(xué)中的蛋白質(zhì)折疊模擬算法是一個重要的研究對象。通過氨基酸長鏈彎曲、扭曲和折疊，蛋白質(zhì)可以在三維結(jié)構(gòu)上具有不同的構(gòu)象。結(jié)構(gòu)生物學(xué)已經(jīng)驗證，蛋白質(zhì)二維或三維結(jié)構(gòu)決定了蛋白質(zhì)的特定功能[2]。

目前人類對于折疊機(jī)制的了解程度還不足以精確的預(yù)測一個特定的序列如何折疊到天然構(gòu)象，或用逆折疊方法設(shè)計出能折疊到具有穩(wěn)定結(jié)構(gòu)的真實蛋白的新序列[3]。雖然這種結(jié)構(gòu)上的改變在自然界中只需要幾秒到幾分鐘，但到目前為止，即便是速度最快的計算機(jī)也無法完成。

蛋白質(zhì)由數(shù)目龐大的氨基酸組成，氨基酸不同結(jié)構(gòu)的排列可能性，決定了蛋白質(zhì)構(gòu)象可能具有無窮種結(jié)構(gòu)性狀，這也就意味著模擬算法的機(jī)制盡可能的要接近真實折疊機(jī)制，在眾多預(yù)測算法中，很多仿生預(yù)測算法應(yīng)運而生，用自然界已知的生物具有的自身特征性算法去解決未知的生物問題，如人工魚群算法[4,5]、遺傳算法[6,7]、人工神經(jīng)網(wǎng)絡(luò)[8,9]、粒子群算法[10,11]、蟻群算法[12,13]等。擬蛇算法[14]是一種新穎的蛋白質(zhì)折疊預(yù)測算法，本文對這一算法在蛋白質(zhì)折疊模擬中的應(yīng)用可行性進(jìn)行研究，以推動該算法在領(lǐng)域研究中的運用。

1 擬蛇算法

自然界中，蛇不具有四肢，但它可以靠軀體的形狀的改變來獲得移動的動力。在這一點上，它與蛋白質(zhì)無論從形狀到運動形式都有相似的地方。在粗糙得地面上蛇作一連串的波浪狀彎曲，體側(cè)不斷向地面施加壓力，由于地表的反作用力關(guān)系，所以能推動蛇體向前前進(jìn)。軀體較粗的蛇或接近獵物時，常常采取直線運動方式爬行。這類蛇的特點是腹鱗與其下方的組織之間較疏松，由于肋骨與腹鱗間的肋皮肌有節(jié)奏的收縮，使寬大的腹鱗依次豎立于地面，于是蛇體就能不停地呈直線向前運動。捕捉到獵物后，蛇會將自身盤緊促使獵物窒息死亡。蛇的運動具有運動穩(wěn)定性好，適應(yīng)地形環(huán)境能力強(qiáng)等特點。

其運動具有以下特點：1）能在凹凸不平的地面上移動，有良好的地形自適應(yīng)性；2）適合于在沼澤、沙漠等松軟環(huán)境中行進(jìn)；3）能通過孔洞等狹小而又彎曲的通路，有較強(qiáng)的過障礙能力；4）能經(jīng)常保持力學(xué)的穩(wěn)定狀態(tài)。

蛋白質(zhì)折疊的結(jié)果也是趨于形成低能量的力學(xué)的穩(wěn)定狀態(tài)的物質(zhì)。蛋白質(zhì)的折疊過程經(jīng)歷了一個中間狀態(tài)的，這種狀態(tài)被科學(xué)家形容為熔球[15]。熔球不像正常折疊后結(jié)構(gòu)緊密地蛋白那樣脆弱，這樣的結(jié)構(gòu)可以進(jìn)行拉扯，不會被輕易破壞。熔球具有正常蛋白所有的二級結(jié)構(gòu)，但是這種二級結(jié)構(gòu)尚未正確折疊形成更高級的結(jié)構(gòu)。當(dāng)?shù)鞍踪|(zhì)折疊成穩(wěn)定構(gòu)型時，其能量是最低的。蛇的運動與蛋白質(zhì)折疊在形狀和運動形式上有相似之處，因此研究和制作蛇形仿生算法來解決蛋白質(zhì)折疊問題具有一定的研究可能性。

擬蛇算法作為一種仿生算法，主要以蛋白質(zhì)折疊過程為研究對象，通過對蛇捕獲獵物的過程模擬蛋白質(zhì)折疊過程。以蛇的三種運動模式：波浪運動、直線式運動和盤繞運動，去模擬蛋白質(zhì)折疊過程：折疊初期的波浪運動、折疊過程中短暫的直線式運動和折疊后期的盤繞運動。

對于蛇捕食過程的描述：在其未發(fā)現(xiàn)捕食目標(biāo)前的覓食過程中蛇做波浪運動，通過隨機(jī)探測目標(biāo)的位置，即，當(dāng)其與食物（外力）距離遠(yuǎn)時（折疊開始時），或當(dāng)區(qū)域空間大，擁擠濃度低時，蛇的軀體作波浪運動，其從頭部至尾部，形成若干個波峰和波谷，波峰和波谷隨時間交替改變，肽鏈的移動路徑是正弦波；一旦鎖定捕食目標(biāo)，進(jìn)入攻擊狀態(tài)，即，當(dāng)其與食物（外力）距離近時（折疊中期），其改波浪運動為直線移動以快速接近獵物，長的肽鏈的移動路徑為直線式；當(dāng)捕獲食物后（折疊后期），其做盤繞運動，將獵物盤緊以穩(wěn)定捕獲狀態(tài)，進(jìn)而完成整個捕食過程，肽鏈的移動路徑是螺旋曲線。

在蛋白質(zhì)折疊模擬過程中擬蛇算法的實現(xiàn)步驟：1）初始狀態(tài)：隨機(jī)產(chǎn)生一條蛋白質(zhì)序列的構(gòu)型。給出氨基酸殘基個數(shù)，設(shè)定肽鏈折疊的最大距離參數(shù)，更新速度步長，給肽鏈最小能量設(shè)初值；2）當(dāng)折疊距離小于折疊的最大距離時，做波浪運動，并計算肽鏈總的最小能量值；3）當(dāng)折疊距離等于折疊的最大距離時，做直線運動，并計算肽鏈總的最小能量值；4）當(dāng)折疊距離大于折疊的最大距離時，做盤繞運動，并計算肽鏈總的最小能量值。5）肽鏈總的最小能量不再變化時，輸出蛋白質(zhì)構(gòu)型，算法結(jié)束[16]。

擬蛇算法根據(jù)六個典型的蛋白質(zhì)空間結(jié)構(gòu)，在蛋白質(zhì)折疊模擬過程中，通過改變參數(shù)演化兩種函數(shù)形式，圓型和扣型兩種類型。擬蛇算法的核心函數(shù)是：

本文從收斂性和穩(wěn)定性兩個方面，通過對核心函數(shù)的分析，驗證擬蛇在蛋白質(zhì)折疊模擬中的應(yīng)用可行性。

2 收斂性的分析

對于一種算法，其收斂性往往是人們所首要關(guān)心的問題。在擬蛇算法中，蛇的正弦移動行為奠定了算法收斂的基礎(chǔ)，直線移動行為增強(qiáng)了算法收斂的穩(wěn)定性和全局性，盤繞行為則增強(qiáng)了算法收斂的快速性和全局性，其行為過程也對算法收斂的速度和穩(wěn)定性提供了保障?？偟膩碚f，算法中對各參數(shù)的取值范圍還是很寬容的，并且對算法的初值也基本無要求。

擬蛇算法中殘基個數(shù)，殘基移動的最大速度和步長在迭代次數(shù)100時，這三個參數(shù)對算法收斂性的影響都是有限的，而合理選擇迭代次數(shù)是提高算法效率的關(guān)鍵。這一規(guī)律是否具有一般性還有待進(jìn)一步研究。

由于算法參數(shù)不同，收斂過程和結(jié)果也存在一定的差異，所以在以下的討論中，將針對每一種參數(shù)連續(xù)多次進(jìn)行全局尋優(yōu)收斂實驗作為一組數(shù)據(jù)，然后對多組數(shù)據(jù)進(jìn)行統(tǒng)計分析，從而確定各參數(shù)的性質(zhì)。通常數(shù)據(jù)的均值(Mean)表征本組數(shù)據(jù)的優(yōu)劣，其標(biāo)準(zhǔn)誤差(SE)則可以反映該組數(shù)據(jù)的穩(wěn)定性。

基于上面的二維正弦函數(shù)分析算法的收斂性，其中，0≤x≤20,0≤y≤20。該函數(shù)的全局極大值的周圍被無窮個極小值(波谷)所包圍，再外圍是無窮個局部極大值(波峰)，在最遠(yuǎn)端的四個角上又是處于局部極大值。使用該函數(shù)作為實驗函數(shù)應(yīng)該具有一定的代表性。對于該函數(shù)，從擬蛇算法的任何初始值出發(fā)，都能收斂到全局最優(yōu)值，并且收斂時間最短為幾秒。

3 穩(wěn)定性分析

擬蛇算法的核心是一種振蕩形式[16]。一個理想的擺，力是Fkx=-，位置坐標(biāo)x，質(zhì)量為m。位置坐標(biāo)可以表示為：x=x(t)，速度函數(shù)為v=v(t)。這兩個函數(shù)彼此間有以下的關(guān)系：

方程式1定義速度函數(shù)，方程式2是牛頓定律用之于震蕩的擺，對式2兩邊對t求導(dǎo)，然后將式1帶入式2的求導(dǎo)，結(jié)果消去dx(t)/dt便得到一個二階常系數(shù)線性微分方程，可以解出v(t)

圖1a 速度v隨時間的t的變化Fig.1 a velocity change according to time

圖1給出由公式4所給出的擺狀態(tài)的時間演化圖。這個擺既在時間上有位置的移動，又在時間上有速度的變化，所以這系統(tǒng)的點的軌跡是上升的螺旋線。

相軌線[12-14]的概念在有關(guān)耦合非線性微分方程的討論中是很重要的，在缺乏完整分析一個動力學(xué)系統(tǒng)的情況下，擺的相軌線可用于有關(guān)運動本質(zhì)的穩(wěn)定性的分析。

相軌線是三維螺旋在v-x平面上的投影。也就是說我們要構(gòu)造一個函數(shù)v=v(x)。這可以由公式5，6消去時間而做到。

所以我們可以得到：

對給出的初始條件來說，或者等價地說，對一個固定值K，公式（7）代表v-x平面上的一個橢圓如圖2所示。每一個K值，有一個橢圓與之對應(yīng)。

圖2 一個理想擺在相平面上的軌跡Fig.2 An idea Gradual stable focus

當(dāng)相平面軌線的螺旋線趨向于奇點，如圖3，從而這個奇點叫做穩(wěn)定焦點。在這種情況下，總的解趨向于一種振蕩運動中的定態(tài)，是漸近穩(wěn)定的。

圖3 漸近穩(wěn)定焦點，螺旋軌跡收斂于奇點Fig.3 Gradually to stable focus, screw track to odd spot

理想狀態(tài)下，擬蛇算法的核心函數(shù)在振蕩模型下，擺的特征方程：

即iωω=±虛

擺有兩個純虛根，并且有，擺反映在坐標(biāo)x與v上的代表點在相平面上隨時間而作周期的變化。因此，其相軌跡線必然都是一些圍繞奇點的封閉曲線。

擺是在小的瞬時的位移x=δx，擺就開始搖動，而此運動是x=x(t)與v=v(t)隨時間而減少，并最后為零，則擺的位置x=0，v=0,是一個穩(wěn)定的狀態(tài)，我們把這一點叫做穩(wěn)定奇點。

對于施加在擺上的每個初始力，會出現(xiàn)一條新的封閉的相軌線，如圖2所示。一個理想的擺可以規(guī)律性地振蕩著，只要沒有新的擾動去干擾它的運動，此時的奇點是穩(wěn)定的。擺運動軌跡的穩(wěn)定性恰好與蛋白質(zhì)折疊最后形成能量最小的穩(wěn)定狀態(tài)的理論相吻合。

4 結(jié)論

本文針對蛋白質(zhì)折疊模擬研究中一種新算法的可行性研究，對擬蛇算法的核心函數(shù)進(jìn)行了收斂性和穩(wěn)定性分析。通過對算法收斂性的分析，以迭代次數(shù)100為限制，驗證該算法核心函數(shù)從任意初始值出發(fā)，都能收斂到全局最優(yōu)值，并具有較快收斂速度，能有效地對蛋白質(zhì)折疊進(jìn)行模擬預(yù)測。通過對算法穩(wěn)定性分析，從振蕩理論的擺軌跡的相平面穩(wěn)定性研究，驗證了在理想狀態(tài)下擬蛇算法的運動軌跡在能達(dá)到一個穩(wěn)定狀態(tài)，這與蛋白質(zhì)折疊最后形成能量最小的穩(wěn)定狀態(tài)的理論相吻合。擬蛇算法僅使用了目標(biāo)問題的函數(shù)值，算法簡單，具有很強(qiáng)的跳出局部極值的能力，算法的穩(wěn)定性確保其能快速跟蹤隨著工作狀況或其他因素的變更造成的極值點的漂移變化，獲得全局最優(yōu)解。綜上所述，擬蛇算法在蛋白質(zhì)折疊模擬研究中，具有應(yīng)用可行性。

[1] ZHANG Y, Min X J. Computational molecular biology: an integration of experimental molecular and genome biology with computational technology: computational molecular biology[J]. 2011, 1(1): 1-3.

[2] GEORGINA M, DANCO D. Incorporating several features in the protein ray descriptor for more accurate protein 3D structure retrieval: Proceedings of the ACM workshop on 3Dobject retrieval [C]. 2012, 51-56.

[3] SCHAEFFER R D, DAGGETT V. Protein folds and protein folding: protein engineering design & selection[J]. 2011, 24(1-2): 11-19.

[4] CUI Z H, ZHANG Y. Swarm Intelligence in Bioinformatics: methods and implementations for discovering patterns of multiple sequences: journal of nanoscience and nanotechnology[J]. 2014, 14(2): 1746-1757.

[5] CUI Z H, ZHANG Y. Methods and implementations for discovering patterns of multiple sequences: journal of nanoscience and nanotechnology[J]. 2014, 14(2): 1746-1757.

[6] ISLAM M L, SHATABDA S, RAHMAN M S. GreMuTRRR: A novel genetic algorithm to solve distance geometry problem for protein structures: 2014 international conference on electrical and computer engineering (ICECE)[C]. 2014, 357-360.

[7] SHIN JM, LEE B, CHO KH. A new efficient conformational search method for ab initio protein folding study: window growth evolutionary algorithm: bulletin of the Korean chemical society[J]. 2016, 37(12) 1971-1976

[8] FLORIDO J P, POMARES H, ROJAS I. Prediction of functional associations between proteins by means of a cost-sensitive artificial neural network: lecture notes in computer science[J]. 2011, 6692: 194-201.

[9] THANGSUNAN P, KITTIWACHANA S, MEEPOWPAN P, KUNGWAN N, PRANGKIO P, HANNONGBUA S, SUREE N. Rapid activity prediction of HIV-1 integrase inhibitors: harnessing docking energetic components for empirical scoring by chemometric and artificial neural network approaches: journal of computer-aided molecular design [J]. 2016, 30(6): 471-488.

[10] KONDOV I. Protein structure prediction using distributed parallel particle swarm optimization : natural computing [J]. 2013, 12(1): 29-41.

[11] CHEUNG N J, DING X M,SHEN H B. Protein folds recognized by an intelligent predictor based-on evolutionary end structural information :journal of computational chemistry. 2016, 37(4): 426-436.

[12] OAKLEY M T,RICHARDSON E G, CARR H. Protein structure optimization with a "lamarckian" ant colony algorithm: IEEE-ACM transactions on computational biology and bioinformatics[C]. 2013, 10(6): 1548-1552.

[13] RAY S S,PAL S K. RNA Secondary structure prediction using soft computing: IEEE-ACM transactions on computational biology and bioinformatics[C]. 2013, 10(1): 2-17.

[14] 張?zhí)祚Y, 張菁. 模擬蛋白質(zhì)折疊過程的新算法研究. 生物信息學(xué)[J]. 2011, 9(31): 142-145.

[15] https://en.wikipedia.org/wiki/Molten_globule

[16] 張菁, 張?zhí)祚Y. 蛋白質(zhì)折疊過程模型. 應(yīng)用科技[J]. 2011, 38(7): 41-43.

Application Feasibility Study on Snake Algorithm of Protein Folding Simulation

ZHANG Jing1, GUO Dan2
(1. Harbin Engineering University, College of Computer Science and Technology, Heilongjiang Harbin 150001, China; 2. Harbin University of Commerce, School of Computer and Information Engineering, Heilongjiang Harbin 150028, China)

The research object of the paper is a new simulation algorithm for protein folding in computational molecular biology. From the view of the astringency and stability, the algorithm research in the field of the purpose of this paper is to provide a kind of algorithm of verifiability. In this paper, snake algorithm was validated is accord with the global optimum of the astringency in the application of protein folding simulation by analyses the core function. And the project further studies the movement stability of the bionic algorithm. Proved that the proposed algorithm of snake trajectory will reach a steady state, which was consistent with Minimum energy of the formation of stable state theory when protein folding is complete. Results show that the proposed snake algorithm was feasible for application in the numerical simulation of protein folding.

Snake algorithm; Protein folding; Feasibility study; Pendulum

TP39 3.08

A

10.3969/j.issn.1003-6970.2017.02.017

黑龍江省教育廳科學(xué)技術(shù)研究基金項目(12541211)

張菁(1965-)，女，博士后，教授，博士生導(dǎo)師，研究方向為計算分子生物學(xué)，虛擬現(xiàn)實，醫(yī)學(xué)圖像處理；郭丹(1978-)，女，博士研究生，副教授，研究方向為計算分子生物學(xué)，大數(shù)據(jù)可視化。

本文著錄格式：張菁，郭丹. 擬蛇算法在蛋白質(zhì)折疊模擬中的應(yīng)用可行性研究[J]. 軟件，2017，38（2）：75-79