基于多特征信息及Ma-Ada多分类器融合的蛋白质结构类预测

郑 斌 厉力华

(杭州电子科技大学生命信息与仪器工程学院，杭州 310018)

引言

人类基因组计划的顺利实施带来了蛋白质数据库中海量的序列信息，面对浩瀚的蛋白质序列数据，传统通过实验方法测定蛋白质结构已经远远不能满足人类的需求。因此，探讨通过理论计算方法来预测蛋白质结构类别显得尤为重要。

蛋白质功能的确定有助于阐明生命体在生理或病理条件下的变化机制，并且对于疾病预防和药物开发等方面都有十分重要的推动作用。科学研究表明，蛋白质的结构和功能是相统一的，因此要研究蛋白质的功能就需要深入了解其结构。英国学者Levitt根据蛋白质序列中二级结构片段的排列和其拓扑结构的不同，将蛋白质分为全α、全β、α/β和α+β四种结构类型［1］，目前已报道的对蛋白质结构类的研究主要集中在这四种类型上。蛋白质序列特征表示和机器学习算法是影响蛋白质结构类预测效果好坏的两个重要方面。对于第一个方面，我们的工作就是用数字参量把从氨基酸序列中提取到的信息用特征参数合理地描述出来，最大程度地挖掘氨基酸序列之间的关系。这方面众多学者已经做了大量的研究工作。比如Nakashima等用20维的特征信息表示20种氨基酸在蛋白质序列中出现的频率［2］;Zhang等将自相关函数应用于蛋白质结构类型预测研究中，其主要是描述一种基于氨基酸指数的特征提取方法［3］;Chou在2001年首次提出了伪氨基酸组成方法，它是(20+λ)维的特征信息［4］。但是上述工作仅基于单一性质的特征信息进行蛋白质结构类预测研究，从而导致提取的特征信息所包含的信息量非常有限，不能全面描述蛋白质序列特征。

对于第二个方面，机器学习算法的基本过程就是通过对样本数据训练总结出一整套判别体系及参数后，进而对测试样本数据进行预测。Chris等运用的 ANN 算法［5］，Liu 等运用的 KNN 算法［6］，Wu等运用的SVM算法［7］，都取得了较好的结果。但是传统的单分类器算法存在着一定的缺陷，因为没有任何一个分类器算法能够在所有的样本特征上进行很好的区分。为了解决这一问题，研究者们提出了一种新的分类技术——多分类器融合算法。多分类器融合算法是指先利用多个分类器进行分类，然后通过一定的组合机制把多个分量分类器的结果进行融合，达到对目标进行识别的目的。近年来，越来越多的研究者开始把多分类器融合算法应用于蛋白质结构类预测领域，比如Cai等和Feng等分别把LogitBoost算法和Boosting算法应用于蛋白质结构类预测［8－9］，都取得了比单分类器更加理想的效果。但这些多分类器融合算法没有考虑各个单分类器关于样本的具体情况，即置信度，对样本数据信息挖掘不充分，丢失了很多有用的信息，导致分类效果还是达不到令人满意的程度。

在本课题组前期研究中，提出了k-字统计频率和 k－片段位置分布两种特征提取方法［7，10］，但其特征信息融合的效果还有待提高。为了进一步提高蛋白质结构类的预测精度，本研究将这两种特征提取方法得到的氨基酸序列信息和物理化学性质信息同蛋白质二级结构信息进行融合，并尝试在Adaboost.M1 算法［11］中引入 Multi－Agent(MA)多智能体融合的思想［12－13］，提出了一种 Ma－Ada 多分类器融合算法，该算法可以挖掘单分类器度量层信息以及各个单分类器之间的交互融合信息，以进一步改进预测的准确性。

1 方法与数据

1.1 蛋白质结构类特征提取及融合

1.1.1 k-字统计频率特征

