预测矩阵范文

预测矩阵范文（精选3篇）

预测矩阵 第1篇

1 协同过滤推荐

协同过滤这一概念于1992 年由Goldberg、Nicols、Oki及Terry首次提出[1]。推荐系统发展至今, 协同过滤已经成为最流行和最成熟的技术。它的基本思想是:利用已有用户群过去的行为或意见预测当前用户最可能喜欢哪些东西或对哪些东西感兴趣[2]。

2 实验数据集和评测标准

文章所采用的是Movie Lens网站所提供的1M数据集, 简称为ML 1M。Movie Lens是一个历史悠久的推荐系统, 由美国Minnesota大学计算机科学与工程学院的Group Lens项目组创办, 是一个非商业性质的、以研究为目的的实验性站点。Movie Lens主要使用Col-laborative Filtering和Association Rules相结合的技术, 向用户推荐他们感兴趣的电影。文章采用评测方法中的均方根误差 (RMSE) 作为评测标准, 用于评价算法的预测性能。

3 基于NMF协同过滤推荐算法分析

文章通过实验实现了基于非负矩阵分解的协同过滤推荐算法, 在该算法中需要将原始用户评分矩阵分解为用户集合的矩阵和电影集合的矩阵, 通过计算它们特征向量的点积预测评分。分解原始用户评分矩阵采用的是梯度下降法通过迭代逐渐减小预测评分和真实矩阵的误差直至收敛而得到。在本实验中梯度下降常数设为0.0002。采用均方根误差RMSE计算误差, 即循环地计算每一条目的误差, 最后将其结果相加。

为了选取合适的非负矩阵分解算法的参数n的值, 需要通过实验观察不同的迭代次数对RMSE的影响。最后通过实验得出n>=100 时, RMSE的值趋于平缓, 达到最小为1.131, 也就是n的值对于RMSE值的变化不再敏感, 所以选择n=100。通过实验可以看出虽然NMF使矩阵的维度得到了有效的降低, 但是在算法执行过程中收敛速度很慢, 需要200 次的迭代才能得出比较满意的结果, 时间代价太大, 在Movie Lens 1M数据集上需要2730.2S才能实现最后评分预测。

4 基于SVD协同过滤推荐算法分析

文章所采用的是2006 年Simon Funk提出了一个新的SVD分解算法, 称为Funk-SVD, 在该算法中有几个非常重要的参数, 如学习速率、特征矩阵维度k及user特征矩阵和item特征矩阵的初值。本实验中选取k为100。User特征矩阵和item特征矩阵是通过原矩阵分解得到的, 而此分解是一个NP问题, 也就是得不到全局最优解, 只能从两个矩阵的初值开始, 沿着梯度方向向下走, 得到局部最优解, 所以user特征矩阵和item特征矩阵初值的确定关系到局部最优解的效果, 在本实验中定义其初值为0.1*rand (0, 1) /sqrt (k) 。随着迭代次数的增加, RMSE的值也在不断变化, 当迭代次数为100时, RMSE达到最小值0.871069。虽然定义迭代次数为100, 实际上只进行了48 次。

基于奇异值分解的协同过滤推荐算法, 在每次迭代后RMSE的值都减小了, 说明模型的性能也得到了很大提高, 在第一次迭代后, RMSE的值从0.947080 下降到0.935648, 性能提高了1%;经过十次迭代后, RMSE的值下降到0.914292, 性能提高了3%;经过四十八次迭代后, RMSE的值下降到0.871069, 性能提高了7%。但是在实验过程中, RMSE值的下降速度越来越缓慢, 需要很多的迭代次数和执行时间。

5基于非负矩阵分解与奇异值分解混合推荐算法分析

