论文部分内容阅读
摘要：
蛋白质二级结构与蛋白质三级结构及蛋白质功能密切相关，是生物信息学研究的热点，其中概率图模型隐马尔可夫算法（HMM）是该领域研究的重要工具。但是在实际应用中，存在着HMM训练下溢、不同训练集的效果差异较大及参数优化困难等问题。对预测蛋白质二级结构时HMM遇到的训练下溢问题提出了改进方案；首次提出8状态HMM来预测蛋白质二级结构，并且将参数B改进成为包含状态转移信息的三维参数；为了改进最优HMM模型的确定方法，用每个样本分别对初始HMM模型进行训练，得到一系列新的模型，然后对这些新模型的参数求均值，将求得的均值作为最优模型的参数。这些改进方法提高了HMM预测蛋白质二级结构的准确率，为HMM的进一步优化打下良好的基础。
关键词：应用生物化学；概率图；蛋白质二级结构；HMM；下溢；参数优化
中图分类号：O175.8文献标志码：A
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 8state HMM model to predict protein secondary structure for the first time； and modify parameter to be a threedimensional 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
生物学原理[1]指出：DNA序列首先通过转录、翻译生成氨基酸序列，氨基酸序列再经过盘曲折叠形成复杂的二级、三级等空间结构。研究发现，蛋白质二级和三级结构能有效揭示蛋白质的生物功能[24]，可以用X射线晶体学技术、电子显微镜技术和核磁共振衍射技术（NMR）等来测定它们[5]。这些方法虽然比较直接，但预测时周期长、成本高、技术难度大。人们越来越多地关注生物信息学的应用，即基于经验知识与计算化学、统计物理学、信息学等方法的结合，从理论上预测蛋白质的空间结构[69]，其中二级结构是预测三级结构的基础。蛋白质二级结构的主要形式包括α螺旋、310螺旋、π螺旋、β折叠、β转角和无规则卷曲等。最流行的二级结构预测方法有DSSP[10]，STRIDE[11]， DEFINE[12]等，通常利用DSSP算法将蛋白质二级结构分为8类：H（αhelix），G（310helix），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]，蛋白质二级结构SS8的8种状态等[13，17]，而其预测方法则包括最近邻方法[1820]、人工神经网络（ANN）[16，2122]、支持向量机（SVM）[2324]和隐马尔可夫算法（HMM）[2526]等。
本文研究的蛋白质二级结构预测算法可以同时实现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重交叉检验的平均准确率。
准确率的定义为一条氨基酸序列的每个氨基酸都从属于蛋白质二级结构状态中的一种，在对蛋白质二级结构进行预测时，是对其每个氨基酸的所属状态进行预测。本条序列的预测准确率定义为
准确率=[SX（]本序列中被正确预测结构状态的氨基酸数[]本序列中的氨基酸总数[SX）]×100% ，
而基于某个HMM对一组序列进行蛋白质二级结构预测的准确率定义为对所有序列预测准确率的平均值。
1.2隐马尔可夫算法
HMM是一种概率图算法，在语音识别[7]和生物信息学中[89]有广泛应用。以往的蛋白质二级结构预测常利用3状态或7状态HMM，由于7状态比3状态包含的蛋白质信息较多，所以前者预测精度较高。因此，本文蛋白质二级结构预测在7状态的基础上进行改进，提出8状态HMM，把蛋白质的8种二级结构状态分别作为状态[WTBX]S1，S2，…，S8，包括α螺旋的起始、中间和结束状态HB，H，HE（α螺旋的第1个氨基酸状态为HB，最后一个氨基酸状态为HE，中间部分的氨基酸状态为H），β折叠的起始、中间和结束状态EB，E，EE（氨基酸状态归属情况同α螺旋），无规则卷曲状态C及非二级结构状态F。蛋白质的每个氨基酸都从属于8种状态的一种，随着同一蛋白质上各种二级结构的交替出现，氨基酸的8种状态之间就发生了“转移”（transition），转移概率矩阵记为[WTHX]A8×8。HMM把每个氨基酸看成是在该氨基酸的当前状态之下依照概率矩阵[WTHX]B8×20而“发出”（emit）的，加上初始状态分布[WTBX]π，M=（π，A，B）就被称为HMM模型。一个蛋白质序列的氨基酸是“可见”（observable）的符号，而蛋白质上的二级结构则是“隐含”（hidden）的状态，这就是HMM的由来。 显然，HMM试图用统一的状态转移矩阵和各状态下可见符号的出现概率来描述蛋白质序列中的二级结构与氨基酸序列的依存性，从而用这种依存性来预测陌生蛋白质中二级结构分布。 实际上，还可以建立2个连续状态组合成的8×8=64种状态甚至83=512状态等模型，但是随着[WTHX]矩阵A和矩阵B[WTBZ]的增大，计算量也会空前增大。所以，该文只考虑8状态的HMM模型。
一般来说，利用HMM来预测蛋白质二级结构会涉及到以下3个问题。
问题1求由已知HMM模型生成已知氨基酸序列的概率。
给定蛋白质序列[WTBX]O=O1，O2，…，OT以及训练好的模型M，计算条件概率P（O|M）的值。基于不同的模型M，同一条蛋白质序列的出现概率值可以不同。计算条件概率P（O|M）的算法有前向算法、后向算法及前后向算法[5，13]。
前向算法的步骤如下（其他类似）。
1）初始化：α1（i）=1，1≤i≤N； 2）递归：
αt+1（j）=∑[DD（]N[]i=1[DD）]αt（i）aijbij（Ot），1≤t≤（T-1），1≤j≤N；3）累加：P（O|M）=∑[DD（]N[]i=1[DD）]αT（i）。此评估问题的解决只是简单的迭代，没有运用复杂的算法。这里T是氨基酸序列的长度；N=8是状态数；状态i→j转移概率组成矩阵[WTHX]A[WTBX]=（aij），而这一状态的转移是由第t个位置上氨基酸Ot的输出来实现的，概率是bij（Ot）；αt（i）是一个概率值，表示第t个位置的氨基酸处于第i个状态的概率。如果氨基酸序列较长，则当t大于某一值时，α值会很小，几乎接近0，Matlab程序会默认为0。为了避免这种下溢情况，本文采用文献[5]中的比例因子方法。
问题2已知HMM模型和氨基酸序列，求最佳二级结构状态序列。
给定观察序列[WTBX]O=O1，O2，…，OT以及模型M，用动态规划算法把蛋白质序列分成不同阶段，通过把条件概率每步最大化来找到一个概率最大的状态序列S=S1，S2，…，ST，作为观察序列O的最佳解释。
解决该问题的算法为动态规划的Viterbi算法[5，13]。 [WTBX]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模型。
给定观察序列[WTBX]O=O1，O2，…，OT的集合，需要找到最佳模型M=（π，A，B），使得P（O|M）最大。基于训练集中的420条氨基酸序列，如果要找到一个包含尽可能多的序列与二级结构对应信息的模型，必须把模型M在各个氨基酸序列上反复迭代来收集信息和改进模型。通过启发迭代来训练模型M=（π，A，B）的算法为BaumWelch算法，该算法中用来优化矩阵[WTHX]A和B[WTBX]中元素的迭代重估公式为
显然这个启发式算法是非常费时间的，与上面的简单迭代和流程固定的动态规划不同。当不同氨基酸序列之间信息差异很大时，会在某些情况下出现随着训练次数或训练序列数的增加效果反而下降的情况。本文探讨了如何寻找最佳训练集的问题。 利用HMM进行蛋白质二级结构预测时，先是基于训练集中的420条氨基酸序列选出最优的[WTHX]矩阵A，B；然后针对二级结构的氨基酸序列，用训练出来的模型来“解码”，预测其最佳的二级结构状态序列。
1.3原有蛋白质二级结构预测的HMM模型中存在的问题和本文的改进方案
人们用3状态和7状态HMM对蛋白质二级结构进行预测时[5，13]是基于3种二级结构来定义状态的，未考虑到非二级结构的状态F，本文中加上了非二级结构的状态F。参[WTBX]数B在蛋白质二级结构预测时起着很重要的作用，但其并未包含状态间的转移，本文把B改造成三维参数来包含状态转移的信息。另外，利用BaumWelch算法进行参数重估，当训练样本不含某状态时，该状态转移到其他状态的情况就不存在，则其对应的参数值为不定数，即训练下溢。针对训练下溢的情况，本文的改进方案是当初始模型选定后，训练参数直至下溢，保留这个过程中最佳模型的参数，而不使用添加因子等传统手段。
2结果与讨论
2.1新的8状态HMM算法流程
通过对CB513数据集中的序列进行统计，α螺旋的长度最少为3个氨基酸，为了提供更多的蛋白质结构信息，
将α螺旋的状态H扩展为HB（起始位置）、H（中间位置）和HE（结束位置）。虽然折叠的长度最少是1，但将其状态扩展为EB，E，EE后，预测准确率有所提高，故采取其3状
态的情况。对于无规则卷曲，将其扩展为3状态后，预测准确率并没有明显提高，故采取其单状态的情况。在此基础上增加非二级结构状态F，共计8状态，其HMM结构如图1所示。在利用8状态HMM进行蛋白质二级结构预测时，首先根据其中的每个氨基酸的所属结构将氨基酸序列转化为状态序列，然后通过统计得到状态转移概率矩阵[WTHX]A和8状态下20种氨基酸的“发出”概率矩阵[WTHX]B，这就是“由已知序列和二级结构的训练集得到最佳HMM模型”的算法问题。基于这个HMM模型，针对一条陌生的序列，按着上面介绍的“已知HMM模型和氨基酸序列，求最佳二级结构状态序列”算法流程，就可以预测这条陌生序列的二级结构了。
2.2 参数B定义的改进
在将不同的氨基酸序列预测为其对应的状态序列时，参数[WTBX]B起着很重要的作用，[WTBX]B包含的信息越多，预测准确率就越高，故考虑将二维状态的[WTBX]B改进为三维，使其也蕴含状态间的转移。即当[WTBX]B[WTBX]为二维时，B（i，k）表示状态i输出氨基酸k的概率；当[WTBX]B[WTBX]为三维时，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可知，第1次训练参数的预测效果最好，由于在用BaumWelch算法进行参数训练时，每训练一次，参数中不定数的个数会增加，预测效果反而会变差。因此，由初始参数分别对每个样本训练一次，得到420个HMM模型（当然包含[WTHX]A和B），然后分别用这420个HMM对测试集进行预测，经过统计，其中最好的HMM模型的准确率达到 0.361 84。为了进一步提高预测准确率，在删掉108组准确率为0的HMM后，对剩余的312个HMM的参数矩阵[WTHX]A和B分别求平均值，最后利用这个“平均”HMM对测试集进行预测，准确率提高为0.401 55。总之，分别从每条训练序列开始HMM模型的更新过程，不用“缩放因子”等传统方法进行人为干预，而是让它一直训练直至下溢，选取其中准确率最高的HMM模型存放，每条训练集序列都这样训练到下溢并存储此过程中准确率最高的HMM模型，然后对有效的312个HMM模型中的参数[WTBX]A和B分别进行平均，作为最终的HMM模型的参数。可喜的是，基于这个最终的“平均”模型的预测精度的确提高了。
3结论
文献[5]中3状态的预测精度为0.389 0，7状态的预测精度为0.414 3；文献[13]中3状态的预测精度为0.447 1。在文献[5]中采用的是HGI分类，相比EHL分类较容易预测；而文献[13]为了避免下溢情况，在BaumWelch算法的重估公式中引入拉普拉斯修正项，虽然精度有所提高，但没有从根本上解决下溢问题。本文不使用“缩放因子”等传统手段，通过在参数维数、训练模型等方面的改进来提高预测精度，为应用HMM预测蛋白质二级结构的改进提供了新的思考方向。
本文阐述了HMM预测蛋白质二级结构时遇到的训练下溢问题、非二级结构状态和参数[WTBX]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）： 425440.
[3]WHISSTOCK J，LESK A. Prediction of protein function from protein sequence and structure[J]. Quarterly Reviews of Biophysics，2003，36（3）： 307340.
[4]DOMINGUES F，LENGAUER T. Protein function from sequence and structure data[J]. Applied Bioinformatics，2003，2（1）： 312.
[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）： 686691.
WANG Pengliang，JIANG Shouping， LUO Yu， et al. Comprehensive analysis of the prediction of protein’s secondary structure[J]. Acta PhysicoChimica Sinica， 1990， 6（6）： 686691.
[7]LAWRENCE R，RABINER A.Tutorial on hidden Markov models and selected applications in speech recognition[J]. Proceedings of the IEEE，1989，77（2）： 257286.
[8]STANKE M，WAACK S. Gene prediction with a hidden Markov model and a new intron submodel[J]. Bioinformatics，2003，19（sup2）： 215225.
[9]PEDERSEN S，HEIN J. Gene finding with a hidden Markov model of genome structure and evolution[J]. Bioinformatics，2003，19（2）： 219227.
[10]KABSCH W，SANDER C. Dictionary of secondary structure pattern recognition of hydrogenbonded and geometric features[J]. Biopolymers，1983，22（12）： 25772637.
[11]HEINIG M，FRISHMAN D. STRIDE：Web server for secondary structure assignment from known atomic coordinates of proteins[J]. Nucleic Acids Research，2004，32： 500502.
[12]RICHARDS F，KUNDROT C. Identification of structural motifs from protein coordinate data：Secondary structure and firstlevel supersecondary structure[J]. Proteins，1988，3（2）： 7184.
[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）： 275285.
[15]MOULT J，FIDELIS K，ZEMLA A，et al. Critical assessment of methods of protein structure prediction（CASP）： Round Ⅳ[J]. Proteins，2001，45（sup5）： 27.
[16]JONES D. Protein secondary structure prediction based on positionspecific scoring matrices[J]. Journal of Molecular Biology，1999，292（2）：195202. [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）：303308.
[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）： 4554.
[20]YI T，LANDER E. Protein secondary structure prediction using nearestneighbor methods[J]. Journal of Molecular Biology，1993，232（4）： 11171129.
[21]ROST B，SANDER C. Prediction of protein secondary structure at better than 70% accuracy[J]. Journal of Molecular Biology，1993，232（2）： 584599.
[22]CUFF J，BARTON G. Application of multiple sequence alignment profiles to improve protein secondary structure prediction[J]. Proteins，2000，40（3）：502511.
[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）： 397407.
[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）： 173190.
[26]陈军霞，刘紫玉. 基于BaumWelch算法HMM模型的孤词算法研究[J].河北科技大学学报，2015，36（1）：5257.
CHEN Junxia，LIU Ziyu. Study on solitary word based on HMM model and BaumWelch algorithm[J]. Journal of Hebei University of Science and Technology，2015，36（1）： 5257.
[27]AYDIN Z，ALTUNBASAK Y，BORODOVSKY M. Protein secondary structure prediction for a singlesequence using hidden semiMarkov models[J]. BMC Structural Biology，2006，7： 178192.
蛋白质二级结构与蛋白质三级结构及蛋白质功能密切相关，是生物信息学研究的热点，其中概率图模型隐马尔可夫算法（HMM）是该领域研究的重要工具。但是在实际应用中，存在着HMM训练下溢、不同训练集的效果差异较大及参数优化困难等问题。对预测蛋白质二级结构时HMM遇到的训练下溢问题提出了改进方案；首次提出8状态HMM来预测蛋白质二级结构，并且将参数B改进成为包含状态转移信息的三维参数；为了改进最优HMM模型的确定方法，用每个样本分别对初始HMM模型进行训练，得到一系列新的模型，然后对这些新模型的参数求均值，将求得的均值作为最优模型的参数。这些改进方法提高了HMM预测蛋白质二级结构的准确率，为HMM的进一步优化打下良好的基础。
关键词：应用生物化学；概率图；蛋白质二级结构；HMM；下溢；参数优化
中图分类号：O175.8文献标志码：A
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 8state HMM model to predict protein secondary structure for the first time； and modify parameter to be a threedimensional 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
生物学原理[1]指出：DNA序列首先通过转录、翻译生成氨基酸序列，氨基酸序列再经过盘曲折叠形成复杂的二级、三级等空间结构。研究发现，蛋白质二级和三级结构能有效揭示蛋白质的生物功能[24]，可以用X射线晶体学技术、电子显微镜技术和核磁共振衍射技术（NMR）等来测定它们[5]。这些方法虽然比较直接，但预测时周期长、成本高、技术难度大。人们越来越多地关注生物信息学的应用，即基于经验知识与计算化学、统计物理学、信息学等方法的结合，从理论上预测蛋白质的空间结构[69]，其中二级结构是预测三级结构的基础。蛋白质二级结构的主要形式包括α螺旋、310螺旋、π螺旋、β折叠、β转角和无规则卷曲等。最流行的二级结构预测方法有DSSP[10]，STRIDE[11]， DEFINE[12]等，通常利用DSSP算法将蛋白质二级结构分为8类：H（αhelix），G（310helix），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]，蛋白质二级结构SS8的8种状态等[13，17]，而其预测方法则包括最近邻方法[1820]、人工神经网络（ANN）[16，2122]、支持向量机（SVM）[2324]和隐马尔可夫算法（HMM）[2526]等。
本文研究的蛋白质二级结构预测算法可以同时实现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重交叉检验的平均准确率。
准确率的定义为一条氨基酸序列的每个氨基酸都从属于蛋白质二级结构状态中的一种，在对蛋白质二级结构进行预测时，是对其每个氨基酸的所属状态进行预测。本条序列的预测准确率定义为
准确率=[SX（]本序列中被正确预测结构状态的氨基酸数[]本序列中的氨基酸总数[SX）]×100% ，
而基于某个HMM对一组序列进行蛋白质二级结构预测的准确率定义为对所有序列预测准确率的平均值。
1.2隐马尔可夫算法
HMM是一种概率图算法，在语音识别[7]和生物信息学中[89]有广泛应用。以往的蛋白质二级结构预测常利用3状态或7状态HMM，由于7状态比3状态包含的蛋白质信息较多，所以前者预测精度较高。因此，本文蛋白质二级结构预测在7状态的基础上进行改进，提出8状态HMM，把蛋白质的8种二级结构状态分别作为状态[WTBX]S1，S2，…，S8，包括α螺旋的起始、中间和结束状态HB，H，HE（α螺旋的第1个氨基酸状态为HB，最后一个氨基酸状态为HE，中间部分的氨基酸状态为H），β折叠的起始、中间和结束状态EB，E，EE（氨基酸状态归属情况同α螺旋），无规则卷曲状态C及非二级结构状态F。蛋白质的每个氨基酸都从属于8种状态的一种，随着同一蛋白质上各种二级结构的交替出现，氨基酸的8种状态之间就发生了“转移”（transition），转移概率矩阵记为[WTHX]A8×8。HMM把每个氨基酸看成是在该氨基酸的当前状态之下依照概率矩阵[WTHX]B8×20而“发出”（emit）的，加上初始状态分布[WTBX]π，M=（π，A，B）就被称为HMM模型。一个蛋白质序列的氨基酸是“可见”（observable）的符号，而蛋白质上的二级结构则是“隐含”（hidden）的状态，这就是HMM的由来。 显然，HMM试图用统一的状态转移矩阵和各状态下可见符号的出现概率来描述蛋白质序列中的二级结构与氨基酸序列的依存性，从而用这种依存性来预测陌生蛋白质中二级结构分布。 实际上，还可以建立2个连续状态组合成的8×8=64种状态甚至83=512状态等模型，但是随着[WTHX]矩阵A和矩阵B[WTBZ]的增大，计算量也会空前增大。所以，该文只考虑8状态的HMM模型。
一般来说，利用HMM来预测蛋白质二级结构会涉及到以下3个问题。
问题1求由已知HMM模型生成已知氨基酸序列的概率。
给定蛋白质序列[WTBX]O=O1，O2，…，OT以及训练好的模型M，计算条件概率P（O|M）的值。基于不同的模型M，同一条蛋白质序列的出现概率值可以不同。计算条件概率P（O|M）的算法有前向算法、后向算法及前后向算法[5，13]。
前向算法的步骤如下（其他类似）。
1）初始化：α1（i）=1，1≤i≤N； 2）递归：
αt+1（j）=∑[DD（]N[]i=1[DD）]αt（i）aijbij（Ot），1≤t≤（T-1），1≤j≤N；3）累加：P（O|M）=∑[DD（]N[]i=1[DD）]αT（i）。此评估问题的解决只是简单的迭代，没有运用复杂的算法。这里T是氨基酸序列的长度；N=8是状态数；状态i→j转移概率组成矩阵[WTHX]A[WTBX]=（aij），而这一状态的转移是由第t个位置上氨基酸Ot的输出来实现的，概率是bij（Ot）；αt（i）是一个概率值，表示第t个位置的氨基酸处于第i个状态的概率。如果氨基酸序列较长，则当t大于某一值时，α值会很小，几乎接近0，Matlab程序会默认为0。为了避免这种下溢情况，本文采用文献[5]中的比例因子方法。
问题2已知HMM模型和氨基酸序列，求最佳二级结构状态序列。
给定观察序列[WTBX]O=O1，O2，…，OT以及模型M，用动态规划算法把蛋白质序列分成不同阶段，通过把条件概率每步最大化来找到一个概率最大的状态序列S=S1，S2，…，ST，作为观察序列O的最佳解释。
解决该问题的算法为动态规划的Viterbi算法[5，13]。 [WTBX]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模型。
给定观察序列[WTBX]O=O1，O2，…，OT的集合，需要找到最佳模型M=（π，A，B），使得P（O|M）最大。基于训练集中的420条氨基酸序列，如果要找到一个包含尽可能多的序列与二级结构对应信息的模型，必须把模型M在各个氨基酸序列上反复迭代来收集信息和改进模型。通过启发迭代来训练模型M=（π，A，B）的算法为BaumWelch算法，该算法中用来优化矩阵[WTHX]A和B[WTBX]中元素的迭代重估公式为
显然这个启发式算法是非常费时间的，与上面的简单迭代和流程固定的动态规划不同。当不同氨基酸序列之间信息差异很大时，会在某些情况下出现随着训练次数或训练序列数的增加效果反而下降的情况。本文探讨了如何寻找最佳训练集的问题。 利用HMM进行蛋白质二级结构预测时，先是基于训练集中的420条氨基酸序列选出最优的[WTHX]矩阵A，B；然后针对二级结构的氨基酸序列，用训练出来的模型来“解码”，预测其最佳的二级结构状态序列。
1.3原有蛋白质二级结构预测的HMM模型中存在的问题和本文的改进方案
人们用3状态和7状态HMM对蛋白质二级结构进行预测时[5，13]是基于3种二级结构来定义状态的，未考虑到非二级结构的状态F，本文中加上了非二级结构的状态F。参[WTBX]数B在蛋白质二级结构预测时起着很重要的作用，但其并未包含状态间的转移，本文把B改造成三维参数来包含状态转移的信息。另外，利用BaumWelch算法进行参数重估，当训练样本不含某状态时，该状态转移到其他状态的情况就不存在，则其对应的参数值为不定数，即训练下溢。针对训练下溢的情况，本文的改进方案是当初始模型选定后，训练参数直至下溢，保留这个过程中最佳模型的参数，而不使用添加因子等传统手段。
2结果与讨论
2.1新的8状态HMM算法流程
通过对CB513数据集中的序列进行统计，α螺旋的长度最少为3个氨基酸，为了提供更多的蛋白质结构信息，
将α螺旋的状态H扩展为HB（起始位置）、H（中间位置）和HE（结束位置）。虽然折叠的长度最少是1，但将其状态扩展为EB，E，EE后，预测准确率有所提高，故采取其3状
态的情况。对于无规则卷曲，将其扩展为3状态后，预测准确率并没有明显提高，故采取其单状态的情况。在此基础上增加非二级结构状态F，共计8状态，其HMM结构如图1所示。在利用8状态HMM进行蛋白质二级结构预测时，首先根据其中的每个氨基酸的所属结构将氨基酸序列转化为状态序列，然后通过统计得到状态转移概率矩阵[WTHX]A和8状态下20种氨基酸的“发出”概率矩阵[WTHX]B，这就是“由已知序列和二级结构的训练集得到最佳HMM模型”的算法问题。基于这个HMM模型，针对一条陌生的序列，按着上面介绍的“已知HMM模型和氨基酸序列，求最佳二级结构状态序列”算法流程，就可以预测这条陌生序列的二级结构了。
2.2 参数B定义的改进
在将不同的氨基酸序列预测为其对应的状态序列时，参数[WTBX]B起着很重要的作用，[WTBX]B包含的信息越多，预测准确率就越高，故考虑将二维状态的[WTBX]B改进为三维，使其也蕴含状态间的转移。即当[WTBX]B[WTBX]为二维时，B（i，k）表示状态i输出氨基酸k的概率；当[WTBX]B[WTBX]为三维时，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可知，第1次训练参数的预测效果最好，由于在用BaumWelch算法进行参数训练时，每训练一次，参数中不定数的个数会增加，预测效果反而会变差。因此，由初始参数分别对每个样本训练一次，得到420个HMM模型（当然包含[WTHX]A和B），然后分别用这420个HMM对测试集进行预测，经过统计，其中最好的HMM模型的准确率达到 0.361 84。为了进一步提高预测准确率，在删掉108组准确率为0的HMM后，对剩余的312个HMM的参数矩阵[WTHX]A和B分别求平均值，最后利用这个“平均”HMM对测试集进行预测，准确率提高为0.401 55。总之，分别从每条训练序列开始HMM模型的更新过程，不用“缩放因子”等传统方法进行人为干预，而是让它一直训练直至下溢，选取其中准确率最高的HMM模型存放，每条训练集序列都这样训练到下溢并存储此过程中准确率最高的HMM模型，然后对有效的312个HMM模型中的参数[WTBX]A和B分别进行平均，作为最终的HMM模型的参数。可喜的是，基于这个最终的“平均”模型的预测精度的确提高了。
3结论
文献[5]中3状态的预测精度为0.389 0，7状态的预测精度为0.414 3；文献[13]中3状态的预测精度为0.447 1。在文献[5]中采用的是HGI分类，相比EHL分类较容易预测；而文献[13]为了避免下溢情况，在BaumWelch算法的重估公式中引入拉普拉斯修正项，虽然精度有所提高，但没有从根本上解决下溢问题。本文不使用“缩放因子”等传统手段，通过在参数维数、训练模型等方面的改进来提高预测精度，为应用HMM预测蛋白质二级结构的改进提供了新的思考方向。
本文阐述了HMM预测蛋白质二级结构时遇到的训练下溢问题、非二级结构状态和参数[WTBX]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）： 425440.
[3]WHISSTOCK J，LESK A. Prediction of protein function from protein sequence and structure[J]. Quarterly Reviews of Biophysics，2003，36（3）： 307340.
[4]DOMINGUES F，LENGAUER T. Protein function from sequence and structure data[J]. Applied Bioinformatics，2003，2（1）： 312.
[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）： 686691.
WANG Pengliang，JIANG Shouping， LUO Yu， et al. Comprehensive analysis of the prediction of protein’s secondary structure[J]. Acta PhysicoChimica Sinica， 1990， 6（6）： 686691.
[7]LAWRENCE R，RABINER A.Tutorial on hidden Markov models and selected applications in speech recognition[J]. Proceedings of the IEEE，1989，77（2）： 257286.
[8]STANKE M，WAACK S. Gene prediction with a hidden Markov model and a new intron submodel[J]. Bioinformatics，2003，19（sup2）： 215225.
[9]PEDERSEN S，HEIN J. Gene finding with a hidden Markov model of genome structure and evolution[J]. Bioinformatics，2003，19（2）： 219227.
[10]KABSCH W，SANDER C. Dictionary of secondary structure pattern recognition of hydrogenbonded and geometric features[J]. Biopolymers，1983，22（12）： 25772637.
[11]HEINIG M，FRISHMAN D. STRIDE：Web server for secondary structure assignment from known atomic coordinates of proteins[J]. Nucleic Acids Research，2004，32： 500502.
[12]RICHARDS F，KUNDROT C. Identification of structural motifs from protein coordinate data：Secondary structure and firstlevel supersecondary structure[J]. Proteins，1988，3（2）： 7184.
[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）： 275285.
[15]MOULT J，FIDELIS K，ZEMLA A，et al. Critical assessment of methods of protein structure prediction（CASP）： Round Ⅳ[J]. Proteins，2001，45（sup5）： 27.
[16]JONES D. Protein secondary structure prediction based on positionspecific scoring matrices[J]. Journal of Molecular Biology，1999，292（2）：195202. [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）：303308.
[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）： 4554.
[20]YI T，LANDER E. Protein secondary structure prediction using nearestneighbor methods[J]. Journal of Molecular Biology，1993，232（4）： 11171129.
[21]ROST B，SANDER C. Prediction of protein secondary structure at better than 70% accuracy[J]. Journal of Molecular Biology，1993，232（2）： 584599.
[22]CUFF J，BARTON G. Application of multiple sequence alignment profiles to improve protein secondary structure prediction[J]. Proteins，2000，40（3）：502511.
[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）： 397407.
[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）： 173190.
[26]陈军霞，刘紫玉. 基于BaumWelch算法HMM模型的孤词算法研究[J].河北科技大学学报，2015，36（1）：5257.
CHEN Junxia，LIU Ziyu. Study on solitary word based on HMM model and BaumWelch algorithm[J]. Journal of Hebei University of Science and Technology，2015，36（1）： 5257.
[27]AYDIN Z，ALTUNBASAK Y，BORODOVSKY M. Protein secondary structure prediction for a singlesequence using hidden semiMarkov models[J]. BMC Structural Biology，2006，7： 178192.