蛋白質二級結構預測概率圖模型的改進

趙凌琪，朱麗娟，王柯靜，董小慶，張　屹，

(1.內蒙古民族大學計算機科學與技術學院，內蒙古通遼　028043；2.河北科技大學理學院，河北石家莊　050018)

?

蛋白質二級結構預測概率圖模型的改進

趙凌琪1，朱麗娟2，王柯靜2，董小慶2，張屹1，2

(1.內蒙古民族大學計算機科學與技術學院，內蒙古通遼028043；2.河北科技大學理學院，河北石家莊050018)

摘要：蛋白質二級結構與蛋白質三級結構及蛋白質功能密切相關，是生物信息學研究的熱點，其中概率圖模型隱馬爾可夫算法(HMM)是該領域研究的重要工具。但是在實際應用中，存在著HMM訓練下溢、不同訓練集的效果差異較大及參數優化困難等問題。對預測蛋白質二級結構時HMM遇到的訓練下溢問題提出了改進方案；首次提出8-狀態HMM來預測蛋白質二級結構，并且將參數B改進成為包含狀態轉移信息的三維參數；為了改進最優HMM模型的確定方法，用每個樣本分別對初始HMM模型進行訓練，得到一系列新的模型，然后對這些新模型的參數求均值，將求得的均值作為最優模型的參數。這些改進方法提高了HMM預測蛋白質二級結構的準確率，為HMM的進一步優化打下良好的基礎。

關鍵詞：應用生物化學；概率圖；蛋白質二級結構；HMM；下溢；參數優化

生物學原理[1]指出：DNA序列首先通過轉錄、翻譯生成氨基酸序列，氨基酸序列再經過盤曲折疊形成復雜的二級、三級等空間結構。研究發現，蛋白質二級和三級結構能有效揭示蛋白質的生物功能[2-4]，可以用X射線晶體學技術、電子顯微鏡技術和核磁共振衍射技術(NMR)等來測定它們[5]。這些方法雖然比較直接，但預測時周期長、成本高、技術難度大。人們越來越多地關注生物信息學的應用，即基于經驗知識與計算化學、統計物理學、信息學等方法的結合，從理論上預測蛋白質的空間結構[6-9]，其中二級結構是預測三級結構的基礎。蛋白質二級結構的主要形式包括α-螺旋、310-螺旋、π-螺旋、β-折疊、β-轉角和無規則卷曲等。最流行的二級結構預測方法有DSSP[10]，STRIDE[11]， DEFINE[12]等，通常利用DSSP算法將蛋白質二級結構分為8類：H(α-helix)，G(310-helix)，I(π-helix)，E(extended β-strand)，B(isolated β-strand)，T(turns)，S(bend)，C(coil)[5,13]。在進行蛋白質二級結構預測時，一般又把這8類歸并為3大類，即H(helix)，E(sheet)和C(coil)，通常有CK模式[14]、EHL模式[15]和PSIPRED[16]這3種歸類方法。目前，大多采用EHL模式歸類方法，即 H，G，T→H；E，B→E；其余→C[13]。在對蛋白質二級結構進行預測時，選取的特征有氨基酸的親水性、疏水性和極性[13]，蛋白質二級結構SS-8的8種狀態等[13,17]，而其預測方法則包括最近鄰方法[18-20]、人工神經網絡(ANN)[16,21-22]、支持向量機(SVM)[23-24]和隱馬爾可夫算法(HMM)[25-26]等。

本文研究的蛋白質二級結構預測算法可以同時實現2個目的：界定一個蛋白質序列中所蘊含的二級結構片段的邊界及對分割出來的片段進行EHL模式的分類預測。

1材料與方法

1.1數據集與準確率