通过对两种算法原理的论述, 两种算法各有其优点, 为了更好地提高预测的准确度, 解决矩阵的稀疏性问题, 文章提出了基于非负矩阵分解与奇异值分解混合推荐算法。非负矩阵分解算法通过迭代可以得到用户矩阵和物品矩阵, 通过它们特征向量的乘积可以得到初步的用户与测评分矩阵, 使得原始的稀疏矩阵变得更加稠密, 但是其预测准确度并不高。所以将非负矩阵分解得到的用户特征矩阵作为K-均值聚类算法的输入, 将用户集分成不同的簇, 每个簇内的用户都具有较高的相似性, 由于SVD算法具有较高的预测准确度, 所以对每个簇内的用户数据进行SVD分解, 最后得到新的用户评分矩阵。本算法实际上是对上述两种算法的结合, 所以在实验过程中需要考虑非负矩阵分解算法中的迭代次数n, 设定迭代次数n为100, 梯度下降常数为0.002。奇异值分解时学习速率=学习速率*0.9、特征矩阵维度k=100及user特征矩阵和item特征矩阵的初值为0.1*rand (0, 1) /sqrt (k) 。在算法中需要通过K-均值聚类算法对用户集进行分类, 通过实验得出聚类的个数等于60时RMSE的值最小, 也就是可以达到最好的准确度, 所以在此改进算法中设定K值为60。

如图1所示, 从以上三个算法的对比试验可以得出, 基于SVD协同过滤算法在时间性能上较基于NMF协同过滤算法具有较大的优势, 但是准确性一般;基于NMF协同过滤算法预测准确度最差, 而且时间消耗很大。而基于非负矩阵分解与奇异值分解混合过滤算法相对上述两种方法有了很大的提升, 在时间上优于NMF算法与SVD算法, 准确性要高于前两种算法。

参考文献

[1]David Goldberg, David Nichols, Brian M.Oki and Douglas Terry.Using collaborative filtering to weave an information tapestry.Communications of the ACM[J].1992, 35 (12) :61-70.

预测矩阵 第2篇

关键词：人口增长,灰色系统,Leslie矩阵

0 引言

目前国内学者对于人口预测方法进行了深入的研究[1,2,3,4,5,6,7,8]。已有文献所用的预测方法主要可以分为以下几类: 神经网络[1,2]、时间序列分析法[3,4,5]、灰色预测[6,7,8]。其中灰色预测模型是一种比较成熟的方法,但是灰色预测模型也存在一些不足: 它只适用于呈近似指数增长规律的数据序列,而且求解参数的算法也有一些缺陷。而Leslie矩阵构建的人口动力学方程,利用某一初始时刻人口的年龄结构现转,可以动态地预测人口年龄结构及数量随时间的演变过程。

本文采用基于Leslie矩阵模型与灰色系统理论的合成模型,即改进的Leslie矩阵灰色预测模型来确定人口增长预测。该方法能从人口增长的影响因素出发,突出了灰色系统在影响人口不确定因素的预测能力,且结合Leslie矩阵人口预测模型全面地考虑到影响人口总量与结构的各种主要因素,因而更加提高了人口预测的可信度和精确度。

1 人口增长影响因素分析

由人口平衡方程可知,影响人口变化不外乎出生、死亡和迁移三大因素[9]。为了综合考虑人口增长影响因素对人口增长的作用论,以及客观上受经验数据的全面性制约,没有也不可能包含影响人口增长的全部变量。如果所缺失的变量在估计的时间范围内基本保持不变,则可以将其影响归入到不确定性因素中,其中,不确定性因素主要包括经济因素,文化因素和医疗卫生因素等。

1. 1 出生率

出生率指在一定时期内( 通常指一年) 平均每千人所出生的人数的比率。生育和出生是两个不同但又密切关联的概念,二者所指的对象完全不同,可是生育和出生又有着密切的练习。通常情况下,一个育龄妇女一次怀孕只能生育一个孩子( 多胞胎除外) ,而且一个婴儿也仅有一个有血缘关系的母亲,因此二者存在“一对一”的对应关系。出生率一般用千分率进行计量。计算公式为:

出生率= ( 年出生人数/年平均人数) × 1000‰

其中,出生人数指活产婴儿,即胎儿脱离母体时,有过呼吸或有其他生命现象。

1. 2 婴儿死亡率

婴儿死亡率是指死亡率婴儿出生后不满周岁死亡人数同出生人数的比率。影响婴儿死亡率的因素有很多。从宏观上看,可能的影响因素包括经济发展水平、医疗水平和社会保障水平等; 从中观上看,家庭的收入、父母的文化水平和身体状况以及婴儿的照料等都会影响婴儿死亡率; 从微观上看,婴儿死亡的可能性还受到婴儿有无先天性疾病等因素的影响。与婴儿死亡相关的因素分析使用了婴儿死亡概率而不是婴儿死亡率,另外考虑到城市与农村在经济和卫生等方面的指标含义和分组方法上有所不同,所以与婴儿死亡相关的因素分析均纳入数据。计算公式为:

婴儿死亡率= ( 本年出生本年死亡人数/本年出生人数) × 1000‰

1. 3 人口死亡率

人口死亡率是某一地区一段时间内的死亡人数与该时期平均总人数之比率,反映社会经济发展水平和居民健康状况的重要指标。随着社会经济的发展和医疗卫生水平的提高,人口死亡率不断下降,人口寿命逐步延长。人口寿命的延长给老年保障体系带来财务压力,世界各国纷纷采取提高退休年龄的办法,缓解寿命延长和人口老化带来的养老金支付压力。计算公式为:

人口死亡率= ( 死亡人口/总人口数) × 1000‰

1. 4 不确定性因素

人口的增长离不开医疗水平的提高、经济水平的发展和地区差异等因素,则在本研究中,一切不确定性因素也纳入模型考虑。经济因素对人口自然增长的作用主要表现在它决定了人口的增殖条件和生存条件,通过改变人口的出生率和死亡率来影响人口的自然增率。更多地影响着人口的自然增长。随着科学文学水平的提高,人口自然增长率趋于下降,现代社会里这一趋势尤为明显,人口增长的经济效应主要通过人作为生产者和消费者的统一而体现出来。其中,地区差异包含少数民族地域差异带来的生育政策的不同。因此,不确定性因素对人口预测具有不可缺少的影响。

2 改进的Leslie矩阵灰色预测模型

2. 1 灰色GM( 1,1) 模型基本原理

灰色系统理论将所有的系统划分为白色、黑色和灰色系统[10]。所谓“白”就是指所有信息已知;“黑”就是指所有信息未知; “灰”就是指部分信息已知部分信息未知。人口预测模型就是典型的灰色系统,对其影响的地区经济、生态环境、政策影响等情况是已知的,但是其他一些影响因素,例如自然灾害、心理影响等是难以确切知道的。灰色理论的特点在于其对灰色、灰过程的处理上: 用“生成”的方法对原始数据进行处理,得到随机性弱化、规律性增强的新数列进行建模。灰色预测模型的特点在于所需负荷数据少、不需要计算统计特征值、建模精度高。因此在各种预测领域特别是不确定性明显和数据较少的领域中得到较多的应用。

在人口预测模型中,由于医疗水平的不断改善和人民生活水平的不断提高,各年龄组人口的死亡率不断降低,要实现对人口增长的有效控制,只能降低人口出生率,在引进控制变量时,可由灰色GM( 1,1) 理论引进控制变量序列Ii( t) ,则模型的首要在于一次累加生成,记为Ii( 0) → Ii( 1) ,即:

其中,,然后构造向量 x与矩阵 A:

运用最小二乘法求解系数a,u 。

则GM( 1,1) 模型进行灰色预测如下:

其中,I0( k) 为预测值,a为变化系数,u为灰作用变化量。

2. 2 Leslie矩阵模型基本原理

人口的变化除了受到出生率、死亡率变动的影响之外,还受到其他诸多因素的影响[11]。对一个国家人口发展的趋势的分析需要考虑到现在与今后各类人口数量,性别和年龄结构特征等诸多因素的共同影响,这使得分析人口变化特征的有效性存在明显缺陷。利用Leslie矩阵人口预测模型可分析不同年份各年龄段人口总量的变换,从而预测我国未来的人口总量以及各类人口所占比重。

由于人口的性别通常有一定的比例,时间以年为单位,年龄按周岁计算,设最大年龄为n岁,yi( t) 为t年i岁( 满i周岁而不到i + 1 周岁) 的人口综述,i =0,1,…,n . t = 2005,…,2014 . 只考虑由于生育、老化和死亡引起的人口数量变化,而不计其他社会因素的影响,记bi( t) 为t年i岁人口死亡率,则有:

其中,i = 0,1,…,n - 1 ,t = 2005,…,2014。

另记ci( t) 为t年i岁人口的出生率,di( t) 为t年婴儿死亡率,则:

则人口变化预测模型为:

2. 3 改进Leslie矩阵灰色预测模型