k-字统计频率特征提取方法主要是统计长度为k的氨基酸片段频率信息。其具体方法是，对于任一条长度为 L 的氨基酸序列 S=R1，R2，R3，…，RL，通过移动长度为k的滑动窗口来统计k-字氨基酸片段在给定氨基酸序列中出现的频率。与传统统计氨基酸序列频率特征的方法相比，此方法可以通过变化的k-字获得更为全面的氨基酸序列频率信息。

1.1.2 k-片段位置分布特征

k-片段位置分布特征提取方法主要是统计氨基酸序列的位置分布信息。其具体方法是，给定任一条长度为 L 的氨基酸序列 S=R1，R2，R3，…，RL，将其看作是首尾相连，用O(y)对各氨基酸片段出现的位置分别进行标记。其中，y表示某一氨基酸片段。用变量ξ表示某一特定氨基酸片段y的位置间隔差，然后对变量ξ进行统计可以得到概率P(y)(ξ)，进而可以得出其均值E(y)(ξ)以及方差D(y)(ξ)。最后由统计学概念计算出变异系数的倒数C(y)(ξ)变量的值来表征氨基酸序列位置分布信息。

式中，C(y)(ξ)较好地反映了氨基酸片段位置分布信息，其值越大表示变量分布较为密集，反之则表示变量分布较为分散。

1.1.3 多特征信息融合

早期研究中仅基于单一性质的特征信息进行蛋白质结构类预测研究，如果将不同特征提取方法得到的多种特征信息加以联系和有机的融合，将为分类预测提供更多的信息量。在本课题组的前期研究中，当取k=1时，能降低特征信息维数和减少特征信息冗余，从而能够获得更高的分类率［10］。利用1－字统计频率分布和1－片段位置分布两种特征提取方法，在包含20种氨基酸的蛋白质一级序列上分别提取20维氨基酸频率分布信息和20维氨基酸序列位置分布信息，分别记为AAC和AAP。

氨基酸自身及之间的物理化学特性决定了蛋白质的折叠构象以及最终的结构。在本研究中，根据氨基酸的物理化学性质，把20种氨基酸分为疏水类I、亲水类E以及中性类A等3类。

通过式(2)，可以把蛋白质一级序列整合成只包含三种氨基酸组成的序列，然后利用1－字统计频率分布和1－片段位置分布两种特征提取方法，分别提取3维氨基酸频率分布信息和3维氨基酸序列位置分布信息，分别记为IEAC和IEAP。考虑到蛋白质结构类与蛋白质二级结构序列的组分及其空间排列息息相关，因此，采用Liu等设计的11维二级结构特征信息［14］，记为SSI。通过融合以上不同性质的特征信息，组成17维和57维的特征信息集。其组成如表1所示。

表1 特征信息集的组成Tab.1 The composition of the feature information set

1.2 Ma-Ada多分类器融合

1.2.1 融合算法原理

在多分类器融合领域，Adaboost.M1是一种比较成功的多分类器集成学习算法，已经广泛应用于人脸检测和文本分类等领域［15－16］。它的核心思想是通过对训练样本集重复采样，训练出多个具有差异性的弱分类器集，然后将多个弱分类器集成得到一个强分类器，最后采用投票规则输出最终的分类结果。不过，该算法只是简单地把属于每一类的弱分类器权重求和，再把样本归于和值最大的那一类。这样处理的后果就是丢掉了很多弱分类器输出的有用信息，比如弱分类器对样本的输出类别以及样本属于每个类别的后验概率。

成员分类器之间的差异性是多数融合算法要求的前提，它对融合系统的性能有着重要影响。Ma－Ada多分类器融合算法的主要思想是首先通过Adaboost.M1算法，对训练集样本进行训练获得一系列具有差异性的单分类器，然后使用这一系列具有差异性的单分类器对训练集样本进行测试，得到训练样本的分类信息。

借鉴Multi－Agent(MA)多智能体的融合思想，把统计得到的分类信息引入决策共现矩阵。其定义如下:

式中，k代表样本类别数，n代表单分类器个数。其元素 djk1，jk2，i，k1，k2定义为