在對HMM算法進行改進時，采用目前使用較多的CUFF和BARTON建立的CB513數據集(http://www.compbio.dundee.ac.uk/jpred/about.shtml)，包括513條蛋白質，分別用X射線測定二級結構，分辨率>2.5 ?，相似性<25%。首先對該數據集進行預處理，去掉16條長度小于30的序列，然后去掉5條含有‘？’的序列，剩下492條蛋白質序列。將492條序列隨機分為7等份，每次都取其中的1份(72條)作為測試集，取剩下的6份(即420條)作訓練集；如此循環7次，完成7重交叉檢驗。下文中提到的準確率都是這7重交叉檢驗的平均準確率。

準確率的定義為一條氨基酸序列的每個氨基酸都從屬于蛋白質二級結構狀態中的一種，在對蛋白質二級結構進行預測時，是對其每個氨基酸的所屬狀態進行預測。本條序列的預測準確率定義為

而基于某個HMM對一組序列進行蛋白質二級結構預測的準確率定義為對所有序列預測準確率的平均值。

1.2隱馬爾可夫算法

HMM是一種概率圖算法，在語音識別[7]和生物信息學中[8-9]有廣泛應用。以往的蛋白質二級結構預測常利用3-狀態或7-狀態HMM，由于7-狀態比3-狀態包含的蛋白質信息較多，所以前者預測精度較高。因此，本文蛋白質二級結構預測在7-狀態的基礎上進行改進，提出8-狀態HMM，把蛋白質的8種二級結構狀態分別作為狀態S1，S2，…，S8，包括α-螺旋的起始、中間和結束狀態HB，H，HE(α-螺旋的第1個氨基酸狀態為HB，最后一個氨基酸狀態為HE，中間部分的氨基酸狀態為H)，β-折疊的起始、中間和結束狀態EB，E，EE(氨基酸狀態歸屬情況同α-螺旋)，無規則卷曲狀態C及非二級結構狀態F。蛋白質的每個氨基酸都從屬于8種狀態的一種，隨著同一蛋白質上各種二級結構的交替出現，氨基酸的8種狀態之間就發生了“轉移”(transition)，轉移概率矩陣記為A8×8。HMM把每個氨基酸看成是在該氨基酸的當前狀態之下依照概率矩陣B8×20而“發出”(emit)的，加上初始狀態分布π，M=(π,A,B)就被稱為HMM模型。一個蛋白質序列的氨基酸是“可見”(observable)的符號，而蛋白質上的二級結構則是“隱含”(hidden)的狀態，這就是HMM的由來。 顯然，HMM試圖用統一的狀態轉移矩陣和各狀態下可見符號的出現概率來描述蛋白質序列中的二級結構與氨基酸序列的依存性，從而用這種依存性來預測陌生蛋白質中二級結構分布。 實際上，還可以建立2個連續狀態組合成的8×8=64種狀態甚至83=512狀態等模型，但是隨著矩陣A和矩陣B的增大，計算量也會空前增大。所以，該文只考慮8-狀態的HMM模型。

一般來說，利用HMM來預測蛋白質二級結構會涉及到以下3個問題。

問題1求由已知HMM模型生成已知氨基酸序列的概率。

給定蛋白質序列O=O1,O2,…,OT以及訓練好的模型M，計算條件概率P(O|M)的值。基于不同的模型M，同一條蛋白質序列的出現概率值可以不同。計算條件概率P(O|M)的算法有前向算法、后向算法及前后向算法[5,13]。

前向算法的步驟如下(其他類似)。

問題2已知HMM模型和氨基酸序列，求最佳二級結構狀態序列。

給定觀察序列O=O1,O2,…,OT以及模型M，用動態規劃算法把蛋白質序列分成不同階段，通過把條件概率每步最大化來找到一個概率最大的狀態序列S=S1,S2,…,ST，作為觀察序列O的最佳解釋。

解決該問題的算法為動態規劃的Viterbi算法[5,13]。 1)初始化：α1(i)=1,1≤i≤N; 2)每步都追求最優化的遞歸：αt+1(j)=max(αt(i)aijbij(Ot)),1≤t≤(T-1),1≤j≤N; 3)得到最終結果：P(O|M)=max(αT(i)),1≤i≤N。

問題3由已知序列和二級結構的訓練集得到最佳HMM模型。

給定觀察序列O=O1,O2,…,OT的集合，需要找到最佳模型M=(π，A,B)，使得P(O|M)最大。基于訓練集中的420條氨基酸序列，如果要找到一個包含盡可能多的序列與二級結構對應信息的模型，必須把模型M在各個氨基酸序列上反復迭代來收集信息和改進模型。通過啟發迭代來訓練模型M=(π,A,B)的算法為Baum-Welch算法，該算法中用來優化矩陣A和B中元素的迭代重估公式為

1.3原有蛋白質二級結構預測的HMM模型中存在的問題和本文的改進方案