在人口预测模型中,随着医疗水平和人民的生活水平不断提高的条件,各年龄组人口的死亡率在不断的降低。要实现对人口增长的科学预测,需要考虑到不可测的影响因素。可以利用灰色GM( 1,1) 作为不可测因素的灰色估计,再结合Leslie矩阵预测模型,进而改善对人口增长做出科学的预测模型。由灰色GM( 1,1) 引进的控制变量Ii( t) ,使得:

其中,,α( t) 是控制人口数量的主要参数,称为综合生育率,其表示t年生育婴儿数。

在现实环境下,可得bi( t) 、Ii( t) 、di( t) 、c( t) 与时间t无关,则bi( t) = bi,Ii( t) = Ii,di( t) = di,c( t) = c,即改进的Leslie矩阵的人口灰色预测模型可写为:

3 南京市人口预测实证分析

由南京市统计年鉴中2005 年至2014 年的相关数据,画出散点图,发现2005 - 2014 各年生育率、婴儿死亡率及死亡率曲线相似,即出生率、婴儿死亡率与死亡率不随以年为单位的时间变化而改变。综合考虑以上三者定量性因素,选取生育率和人口死亡率随年龄变化取值,婴儿死亡率随月份变化取值。以2005 年数据作为拟合函数的基础,拟合如图1所示。

南京市适龄妇女生育年龄主要集中在20 岁~30 岁,占生育总人口的64. 12% ; 婴儿死亡率随月份的增加而逐渐降低,平均死亡率为13. 4‰; 而人口死亡率随年龄的增加而逐渐升高,其中死亡年龄集中在75 岁以上。生育率、婴儿死亡率和人口死亡率的显著性变化对人口增长的变化是显著的。因此,将生育率、婴儿死亡率和人口死亡率纳入人口预测模型是非常必要的。

本研究利用MATLAB软件,以南京市1949 -2004 年的历史人口规模数量值作为原始数据,对其进行Leslie矩阵预测模型、灰色预测模型和Leslie矩阵灰色预测模型三种不同的数值模拟。利用中心差分的方法对公式( 1) 进行数值差分,利用向前差分的方法对公式( 2) - ( 3) 进行数值差分,得出2005 - 2013 年南京市人口总数。三种数值模拟的具体方程式及模型拟合仿真效果如图2 所示。

本研究通过将Leslie矩阵预测模型的不确定性因素考虑到灰色预测中,得到合成的Leslie矩阵灰色预测模型,以2013 年南京市818. 78 万人为参考值,将实测值与三种模型的预测值进行比较,对Leslie矩阵灰色预测模型与Leslie矩阵预测模型和灰色预测模型进行K - S拟合检验,从K - S拟合概率角度看,Leslie矩阵灰色预测模型的拟合概率相对较高,可认为比其他两种模型更能准确地描述人口增长变化特征,同时,Leslie矩阵预测模型拟合程度较低,可认为存在一定的拟合偏差。结果如表1所示。

注: 概率值为分布模型准确性检验的概率值。

由表1 中三种模型的误差精度比较,Leslie矩阵灰色预测模型误差精度最小。在短时间内出生率和死亡率不变,即人口年龄结构不变的情况下,考虑三种模型对南京市2005 - 2013 年的人口总数的预测结果,通过结果数据的比较,可以看出改进Leslie矩阵灰色预测模型的预测误差值最小,均有效的控制在5% 以内,精确度最高。因此利用改进Leslie矩阵灰色预测模型对人口预测具有很大的可行性和有效性。

4 结束语

本文分别运用了改进Leslie矩阵灰色预测模型对人口规模进行预测。从预测结果来看,相比于Leslie矩阵预测模型与灰色预测模型,Leslie矩阵预测模型结果偏大,灰色预测模型结果偏小,改进Leslie矩阵灰色预测模型居于二者之间。究其原因: 将不可实测的影响变量转化为灰色预测,并加入Leslie矩阵预测模型中,得到的预测值更加接近实际情况。

综上所述,Leslie矩阵预测模型所得预测序列发展趋势稳定,预测结果较为保守,对于发展趋势稳定的区域,预测效果良好,但可能不太适应人口变动幅度大的区域。灰色预测模型中由于各种曲线模型反应的趋势有所差异,如线性模型变化较为稳定,指数模型发展趋势呈现先慢后快的状况,对数模型则恰好相反。所以,应在可预见的范围内,对人口发展趋势做出大致可靠的估计,选择改进Leslie矩阵灰色预测模型,对人口预测具有实际的参考意义。

