張 菁，郭 丹,2

擬蛇算法在蛋白質折疊模擬中的應用可行性研究

張 菁1，郭 丹1,2

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

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

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

0 引言

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

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

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

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

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

1 擬蛇算法

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

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

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

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

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

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

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

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

2 收斂性的分析

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

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

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

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

3 穩(wěn)定性分析

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

方程式1定義速度函數(shù)，方程式2是牛頓定律用之于震蕩的擺，對式2兩邊對t求導，然后將式1帶入式2的求導，結果消去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]的概念在有關耦合非線性微分方程的討論中是很重要的，在缺乏完整分析一個動力學系統(tǒng)的情況下，擺的相軌線可用于有關運動本質的穩(wěn)定性的分析。

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

所以我們可以得到：

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

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

當相平面軌線的螺旋線趨向于奇點，如圖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ωω=±虛

擺有兩個純虛根，并且有，擺反映在坐標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)定性恰好與蛋白質折疊最后形成能量最小的穩(wěn)定狀態(tài)的理論相吻合。

4 結論

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

[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, 張菁. 模擬蛋白質折疊過程的新算法研究. 生物信息學[J]. 2011, 9(31): 142-145.

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

[16] 張菁, 張?zhí)祚Y. 蛋白質折疊過程模型. 應用科技[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

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

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

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