式中，A1表示训练样本集中属于第i类的样本被单分类器k1分为jk1类的个数;A2表示训练样本集中属于第i类的样本被单分类器k2分为jk2类的个数;A3表示训练样本中属于第i类的样本被单分类器k1分为jk1类，并且被单分类器k2分为jk2类的个数。

当有待测样本需要进行分类时，就可以通过已经训练好的一系列单分类器，获得待测样本在每个单分类器上属于每一类别的后验概率信息，即可信度矩阵。其定义如下:

式中，K代表样本类别数，n代表单分类器个数。可信度矩阵B的行值为1，元素bij表示单分类器i认为样本x属于类别j的后验概率值。

最后把可信度矩阵作为初始状态输入溯源矩阵，通过引入决策共现矩阵以及权重矩阵，在溯源矩阵中使各个单分类器之间进行信息交互，从而改变各个单分类器向不同类别溯源的概率，最终得到群体决策，也就是得到相应的多分类器融合结果。与其它多分类器融合算法相比，Ma－Ada多分类器融合算法是一个集成系统，它把各个弱分类器信息集成在一起，从而使信息量更加丰富。并且，它通过定义单分类器的个体行为和个体之间的交互协商，实现了多个个体所组成的群体行为，最大程度实现各自的目标［17］，有效提高了解决问题的能力。Ma－Ada算法工作流程图如图1所示。

图1 Ma-Ada多分类器融合算法流程图Fig.1 Flow chart of the Ma-Ada multi-classifier fusion algorithm

1.2.2 融合算法实现

假定进行融合的训练集上包含N个样本，样本的类别数为K，Ma－Ada融合算法实现步骤如下:

步骤1 初始化训练集上样本权重分布为D1(i)=1/N。

步骤2 用单分类器学习算法迭代运算n次，每次迭代运算后都按照分类结果更新训练集数据权重分布，对于分类失败的个体赋予较大的权重，下一次迭代运算时更加关注这些训练个体。单分类器学习算法通过反复迭代得到n个单分类器集，分类结果越好的单分类器，其对应的权重也越大。

步骤3 经过步骤2可以统计得到权重矩阵W以及各个单分类器对训练集样本分类所产生的类标号信息，然后根据式(5)计算得到决策共现矩阵D。

步骤4 对于一个待分类样本x，经过已经训练完成的n个单分类器决策判断，会得到属于每个单分类器关于各个类别的后验概率值，即可信度矩阵B。通过引入权重矩阵W体现不同单分类器分类性能的差异性。用WB初始化溯源矩阵 S=［ski］n×K。

步骤5 定义溯源矩阵S中元素最大值为V，表示各个单分类器对待测样本的决策置信度，L表示决策阈值。若V＞L，表示各个单分类器基本上达成共识，则进行步骤7。否则调用(9)式调整溯源矩阵S中各个元素的值。步骤6 将更新的溯源矩阵S每一行归一化，保证每行和为1，转步骤5，重新计算V值。

步骤7 各个单分类器最终达成一致意见，即可输出最终的分类决策结果。

1.3 实验数据

SCOP(structure classification of protein)数据库是目前国际上包含蛋白质比较全面和分类比较客观的蛋白质结构数据库之一，也是蛋白质结构类预测研究中基本的数据来源。为了保证在比较衡量时的科学性及公平公正性，本研究采用的数据集都是基于研究者们在已有成果中构建和广泛采用的4个标准数据集。由Zhou构建的Z277和Z498两个数据集分别包括277条和498条氨基酸序列，1189和D640数据集分别包括1092条和640条氨基酸序列。数据集中详细的数据构成参见表2。

表2 4个数据集的构成Tab.2 The composition of four datasets

1.4 分类器选择