参考文献

[1]刘萌伟,黎夏,刘涛.基于基因表达式编程的人口预测模型[J].中山大学学报:自然科学版,2010,49(6):115-120.

[2]秦中春.中国未来人口变化的三大转折点预测——基于年龄移算人口预测模型的分析[J].区域经济评论,2013,12(2):5-14.

[3]吴琼,陈永当,秦路宇.GM(1,1)模型及其在陕西省人口数量预测中的应用[J].中国管理信息化,2015,18(3):156-158.

[4]卞焕清,夏乐天.基于灰色马尔科夫链模型的人口预测[J].数学的实践与认识,2012,42(7):127-132.

[5]田成诗,朱佳宝.我国省域人口的时序预测模型的选择——基于预测精度、偏差和不确定性的分析[J].数学的实践与认识,2014,44(12):157-169.

[6]曹美丽.内蒙古人口灰色模型及Verhulst模型预测分析[J].经济论坛,2012,508(11):40-42.

[7]胡泊.灰色Verhulst模型在长春市人口预测中的应用[J].理论经济学,2009,3:21-23.

[8]甘蓉蓉,陈娜姿.人口预测的方法比较——以生态足迹法、灰色模型法及回归分析法为例[J].西北人口,2010,31(1):57-60.

[9]袁小平,梁海艳.中国人口年龄结构变动对出生率的影响研究[J].西北人口,2014,35(6):49-53.

[10]邓聚龙.灰色系统理论教程[M].武汉:华中理工大学出版社,1990.

预测矩阵 第3篇

关键词：网格,蛋白质二级结构预测,结构分类,位矩阵编码,并行遗传算法

随着人类基因组计划的完成,进入了以基因功能研究为核心的“后基因组时代”,大规模的结构基因组、蛋白质组以及药物基因组的研究计划已经成为新的热点。每天在全世界,大量的生物学数据不断地产生和积累,要有效地处理、保存和利用这些处于异域的巨量信息,必须建立强大而高效的信息处理平台,“生物信息网格”应运而生。

蛋白质结构预测是生物信息学中一个重要问题,它研究如何从氨基酸序列出发,预测蛋白质的功能构象。20世纪50年代后期,Christian B.Anfinsen等人[1]通过蛋白质复性实验证实:某些蛋白质在体外的一定条件下解聚失活后,可以自动折叠而恢复其原有的高级结构与活性。这就意味着蛋白质空间结构的全部信息蕴藏在蛋白质的一级结构(即蛋白质的氨基酸序列)中。蛋白质一级结构决定其高级结构是蛋白质结构预测的理论基础。蛋白质的二级结构在蛋白质肽链快速折叠成具有特定功能的构象方面,扮演着极其重要的角色。因此,蛋白质二级结构的预测不仅有助于了解蛋白质的功能及其作用机制,对于正确预测蛋白质的空间结构更具有非常重要的意义。

目前对蛋白质预测的大部分研究主要是基于对已知蛋白质结构规律的总结、吸收和利用,采用所谓的、基于知识的预测(Knowledge-based Protein Modeling)。蛋白质结构预测方法总体上可分为三大类,即比较建模法(Comparative modeling method)、反向折叠法(Inverse folding)和从头预测法(ab initio prediction method)。目前,比较建模法和反向折叠法的研究都已取得了重要的进展,这两类方法的共同点是:在预测目标蛋白质的结构时都要利用已知的结构数据库。当目标蛋白质找不到同源蛋白质, 或同源性过低时,这些方法都无法奏效。而从头预测法仅利用氨基酸序列和模拟氨基酸间相互作用的模型来预测目标蛋白质的空间结构, 因此具有更大的发展空间,也是我们关注的重点。这种方法的关键在于发展更高效的搜索方法用于功能构象的搜索,有很多工作研究用遗传算法[2,3]、神经网络[4,5]和模拟退火法[6]等协同算法来解决,取得了一定的成效。但他们也存在算法收敛性不确定[2,6];算法并行度低[3];预测准确率不高[4];过于依赖数据集的规模[5]等缺点。