人們用3-狀態和7-狀態HMM對蛋白質二級結構進行預測時[5,13]是基于3種二級結構來定義狀態的，未考慮到非二級結構的狀態F，本文中加上了非二級結構的狀態F。參數B在蛋白質二級結構預測時起著很重要的作用，但其并未包含狀態間的轉移，本文把B改造成三維參數來包含狀態轉移的信息。另外，利用Baum-Welch算法進行參數重估，當訓練樣本不含某狀態時，該狀態轉移到其他狀態的情況就不存在，則其對應的參數值為不定數，即訓練下溢。針對訓練下溢的情況，本文的改進方案是當初始模型選定后，訓練參數直至下溢，保留這個過程中最佳模型的參數，而不使用添加因子等傳統手段。

2結果與討論

2.1新的8-狀態HMM算法流程

圖1　8-狀態HMM結構Fig.1　8-state HMM structure

通過對CB513數據集中的序列進行統計，α-螺旋的長度最少為3個氨基酸，為了提供更多的蛋白質結構信息，將α-螺旋的狀態H擴展為HB(起始位置)、H(中間位置)和HE(結束位置)。雖然折疊的長度最少是1，但將其狀態擴展為EB，E，EE后，預測準確率有所提高，故采取其3-狀態的情況。對于無規則卷曲，將其擴展為3-狀態后，預測準確率并沒有明顯提高，故采取其單狀態的情況。在此基礎上增加非二級結構狀態F，共計8-狀態，其HMM結構如圖1所示。在利用8-狀態HMM進行蛋白質二級結構預測時，首先根據其中的每個氨基酸的所屬結構將氨基酸序列轉化為狀態序列，然后通過統計得到狀態轉移概率矩陣A和8-狀態下20種氨基酸的“發出”概率矩陣B，這就是“由已知序列和二級結構的訓練集得到最佳HMM模型”的算法問題。基于這個HMM模型，針對一條陌生的序列，按著上面介紹的“已知HMM模型和氨基酸序列，求最佳二級結構狀態序列”算法流程，就可以預測這條陌生序列的二級結構了。

2.2 參數B定義的改進

在將不同的氨基酸序列預測為其對應的狀態序列時，參數B起著很重要的作用，B包含的信息越多，預測準確率就越高，故考慮將二維狀態的B改進為三維，使其也蘊含狀態間的轉移。即當B為二維時，B(i,k)表示狀態i輸出氨基酸k的概率；當B為三維時，B(i,j,k)表示狀態i轉移到狀態j時輸出氨基酸k的概率。由于二維參數B的大小是8×20，三維的大小是8×8×20，所以后者的運算速度會相對慢一些，但準確率有較明顯的提高。當初始參數中B為二維時，蛋白質二級結構預測的準確率為0.255 11；當B為三維時，蛋白質預測準確率為0.310 48。這說明三維B的確對算法有促進作用。

2.3針對下溢問題而采用的平均HMM模型

在初始HMM模型選定的情況下，選取第1個訓練樣本進行更新，然后隨機選取樣本繼續更新，直至下溢；選取第2個訓練樣本對初始HMM進行更新，直至下溢。如此下去，由420個訓練序列分別起始的更新流程會得到共420個HMM模型。利用每次訓練得到的HMM模型對測試集進行預測得到的準確率與訓練次數的關系見圖2。

圖2　更新次數及平均模型(或訓練樣本)個數與準確率的關系Fig.2　Relationship between renew times as well as numbers of average models with accuracy

由圖2可知，第1次訓練參數的預測效果最好，由于在用Baum-Welch算法進行參數訓練時，每訓練一次，參數中不定數的個數會增加，預測效果反而會變差。因此，由初始參數分別對每個樣本訓練一次，得到420個HMM模型(當然包含A和B)，然后分別用這420個HMM對測試集進行預測，經過統計，其中最好的HMM模型的準確率達到 0.361 84。為了進一步提高預測準確率，在刪掉108組準確率為0的HMM后，對剩余的312個HMM的參數矩陣A和B分別求平均值，最后利用這個“平均”HMM對測試集進行預測，準確率提高為0.401 55。總之，分別從每條訓練序列開始HMM模型的更新過程，不用“縮放因子”等傳統方法進行人為干預，而是讓它一直訓練直至下溢，選取其中準確率最高的HMM模型存放，每條訓練集序列都這樣訓練到下溢并存儲此過程中準確率最高的HMM模型，然后對有效的312個HMM模型中的參數A和B分別進行平均，作為最終的HMM模型的參數。可喜的是，基于這個最終的“平均”模型的預測精度的確提高了。

3結論