支持向量机(SVM)是近年来发展起来建立在统计学习VC维理论和结构风险最小原理基础上的学习算法［21］，具有比其他分类算法收敛速度快、准确性高等优点，在生物信息学中已经得到了广泛的应用［22－23］。所以，选用以径向基函数(RBF)为核函数的SVM算法作为Ma－Ada单分类器学习算法。由于蛋白质结构类预测是四分类问题，而传统的SVM算法只适用于两分类问题，在本研究中采用一对一组合策略(one－against－one)来解决四分类问题。

2 结果

2.1 实验结果

经过前期实验表明，把Ma－Ada融合算法中参数λ和决策阈值L值分别设为1/3和0.95，可以取得较好的分类效果。

2.1.1 方法性能评价

在蛋白质结构类预测研究中，Z277、Z498、1189和D640等4个数据集被多种方法用来验证效果，具有很高的可信度。为了保证结果的可比性，本文和其他研究方法一样，采用蛋白质分类研究中被认为最合理、应用最为广泛的Jackknife交叉验证策略。其具体构造方法是假设样本数据集有N个样本，依次将每个样本单独作为测试集，其余的N－1个样本作为训练集，所以Jackknife交叉验证策略会得到N个模型，用这N个模型最终测试集的分类率的平均数作为分类器的性能指标。选用以上四个数据集的57维特征信息集进行本次试验，分类结果见表3。

表3 不同方法的分类率—Jackknife交叉验证Tab.3 Classification accuracies for different methods based on Jackknife cross-validation

从表3中可以看出，在使用相同的数据集和Jackknife交叉验证策略的前提下，本方法在Z277、Z498、1189和D640等4个数据集上的分类率分别达到了91.3%、96.8%、85.3%和87.2%，比表中其他方法的最好值分别高出3.9%、1.4%、0.1%和0.2%，可以说明本方法对提高这4个数据集的分类率是富有成效的。

2.1.2 分类融合算法评价

本次试验中，在各种分类算法都使用相同的特征信息集的情况下，探讨Ma－Ada多分类器融合算法与支持向量机(SVM)、最近邻(KNN)、决策树(DT)、朴素贝叶斯(NB)、人工神经网络(BP)五种分类算法的优缺点。由于Jackknife交叉验证策略需要建立的分类模型数量和总样本数量相等，当总样本数量相当多时，会导致计算成本偏高，故本次试验采用十折交叉验证策略。其具体构造方法是将数据集均分为10份，然后依次将每份样本数据分别做一次测试集，其余的9份样本数据作为训练集，这样会得到10个模型，用这10个模型最终测试集的分类率的平均数作为十折交叉验证下分类器的性能指标。Z277、Z498、1189和D640等4个数据集的实验结果见表4。

表4 不同方法的分类率(%)—十折交叉验证Tab.4 Classification accuracies(%)for different methods based on 10－fold cross-validation

在表4的Z277、Z498、1189和D640这4个数据集中，通过纵向比较可以看出，，在17维特征信息集的情况下，Ma－Ada算法的预测结果分别为90.6%、95.8%、84.8%和88.3%，优于表中其他分类算法最好结果的2.2%、0.8%、1.2%和1.4%。在57维特征信息集的情况下，Ma－Ada算法的预测结果分别为92.1%、97.0%、83.9%和87.8%，比其他分类算法的最好值分别高出1.8%、1.0%、1.8%和0.9%。

2.1.3 分类稳定性评价

稳定性是衡量分类器性能的一个重要指标。本次试验中，使用17维和57维这两个特征信息集，在 Z277、Z498、1189、D640 等 4 个样本数据集上采用十折交叉验证策略，对100次不同的数据组合的分类精度计算标准差来表示分类结果的稳定性，如果其值越大，代表这100次结果的数据波动越大，说明分类算法的稳定性越差。结果如表5所示。

表5 不同方法的稳定性(%)Tab.5 The stability of different methods

从表5可以看出，Ma－Ada多分类器融合算法在Z277和Z498这两个数据集上稳定性最好，在17维特征信息集上标准差分别为0.49%和0.33%，在57维特征信息集上标准差分别为0.54%和0.22%。

3 讨论