在后者的基础上,对上述算法进行改进和优化,提出了一种基于结构分类的按位矩阵编码的并行遗传算法来进行预测。为了充分发挥并行算法的优势,在网格平台进行部署,实验表明预测效率得到较大的提高。

1 基于网格的蛋白质二级结构预测

1.1 问题描述

蛋白质二级结构的基本类型包括α螺旋、β折叠、β转角和无规卷曲,弄清其折叠类型对合理设计生化实验,进行功能研究十分重要。蛋白质特定空间构象是其功能活性的基础,因而空间构象预测可为蛋白功能研究提供启示。根据在笛卡儿空间中使用全原子力场(force field)和外部溶剂描述的分子动力学(MD)方法所建立的时间函数,被认为能够可靠再现多肽链的运动。如果上述理论成立, 那么从一个随机结构出发, 只要产生一条足够长的轨道, 就可以找到功能构象。但事实上,这是一个NP难问题,以目前的计算机能力很难满足“足够长”这一条件。目前的计算能力能产生的MD轨道大约为10-8s, 而蛋白质体外折叠通常需要1 s。也就是说, 即使是一个短肽, 搜索其构象空间的计算量也是十分巨大的[7]。

传统的二级结构预测方法,如Chou-Fasman方法和GOR方法等的预测精度比较低,Chou-Fasman 方法是一种统计方法,通过统计每种氨基酸在α螺旋、β折叠和无规卷曲中出现的频率得到反映20种氨基酸形成三种二级结构的倾向性因子;GOR方法运用信息论的基本原理,将多肽链上一连串的R基团作为一种信息,在蛋白质的折叠中,这种信息被翻译成构象状态。人工神经网络方法的应用将二级结构预测的精度提高到70%以上。一般认为, 如果二级结构的预测准确率能达到80%,那么便可以基本准确地预测一个蛋白质分子的三维空间结构,因此进一步提高蛋白质二级结构预测的准确度是非常关键的。

遗传算法是一种高频率的全局自适应搜索算法,适合于能量最低状态的搜索(按热力学假说,蛋白质在天然状态的能量最低)。但是,由于随着人类基因组和蛋白质科研信息迅速膨胀,在基因组、蛋白质组水平上的生物学数据巨量增长,而且众多生物学数据库分散在不同的异构平台上,在一般网络平台上使用普通遗传算法不仅无法达到生物信息数据整合、智能化的复合、交叉检索、共享、可视化和使用统一的用户界面,还容易因为蛋白质的势能面上存在着很多的局部极小点而陷入局部极值。为了充分利用网络资源,提高预测效率,根据网格动态性、异构性、可扩展性和自治性的特点,采用基于网格的并行遗传算法显然更利于问题的解决。

1.2 基于结构分类的按位矩阵编码的并行遗传算法

目前,用于蛋白质二级结构预测的数据大部分来源于PDB(Protein Data Bank)数据库。PDB数据库中将蛋白质结构分为G,H,I,B,E,S,T和C共8类,简化表示为3类:(a)Helices,包括G,H,I三类,记为H;(b)Sheets,包括B和E二类,记为S;(c)Coils包括S,T和C三类,记为C。由于(1)数据量太大;(2)PDB库更新是很快的,造成某些蛋白质索取码发生变动;(3)并不是所有的蛋白质都适合于预测,因此我们先对随机选取出的数据进行分类预处理,并把预处理后的数据作为初始种群,每个蛋白质作为一个个体。

1.2.1 结构分类预处理

预处理采用Chou-Fasman 算法,参照蛋白质结构分类数据库(SCOP)的二级结构分类方法,将蛋白质的结构类型分为All-α、All-β、α/β和其他(见表1) [8]。

1.2.2 位矩阵编码并行遗传算法

遗传算法是由美国密执安大学的John Holland教授于1975年首先提出的一种仿生类优化算法,它以达尔文的生物进化论“适者生存、优胜劣汰”和孟德尔的遗传变异理论“生物遗传进化主要在染色体上,子代是父代遗传基因在染色体上的有序排列”为基础,模拟生物界进化过程。