文獻[5]中3-狀態的預測精度為0.389 0，7-狀態的預測精度為0.414 3；文獻[13]中3-狀態的預測精度為0.447 1。在文獻[5]中采用的是HGI分類，相比EHL分類較容易預測；而文獻[13]為了避免下溢情況，在Baum-Welch算法的重估公式中引入拉普拉斯修正項，雖然精度有所提高，但沒有從根本上解決下溢問題。本文不使用“縮放因子”等傳統手段，通過在參數維數、訓練模型等方面的改進來提高預測精度，為應用HMM預測蛋白質二級結構的改進提供了新的思考方向。

本文闡述了HMM預測蛋白質二級結構時遇到的訓練下溢問題、非二級結構狀態和參數B的優化問題，并嘗試了改進方案，提高了應用HMM預測蛋白質二級結構的準確率。另外，本文是在沒有利用同源信息的情況下對HMM算法進行改進的，根據AYDIN等[27]的論述，這樣的結果更具有代表性。可見，本文的改進算法為模型的進一步優化打下了良好的基礎。

參考文獻/References:

[1]張海霞. 蛋白質二級結構預測方法研究[D].大連：大連理工大學, 2004.

ZHANG Haixia. The Research on Protein Secondary Structure Prediction Methods[D]. Dalian：Dalian University of Technology，2004.

[2]MARSDEN R，RANEA J，SILLERO A，et al. Exploiting protein structure data to explore the evolution of protein function and biological complexity[J]. Philosophical Transactions of the Royal Society of London, 2006, 361(1467): 425-440.

[3]WHISSTOCK J，LESK A. Prediction of protein function from protein sequence and structure[J]. Quarterly Reviews of Biophysics，2003，36(3): 307-340.

[4]DOMINGUES F，LENGAUER T. Protein function from sequence and structure data[J]. Applied Bioinformatics，2003，2(1): 3-12.

[5]林錦華. 基于隱馬爾可夫模型的蛋白質二級結構預測[D]. 福州: 福建農林大學，2012.

LIN Jinhua. Protein Secondary Structure Prediction Based on the Hidden Markov Model[D]. Fuzhou：Fujian Agriculture and Forestry University，2012.

[6]王鵬良，江壽平，羅宇，等. 蛋白質二級結構預測的綜合分析[J]. 物理化學學報，1990，6(6): 686-691.

WANG Pengliang，JIANG Shouping， LUO Yu, et al. Comprehensive analysis of the prediction of protein’s secondary structure[J]. Acta Physico-Chimica Sinica， 1990, 6(6): 686-691.

[7]LAWRENCE R，RABINER A.Tutorial on hidden Markov models and selected applications in speech recognition[J]. Proceedings of the IEEE，1989，77(2): 257-286.

[8]STANKE M，WAACK S. Gene prediction with a hidden Markov model and a new intron submodel[J]. Bioinformatics，2003，19(sup2): 215-225.

[9]PEDERSEN S，HEIN J. Gene finding with a hidden Markov model of genome structure and evolution[J]. Bioinformatics，2003，19(2): 219-227.

[10]KABSCH W，SANDER C. Dictionary of secondary structure pattern recognition of hydrogen-bonded and geometric features[J]. Biopolymers，1983，22(12): 2577-2637.

[11]HEINIG M，FRISHMAN D. STRIDE：Web server for secondary structure assignment from known atomic coordinates of proteins[J]. Nucleic Acids Research，2004，32: 500-502.

[12]RICHARDS F，KUNDROT C. Identification of structural motifs from protein coordinate data:Secondary structure and first-level supersecondary structure[J]. Proteins，1988，3(2): 71-84.

[13]石鷗燕. 蛋白質結構預測模型的研究[D]. 天津: 天津醫科大學，2008.

SHI Ouyan. Study on the Models of Protein Structure Prediction[D]. Tianjin:Tianjin Medical University，2008.

[14]CHANDONIA J, KARPLUS M. Neural networks for secondary structure and structural class predictions[J]. Protein Science, 1995, 4(2): 275-285.

[15]MOULT J，FIDELIS K，ZEMLA A，et al. Critical assessment of methods of protein structure prediction(CASP): Round Ⅳ[J]. Proteins，2001，45(sup5): 2-7.

[16]JONES D. Protein secondary structure prediction based on position-specific scoring matrices[J]. Journal of Molecular Biology，1999，292(2)：195-202.

[17]王勇獻. 蛋白質二級結構預測的模型與方法研究[D]. 長沙：國防科學技術大學，2004.

WANG Yongxian. Research on the Models and Methods of Protein[D]. Changsha：National University of Defense Technology，2004.