表3中分类率提高的原因可以从以下两个方面来进行解释。其一，本方法组合了不同类型的特征信息，并将其融合为57维特征信息集。提取的这些特征信息较有代表性，覆盖范围广，既考虑了蛋白质序列中氨基酸频率及位置特征，又考虑了氨基酸疏水性属性这一物理化学特征，还考虑了蛋白质二级结构序列特征信息，从而有效地反映了蛋白质序列短、中、长程之间的关系。其二，本方法使用Ma－Ada多分类器融合算法，从而能比其它的分类算法表现出更好的性能。而且，Ma－Ada多分类器融合算法在分类决策时，引入了多智能体思想。通过决策共现矩阵，利用单分类器之间的决策相关信息，在各个单分类器之间进行信息交流，指导各个单分类器向不同类别溯源，通过各个单分类器之间的信息交互改变溯源概率，最终得到群体决策。

通过表4中的数据可以看出，Ma－Ada多分类器融合算法的性能超过了表4中多数的分类算法，因此有望成为蛋白质结构类的预测工具。从蛋白质结构类每类的预测结果上看，基本上每种分类算法在类α和类β这两类的分类效果最好，在类α+β的分类率最低，这说明在这4种结构类别中，类α+β比其他结构类更难预测。这是由于类α+β在蛋白质结构类定义中，具有比其他三种结构类更复杂的形式，是α－螺旋和β－折叠相隔分布的形式，这也说明蛋白质序列越复杂，预测难度越大，从而造成预测的分类率偏低。

通过横向比较，在Z277和Z498两个数据集上，同一种分类算法在57维特征信息集的分类效果要优于17维特征信息集。但在1189和D640两个数据集上，结果恰好相反。主要原因是当特征维数增加到某一临界点后，继续增加的特征维数不仅会造成维数灾难，而且过高的特征维数会使噪声对分类器的负面影响更加明显，影响分类性能。

在表5中可以看出，与其它方法相比，本研究提出的方法整体上呈现较好的稳定性。这主要是因为Ma－Ada多分类器融合算法采用了多分类器之间的信息融合交互机制，在决策的过程中将各个分类器的相关性引入进来，扩大了信息源，从而能够获得稳定性较好的分类结果。在其他五个分类器中，BP分类器稳定性最差，这主要是由于每次初始化BP网络时都是随机的，而且训练终止时的误差也不完全相同，导致网络训练完成后的权植和阈值也不相同，从而造成分类结果的稳定性较差。

4 结论

探讨理论计算方法预测蛋白质结构类是后基因组时代生物信息学的核心课题之一。本研究将k-字统计频率和k-片段位置分布两种特征提取方法得到的氨基酸序列信息和物理化学信息，与蛋白质二级结构信息进行融合，得到有效的融合特征信息集，并提出了Ma－Ada多分类器融合算法，用于蛋白质结构类分类预测研究。在 Z277、Z498、1189和D640等4个数据集上的实验结果表明，所提出的57维融合特征信息集和Ma－Ada多分类器融合算法的分类率优于大部分已发表的实验结果。而在相同的融合特征信息集上，Ma－Ada多分类器融合算法更能有效地提高蛋白质结构类的预测精度。因此，本方法是蛋白质结构类预测研究的一次有意义尝试，对提高蛋白质结构类的预测精度具有一定的研究参考价值。

［1］Levitt M，Chothia C.Structural patterns in globular proteins［J］.Nature，1976，261(5561):552－558.

［2］Nakashima H，Nishikawa K.Discrimination of intracellular and extracellular proteins using amino acid composition and residuepair frequencies［J］.Journal of Molecular Biology，1994，238(1):54－61.

［3］Bu Weishu，Feng Zhiping，Zhang Ziding，et al.Prediction of protein(domain)structural classes based on amino－acid index［J］.European Journal of Biochemistry，1999，266(3):1043 －1049.

［4］Chou Kuochen.Prediction of protein cellular attributes using pseudo－amino acid composition ［J］. Proteins:Structure，Function，and Bioinformatics，2001，43(3):246 －255.