经典遗传算法存在着局部搜索性能较差的缺陷,对于某些分布变化缓慢的问题,常常需要进行大量的计算,并且由于进化初期的超常个体使得种群过早收敛到局部最小值。为了解决这一缺陷,在遗传算法并行运算的基础上,通过多种群并行进化和引入迁移算子进行种群间信息交流的思想,将遗传算法分解为在多个子种群间并行进行,并通过子种群间交叉来增加基因模式数,避免未成熟收敛。并行遗传算法就是指将遗传算法的计算工作分发到一组并行计算机上并行计算,加快计算速度。并行遗传算法有三种形式:全局并行模型,粗粒度模型和细粒度模型,其中粗粒度模型以其实现简单,便于在网格中多个Agent执行,以及容易模拟等优点,被我们选用。

1.2.2.1 编码

组成蛋白质的氨基酸有20种,根据二维晶格模型,它们在空间有一定的组成和顺序。显然,简单地用一维的二进制编码无法很好地反映蛋白质构象的组成。采用一种多维位矩阵来对蛋白质构象进行编码,这样能更利于遗传算法进行搜索。对于20种氨基酸,采用5位二进制编码,例如氨基酸a用(00001)表示,氨基酸c用(00010)表示,,氨基酸y用(10010)。对于二维晶格模型,蛋白质构象链分为4个方向,每个方向用一个4位二进制表示,构造示意图见图1。对于图2中一个蛋白质构象(acy),编码就为:,其他的构象编码以此类推。

1.2.2.2 染色体和适应度函数

我们将疏水作用力作为衡量自由能的唯一标准,根据适应度函数选择准备进行交配的染色体父串,适应度函数为[9]:

$Fitness(i)=(E(i)-E{}_{\min })/(E{}_{\min }-E{}_{\max })。$

式中E(i)=-1X (X为该构象中HH类的拓扑相邻的数目),为某构象的能量;Emin为该次迭代中构象的最低能量,是一小于或等于0的整数;Emax为该次迭代中构象的最高能量,是一小于或等于0的整数。当Emin=Emax时,该次迭代中所有构象的能量都一样,则此时进行随机选择来决定亲本。

1.2.2.3 交叉和变异

由于交叉的作用是产生新个体,实现算法的全局搜索能力,因此交叉概率要与个体适应度有关。为了避免产生无效基因,我们采用位交叉算子和根据适应度函数评估而定的交叉策略,即用适应度函数评估位交叉的结果,只有适应度能得到提高的变化才能接受。变异起维持种群多样性的作用,即产生新个体和抑制早熟,但概率不大,我们取固定变异概率p =0.05,变异策略采用为并行遗传算法设计的多级变异策略[10]。

1.3 评价指标

为了将我们的方法与其他的方法进行公平的对比,必须要有统一的评价指标。根据国际通用标准,在只提交蛋白质一级序列的前提下,我们选用以下3个标准:

(1)三态准确率

$Q{}_i={\rm P}{}_i/({\rm P}{}_i+{\rm O}{}_i),i\in \{{\rm H},E,C\}。$

其中Pi表示被正确预测为i态的残基个数,Oi表示被错误预测为i态的残基个数。

(2)整体准确率

$Q{}_3=({\rm P}{}_a+{\rm P}{}_b+{\rm P}{}_c)/{\rm T}。$

其中Pi(i∈{a,b,c})分别表示被正确预测出的三态(H,E,C)的残基个数,T代表残基总数。

(3)Motthew函数

$\begin{array}{l}C{}_i=\frac{p{}_{i}n{}_i-\mu {}_{i}o{}_i}{\sqrt{(p{}_i+\mu {}_i)(p{}_i+o{}_i)(n{}_i+\mu {}_i)(n{}_i+o{}_i)}},\\ i\in \{{\rm H},E,C\}。\end{array}$

其中pi表示i态的残基个数,ni表示非i态被预测为非i态的残基个数,μi表示i态被预测为非i态的残基个数,oi表示非i态被预测为i态的残基个数。Ci=0时,称为随机预测;Ci=1时,称为完全预测[11]。

1.4 实验及结果

我们在3台P4 2.4 G,512 M内存的机器中,安装Globus Toolkit3[12]进行实验,将并行遗传算法迭代次数固定为50代,然后对经过预处理的95条蛋白质进行预测。我们把本文算法(GPSSP, Grid-based Protein Secondary Structure Prediction)的预测进行15次后的平均结果分别与在Internet平台下基于BP神经网络(PPSSBP, Predicting Protein Secondary Structure based on BP Neural Network)、Chou-fasman算法、普通遗传算法和模拟退火法的混合算法(HGA, Hybrid Genetic Algorithm)以及国际上目前比较好的蛋白质2级结构预测算法APSSP2(Advance Protein Secondary Structure Prediction)和SOMPA(Self Optimized Prediction Method from Aligment)进行预测的平均结果进行比较(如表2所示),显示本算法是具有一定优势的。