[18]LEVIN J，ROBSON B，GARNIER J. An algorithm for secondary structure determination in proteins based on sequence similarity[J]. Febs Letters，1986，205(2)：303-308.

[19]NISHIKAWA K，OOI T. Amino acid sequence homology applied to the prediction of protein secondary structures,and joint prediction with existing methods[J]. Biochim Biophys Acta，1986，871(1): 45-54.

[20]YI T，LANDER E. Protein secondary structure prediction using nearest-neighbor methods[J]. Journal of Molecular Biology，1993，232(4): 1117-1129.

[21]ROST B，SANDER C. Prediction of protein secondary structure at better than 70% accuracy[J]. Journal of Molecular Biology，1993，232(2): 584-599.

[22]CUFF J，BARTON G. Application of multiple sequence alignment profiles to improve protein secondary structure prediction[J]. Proteins，2000，40(3)：502-511.

[23]HUA S，SUN Z. A novel method of protein secondary structure prediction with high segment overlap measure: Support vector machine approach[J]. Journal of Molecular Biology，2001，308(2): 397-407.

[24]劉倩倩. 基于詞頻統計編碼和流形學習的蛋白質二級結構預測方法研究[D]. 天津：河北工業大學，2013.

LIU Qianqian. Research on Protein Secondary Structure Prediction Based on Word Frequency Statistics Coding and Manifold Learning[D]. Tianjin：Hebei University of Technology，2013.

[25]BYSTROFF C，THORSSON V，BAKER D. HMMS TR：A hidden Markov model for local sequence structure correlations in proteins[J]. Journal of Molecular Biology，2000, 301(1): 173-190.

[26]陳軍霞，劉紫玉. 基于Baum-Welch算法HMM模型的孤詞算法研究[J].河北科技大學學報，2015，36(1)：52-57.

CHEN Junxia，LIU Ziyu. Study on solitary word based on HMM model and Baum-Welch algorithm[J]. Journal of Hebei University of Science and Technology，2015，36(1): 52-57.

[27]AYDIN Z，ALTUNBASAK Y，BORODOVSKY M. Protein secondary structure prediction for a single-sequence using hidden semi-Markov models[J]. BMC Structural Biology，2006，7: 178-192.

Improved probability graph model for protein secondary structure prediction

ZHAO Lingqi1, ZHU Lijuan2, WANG Kejing2, DONG Xiaoqing2, ZHANG Yi1,2

(1.College of Computer Science and Technology, Inner Mongolia University for Nationalities, Tongliao, Inner Mongolia 028043, China; 2.School of Science, Hebei University of Science and Technology, Shijiazhuang, Hebei 050018, China)

Abstract:Protein secondary structure is closely related to protein tertiary structure and function, and became a hot topic in bioinformatics. The probability graph model HMM (Hidden Markov model) is an important tool in this field. In practice, there exist problems such as: HMM training underflow, significant result differences derived from different training set, and hard process of parameter optimization. In this paper, aiming at HMM training underflow problem when predicting protein secondary structure, we put forward a method for solving the underflow problem; propose an 8-state HMM model to predict protein secondary structure for the first time; and modify parameter to be a three-dimensional parameter containing the state transition information. In order to improve the method drilling the optimal HMM, we train the initial HMM model with each sample, and get a series of new models; then average the parameters of the new models, and the obtained average parameter values are used to construct the optimal HMM model. The improved method increases the accuracy of protein secondary structure prediction, hence it is a good foundation for further improvement of HMM.

Keywords:applied biochemistry； probability graph; protein secondary structure; HMM; underflow; parameter optimization

中圖分類號：O175.8

文獻標志碼：A

通訊作者：朱麗娟。E-mail:1439837430@qq.com

作者簡介：趙凌琪(1969—)，女，內蒙古赤峰人，教授，主要從事組合圖論算法方面的研究。

基金項目：國家自然科學基金(61261025，11171088)；河北省自然科學基金(A2015208108)

收稿日期：2015-11-05；修回日期：2016-01-13；責任編輯：張士瑩

doi:10.7535/hbkd.2016yx02009

文章編號：1008-1542(2016)02-0167-06

張屹教授。E-mail:zhaqi1972@163.com

趙凌琪，朱麗娟，王柯靜，等.蛋白質二級結構預測概率圖模型的改進[J].河北科技大學學報,2016,37(2):167-172.

ZHAO Lingqi，ZHU Lijuan，WANG Kejing，et al.Improved probability graph model for protein secondary structure prediction[J].Journal of Hebei University of Science and Technology,2016,37(2):167-172.