［5］Ding CHQ，Dubchak I.Multi－class protein fold recognition using support vector machines and neural networks ［J］.Bioinformatics，2001，17(4):349－358.

［6］Liu Taigang，Zheng Xiaoqi，Wang Jun.Prediction of protein structural class using a complexity－based distance measure［J］.Amino Acids，2010，38(3):721－728.

［7］Wu Li，Dai Qi，Han Bin，et al.Prediction of protein structural class using a combined representation ofprotein－squence information and support vector machine［C］//Bioinformatics and Biomedicine Workshops(BIBMW).HongKong:IEEE，2010:101－106.

［8］Cai YD，Feng KY，Lu WC，et al.Using logitboost classifier to predict protein structural classes［J］.Journal of Theoretical Biology［J］.2006，238(1):172 －176.

［9］Feng KY，Cai YD，Chou KC.Boosting classifier for predicting protein domain structural class［J］.Biochemical and Biophysical Research Communications，2005，334(1):213－217.

［10］Dai Qi，Wu Li，Li Lihua.Improving protein structural class prediction using novelcombined sequenceinformation and predicted secondary structural features［J］. Journal of Computational Chemistry，2011，32(16):3393 －3398.

［11］Freund Y，Schapire RE.Experiment with a new boosting algorithm ［C］//Machine Learning－InternationalWorkshop.Morgan:Kaufmann Publishers，1996:148－156.

［12］彭芳青，厉力华，徐伟栋，等.基于Multi－Agent的乳腺钼靶图像肿块分类方法［J］.传感技术学报，2010，23(2):153－157.

［13］赵浣萍，徐伟栋，厉力华，等.一种基于改进型Multi－Agent多分类器融合的乳腺钼靶肿块分类算法［J］.仪器仪表学报，2011，32(9):2034－2040.

［14］Liu Tian，Jia Cangzhi.A high－accuracy protein structural class prediction algorithm using predicted secondary structural information［J］.Journal of Theoretical Biology，2010，267(3):272－275.

［15］武勃，黄畅，艾海舟，等.基于连续Adaboost算法的多视角人脸检测［J］.计算机研究与发展，2005，42(9):1612－1621.

［16］江林升，朱学芳.一种基于新特征的车牌检测方法［J］.计算机工程与应用，2011，47(20):188－190.

［17］寇忠宝，张长水.基于Multi－Agent的分类器融合［J］.计算机学报，2003，26(2):174－179.

［18］Kurgan LA，Homaeian L.Prediction of structural classes for protein sequences and domains—Impact of prediction algorithms，sequence representation and homology，and test procedures on accuracy［J］.Pattern Recognition，2006，39(12):2323 －2343.

［19］Chen Ke，Kurgan LA，Ruan Jishou.Prediction of protein structuralclass using novel evolutionary collocation－based sequence representation［J］.Journal of computional chemistry，2008，29(10):1596－1604.

［20］Zhou Guoping.An intriguing controversy over protein structural class prediction［J］.Journal of Protein Chemistry，1998，17(8):729－738.

［21］Vapnik VN.An overview of statistical learning theory［J］.IEEE Transactions on Neural Networks，1999，10(5):988－999.

［12］Sun XD，Huang RB.Prediction of protein structural classes using support vector machines［J］.Amino Acids，2006，30(4):469－475.

［23］Cai YD，Liu XJ，Xu X，et al.Support vector machines for predicting protein structural class［J］.BMC Bioinformatics，2001，2(1):1－5.

［24］Cao Youfang，Liu Shi，Zhang Lida，et al.Prediction of protein structural class with rough sets［J］.BMC bioinformatics.BMC Bioinformatics，2006，7(1):7－20.

［25］Yang Jianyi，Peng Zhenling，Chen Xin.Prediction of protein structural classes for low－homology sequences based on predicted secondary structure［J］.BMC Bioinformatics，2010，11(Suppl 1):S9.