(注:H代表α螺旋,E代表β折叠,C代表无规则卷曲;QH代表α螺旋的预测准确率,QE代表β折叠的预测准确率,QC代表无规则卷曲的预测准确率;CH、CE、CC分别为三态的Matthews函数;Q3claim代表为该算法宣称的预测准确率;Q3代表整体准确率)

从目前的研究来看,使用混合算法可以提高蛋白质二级结构预测的准确率,如APSSP2(采用最近邻居法和神经网络混合),SOMPA(采用GOR算法、Levin预测同源算法、双重预测算法、PHD算法和CNRS算法进行混合)和HGA等等,他们普遍可以达到75%～85%的预测率,比单一的预测算法(PPSSBP算法、Chou-fasman算法等)更具优势。

在实验中可以看出,本文提出的算法虽然属于单一算法,但已经达到并优于其他混合算法的预测结果。这主要是由于:首先,位矩阵编码比二进制编码更适合表达蛋白质构象;其次,有目的地对数据进行预处理,即结构分类,使数据集的功能性更加突出;最后,借助网格高性能的并行计算能力,使采用位矩阵编码的并行遗传算法的性能能最大发挥出来,在较短时间内获得全局较优解。

如果将我们的算法改为混合算法,如与蚂蚁算法结合,利用蚂蚁算法对结构分类的蛋白质数据进行预筛选,抽取能决定预测结果的关键数据集,再利用并行遗传算法进行蛋白质二级结构预测,预计也能提高预测的精度,这将是我们下一步的研究工作。

2 总结

蛋白质结构预测是生物信息学中一个重要问题,蛋白质特定空间构象是其功能活性的基础,因而空间构象预测可为蛋白功能研究提供启示。但事实上,这是一个NP难问题。传统的二级结构预测方法,如Chou-Fasman方法和GOR方法等的预测精度比较低。而提高蛋白质二级结构预测的准确度,对于预测一个蛋白质分子的三维空间结构是非常关键的。针对生物信息数据呈指数形式快速增长,而且相关数据库存在不同的地域,受不同的组织拥有,以及预测问题的NP难本质,本文提出了一种网格中基于结构分类的、按位矩阵编码的并行遗传算法来进行预测,实验表明预测效率和精度均得到较大的提高,并为下一步的研究工作打下了坚实的基础。

参考文献

[1] Frederic M R.The protein folding problem.Scientific American,1991;1:31—34

[2] Backofen R,Will S,Clote P.Algorithmic approach to quantifyingthe hydrophobic force contribution in protein folding.In:Klein R,Altman B.Pacific Symposium on Biocomputing,2000.Singapo re:World Scientific Publishing Co Pte L td,2000;95—106

[3] Baker D.A surprising simplicity to protein folding.Nature,2000;405:39—42

[4] Wu C H,Artificial neural networks for molecular sequence analysis.Comput Chem,2006;21(4):21—24

[5] Chandonia J.The importance of larger data sets for protein secondarystructure prediction with neural networks.Protein Sci,2006;5(4):12—16

[6] Pedersen J T,Moult J.Ab initio protein folding simulations with ge-netic algorithms:simulations on the complete sequence of small pro-teins.Proteins,2005;(1):35—39

[7]倪红春,王翼飞,史定华.遗传算法在蛋白质结构预测中的应用.上海大学学报(自然科学版),2001;(6):18—20

[8]李菁,相秉仁.基于结构分类的BP神经网络预测蛋白质二级结构.药学进展,2003;27(2):7—9

[9]熊赟,陈越,朱扬勇.ProFaM:一个蛋白质序列家族挖掘算法.计算机研究与发展,2007;(7):14—15

[10]何婷婷,戴文华,焦翠珍.基于混合并行遗传算法的文本聚类研究.中文信息学报,2007;(4):3—5

[11]张海霞.蛋白质二级结构预测方法的评价.计算机与应用化学,2006;20(6):17—19