（计算机软件与理论专业论文）并行蚁群优化在蛋白质结构预测中的应用研究.pdf

删 苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属在 年一月解密后适用本规定。 非涉密论文口 论文作者签名：墨泣鳆 日 导师签名：墨兰笔 日 并行蚁群优化在蛋白质结构预测中的应用研究 摘要 并行蚁群优化在蛋白质结构预测中的应用研究 摘要 蛋白质三维结构对于生物学和医学来说意义重大，利用生化手段测定蛋白质结 构代价高，耗时长，因此利用计算手段预测蛋白质三维结构逐渐成为计算生物学的重 要课题。在巨大的构象空间中如何有效的搜索，是该课题的重大挑战之一。本文研究 将并行蚁群优化技术应用于蛋白质结构预测问题。 针对基于二维h p 模型的蛋白质结构预测问题，设计了串行算法a c o h p 和基 于共享信息素矩阵的并行算法p a c o h p ，并通过1 1 条测试集对并行算法进行评价， 其中8 个得到了最优解。这为将共享信息素矩阵的并行蚁群算法应用到更真实复杂 的蛋白质三维结构预测提供了基础。 对于蛋白质三维骨架预测问题，通过共享信息素方法将多个能量函数融合，设计 了p a c b a c k b o n e 预测算法。针对蛋白质l o o p 区域灵活多变的特性，采用了局部优化 技术。同时设计了交叉构象操作，能以较少开销衍生更多优质的蛋白质候选构象。选 择最适合的聚类算法和甄别方法，在众多的候选结构中挑出最接近于天然结构的构 象。 用c a s p 8 所公布的1 3 个从头预测类别目标作为测试集，对p a c b a c k b o n e 进行 了测试。与c a s p 8 比赛结果的实际排名进行对照，其中有2 个目标的预测结果超过 c a s p 8 中最好的结果，7 个位列前1 0 名。实验结果证实，利用共享信息素矩阵的并 行蚁群算法解决蛋白质结构预测问题，是一种有潜力的新方法。 关键词：蛋白质结构；从头预测；蚁群算法；并行 作者：吴进珍 指导教师：吕强 t h es t u d yo na p p l y i n gp a r a l l e la n tc o l o n y o p t i m i z a t i o nt op r o t e i ns t r u c t u r ep r e d i c t i o n a b s t r a c t t h e t e r t i a r ys t r u c t u r eo fp r o t e i ni so fs i g n i f i c a n c ef o rb i o l o g ya n dm e d i c i n e h o w - e v e r ，i ti se x p e n s i v ea n dt i m e - c o n s u m i n gt oo b t a i np r o t e i ns t r u c t u r ew i t hb i o c h e m i c a l m e t h o d s t h e r e f o r ep r e d i c t i n gp r o t e i nt h r e e - d i m e n s i o n a ls t r u c t u r ew i t hc o m p u t a t i o n a l m e t h o d sh a sb e c o m ec r i t i c a l i nc o m p u t a t i o n a lb i o l o g y h o wt oe f f e c t i v e l ys e a r c hi n t h ev a s tc o n f o r m a t i o n a ls p a c ei so n eo ft h em a j o rc h a l l e n g e so ft h i sp r o b l e m i nt h i s t h e s i s ，w ep r o p o s et oa p p l yp a r a l l e la n tc o l o n yo p t i m i z a t i o nt e c h n i q u et ot h ep r o b l e m o fp r o t e i ns t r u c t u r ep r e d i c t i o n f o rp r e d i c t i n gp r o t e i ns t r u c t u r eb a s e do nt w o - d i m e n s i o n a lh pm o d e l ，w ed e s i g n as i n g l ea n tc o l o n ya l g o r i t h m a c o h p ，a n dt h ec o r r e s p o n d i n gp a r a l l e lv e r s i o nw i t h s h a r e dp h e r o m o n em a t r i x p a c o h p f o rat e s ts e to f1 1i n s t a n c e s ，p a c o h po b t a i n s 8o p t i m a ls o l u t i o n s t h ee x p e r i m e n tr e s u l t si n s p i r eu st oa p p l yt h es a m es t r a t e g y t ot h er e a l i s t i ca n dc o m p l e xp r o b l e mw h i c ht r i e st op r e d i c tt h r e e - d i m e n s i o n a lp r o t e i n b a c k b o n e f o rt h eb a c k b o n ep r e d i c t i o no fp r o t e i n ，w ed e s i g na n di m p l e m e n tp a c b a c k b o n e ， w h i c he m p l o y sp a r a l l e la n tc o l o n i e sw i t hs h a r i n gp h e r o m o n em a t r i x s u c hp a r a l - l e ls t r a t e g ye n a b l e st of u s et h ed i f f e r e n tt y p e so fe n e r g yf u n c t i o n s i na d d i t i o n ，w e p r e s e n tl o c a lo p t i m i z a t i o nt e c h n i q u et or e f i n et h ef l e x i b l el o o pr e g i o n s ，a n dac r o k s - c o n f o r m a t i o no p e r a t i o nt og e n e r a t em o r eh i g h - q u a l i t yc a n d i d a t ec o n f o r m a t i o n sw i t h l i t t l ec o s t f i n a l l yw et u n et h ep r o p e rc l u s t e r i n ga l g o r i t h mt od i s c r i m i n a t et h ec o n f o r m a t i o nc l o s ee n o u g ht ot h en a t u r ec o n f o r m a t i o nf r o mt h ed e c o y s w ee v a l u a t ep a c b a c k b o n ew i t ha l l1 3d en o v op r e d i c t i o nt a r g e t sf r o mt h el a t e s t c a s p 8 ，a n dc o m p a r et h ea c c u r a c yw i t ht h ep u b l i s h e dr e s u l t so ft h ec o m p e t i t i o n si n c a s p 8 a m o n gt h er e s u l t sf r o mp a c b a c k b o n e ，t w os t r u c t u r e sa r et h eb e s t ，a n d7 s t r u c t u r e sa r et o p1 0 t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tp a c b a c k b o n e ，c o n s i s t e do f p a r a l l e la n tc o l o n i e sw i t hs h a r i n gp h e r o m o n em a t r i x ，i san o v e la p p r o a c hf o rp r o t e i n s t r u c t u r ep r e d i c t i o n k e y w o r d s ：p r o t e i ns t r u c t u r e ；d en o v ep r e d i c t i o n ；a n tc o l o n ya l g o r i t h m ；p a r a l l e l i i i s t r a c tt h es t u d yo na p p l y i n gp a r a l l e la c ot op r o t e i ns t r u c t u r ep r e d i c t i o n w r i t t e nb y ：w uj i n z h e n s u p e r v i s e db y ：l i iq i a n g 并行蚁群优化在蛋白质结构预测中的应用研究 目录 第一章 1 1 1 2 1 3 1 4 第二章 2 1 2 2 2 3 2 4 2 5 2 6 第三章 3 1 3 2 目录 引言 课题背景 研究内容 研究意义 本文的组织结构 蛋白质结构预测概述 蛋白质相关领域知识概述 面向计算机的蛋白质表示方法 经典的蛋白质结构预测方法 2 3 1h p 模型 2 3 2 t o y 模型 2 3 3i t a s s e r 方法 2 3 4r o s e t t a 方法 r o s e t t a 方法采用的片段库 优化算法概述 2 5 1 模拟退火 2 5 2 蚁群算法 本章小结 并行蚁群优化在h p 模型中的应用 问题描述 3 。1 ，1蛋白质的表示方法 3 1 2 能量函数 3 1 3 搜索空间 方法 3 2 1单蚁群算法a c o h p l 1 4 5 6 7 7 9 0 1 2 3 4 5 8 8 9 0 1 1 1 2 2 2 2 l 1 4 5 6 7 7 9 m n 抡 培 m 埒 掩 蝎 均 牡 殂 殂 娩 挖 毖 勉 目录并行蚁群优化在蛋白质结构预测中的应用研究 3 2 2 局部优化2 4 3 2 3 信息素更新与收敛条件2 4 3 2 4并行蚁群算法p a c o h p 2 4 3 3 结果2 5 3 3 1 试验数据集2 5 3 3 2 试验环境及参数设置2 6 3 3 3 试验结果及其评价2 6 3 4 本章小结2 8 第四章并行蚁群在蛋白质骨架预测中的应用2 9 4 1 问题描述2 9 4 1 1搜索空间3 0 4 1 2 能量函数3 0 4 2 从头预测蛋白质结构算法流程设计3 2 4 3 单蚁群优化骨架算法设计3 3 4 3 1 蚁群算法的主框架3 3 4 3 2 构造构象3 5 4 3 3 局部优化3 6 4 3 4 更新信息素3 7 4 3 5 l o o p r e b u i l d 3 8 4 4 并行蚁群优化骨架算法的设计3 8 4 4 1 并行蚁群算法机制与必要性3 8 4 4 2 并行蚁群算法3 9 4 4 3并行算法中的交叉操作3 9 4 5 聚类与模型选择4 1 4 5 1 聚类的必要性4 1 4 5 2 聚类方案4 2 4 6 本章小结4 4 第五章骨架预测结果及分析4 5 5 1 测试数据来源4 5 并行蚁群优化在蛋白质结构预测中的应用研究 目录 5 2 评价方法4 5 5 2 1构象之间的相似度描述准则4 5 5 2 2c a s p 8 中评价预测准则 4 7 5 3 蛋白质骨架预测结果与分析4 7 5 3 1试验环境及算法参数设计4 7 5 3 2 交叉操作4 8 5 3 3 聚类4 9 5 3 4蛋白质骨架预测结果5 0 5 4 本章小结5 4 第六章结束语5 5 6 1 论文总结5 5 6 2 研究展望5 6 参考文献5 7 发表文章目录及参与项目6 3 致谢6 5 并行蚁群优化在蛋白质结构预测中的应用研究 插图 插图 1 1 基因到蛋白质功能 1 1 2 蛋白质折叠的热力学描述 2 2 1 氨基酸及其侧链的构成 7 2 2 两个氨基酸脱水形成肽链 8 2 3 多肽链自折叠成蛋白质三维示意图 8 2 4 一级到四级结构相互关系图 8 2 5 二级结构在三级结构中的形式 9 2 6 蛋白质骨架原子及扭转角度1 0 2 7 蛋白质侧链原子及扭转角度1 1 2 8h p 模型构象图1 1 2 9 t o y 模型构象图1 3 2 1 0i - t a s s e r 方法流程图1 4 2 1 19 残基“窗口 示意图1 7 3 1 3 2 4 1 4 2 4 3 4 4 5 1 5 2 5 3 5 4 相对坐标系统中解元素的表示方法2 2 二维h p 模型预测构象图2 7 从头预测蛋白质算法流程图3 3 单蚁群算法流程图3 4 并行蚁群算法流程图4 0 交叉构象示意图4 1 本文对t 4 1 6 一d 2 ( 上) 和t 5 1 3 d 2 ( - v ) 预测出的s t a r t i n gd e c o y s 和交 叉操作所生成的d e c o y s 的能量值和r m s d 比较结果4 8 四种聚类方法选择模型1 结构后的g d t t s 图 5 1 目标t 4 1 6 - d 2 ( 左) 和目标t 4 4 3 - d 1 ( 右) 的叠加比较情况：天然结 构( 红) ，c a s p 8 中s e r v e r 类最好结构( 蓝) 和本文预测结构( 黄) 5 2 p a c b a c k b o n e 与其他两组z s c o r e 比较情况5 3 并行蚁群优化在蛋白质结构预测中的应用研究 表格 表格 3 1 疏水与亲水残基分类表2 1 3 2 二维h p 模型数据集2 5 3 3 试验结果2 6 4 15 个不同能量函数的权重设置3 2 5 1c a s p 8f m 预测案例4 6 5 21 3 个f m 预测案例聚类结果5 个结构中最优结构4 9 5 31 3 个f m 预测案例聚类结果一模型1 结构5 0 5 4 p a c b a c k b o n e 结果与c a s p 8 结果的比较情况5 2 5 5 p a c b a c k b o n e 与z h a n g - s e r v e r 和b a k e r - r o b e t t a 两个小组的z - s c o r e 比较情况5 3 并行蚁群优化在蛋白质结构预测中的应用研究 算法 算法 1r o s e t t a 3 0 蛋白质结构预测算法1 6 2 蚁群算法a c o h p ( 8 ，n ，t ，e ) 2 3 3 并行蚁群算法p a c o h p ( 8 ，n ，e ，p ) 2 5 4 单蚁群算法a c ( s ，n ，兀u ，丁，e ) 3 4 5 构造算法c o n s t r u c t i o n c o n f o r m a t i o n ( m ) 3 5 6 局部优化算法l o c a l o p t i m i z a t i o n ( m 曲) 3 7 7 并行蚁群骨架预测算法p a c b a c k b o n e ( ) 3 9 并行蚁群优化在蛋白质结构预测中的应用研究 第一章引言 第一章引言 1 1 课题背景 蛋白质在生物体内执行着各项与生命相关的重要任务，比如酶的催化、氧气的传 输、信号的传递等等，所以说蛋白质是生命活动的主要承担者。随着后基因组时代的 来临，生物信息学的主要任务是了解基因以及蛋白质的主要功能 1 】。生物体的基因 组规定了组成蛋白质的氨基酸序列，而只有将构成蛋白质的氨基酸线性序列折叠成 特定的空间构象后蛋白质才能表现出多种多样的功能，整个过程如图1 1 所示。除此 之外，蛋白质结构是设计药物分子的基础。所以说获得蛋白质的三维结构对于研究其 功能和设计蛋白质或改造已有蛋白质【2 】具有非常重要的意义。 匦d 国t 罾学僵定留 图1 1 ：基因到蛋白质功能 确定蛋白质三维结构的实验方法主要有两种：一种是x 射线晶体衍射，另外一 种是核磁共振( n m rn u c l e a rm a g n e t i cr e s o n a n c e ) 。前一种方法需要使待测蛋白质 结晶，然而获得蛋白质的晶体并不容易，对于某些膜蛋白结晶更加困难。而后一种方 法不用结晶蛋白质，能够直接在溶液中测定蛋白质三维结构，但是该方法的主要缺 点是它只能测定较小蛋白质的结构。由于蛋白质在溶液中是具有活性的，所以在结 晶后，确定的仅是蛋白质在溶液中某一时刻的构象，而n m r 方法可以确定若干个构 象。这两种方法都可以确定高精度和高解析度的蛋白质结构，在现在蛋白质结构数据 库p d b 3 1 ( p r o t e i nd a t ab a n k ) 中的大多数蛋白质都是通过这两种方法确定的，但 是这两种方法的相同点是操作耗时、花费昂贵。就目前而言，蛋白质序列数据库的数 据积累速度远远超过了蛋白质结构数据库中结构的积累速度，随着人类对蛋白质结 构的要求日益迫切，仅通过上述两种方法确定蛋白质三维结构明显不能满足要求。因 此，通过理论知识和经验，利用计算机预测蛋白质结构的方法应运而生。 1 9 6 1 年，诺贝尔奖获得者a n f i n s e n 验证了蛋白质的氨基酸序列完全确定其三维 立体结构4 1 ，进而认为，蛋白质的天然结构有可能对应到全局自由能量的极小值 5 】， 如图1 2 。这个发现为蛋白质结构预测奠定了理论基础。因此，可将蛋白质结构预测 问题描述成为：寻找一种从蛋白质的氨基酸序列到蛋白质所有原子的空间坐标的一 并行蚁群优化在蛋白质结构预测中的应用研究 质的构象的全局自由能最小。众所周知，一个普通的蛋白质是由 包括上千个原子，由序列到结构的空间映射随着原子的个数指数 具有超强计算能力的计算机和合理的映射方法。 h 嘏虹嘶嘴甜嫩白即睫蛔- 埘勘哪 图1 2 ：蛋白质折叠的热力学描述 目前的蛋白质结构预测方法根据其序列的同源性可分为两大类【6 ，7 】：基于模板 的建模( t e m p l e t eb a s e dm o d e l i n g ，t b m ) 与自由建模( f r e em o d e l i n g ，f m ) 。这两 种方法在近几年来的应用最为成功。 基于模板的建模，又称为比较建模( c o m p a r a t i v em o d e l i n g ) 。在蛋白质组学上 认为，如果两个蛋白质的氨基酸序列的相似度大于3 0 ，那么认为这两个蛋白质具有 同源性。而这种高度的蛋白质序列相似意味着高度的蛋白质结构相似。基于模板的建 模正是基于这种理论依据的一种蛋白质结构预测方法。其预测过程可以简单描述为： 首先在已知蛋白质结构数据库中搜索与目标蛋白质序列最为相似的蛋白质，并裁剪 搜索到的蛋白质使得与目标蛋白质在序列上能够对齐；然后将搜索到的已知蛋白质 结构作为模板，通过拷贝对齐区域和构造非对齐区域，建立目标蛋白质的骨架；最后 安置侧链，并通过轻微扰动骨架，使得目标蛋白质构象的自由能量最低。这种方法的 关键所在就是是否能够在p d b 中搜索到序列相似的蛋白质以及搜索到的蛋白质的序 2 并行蚁群优化在蛋白质结构预测中的应用研究 第一章引言 列与目标蛋白质序列相似度有多少，也就是说比对的质量是预测精度的关键。如果 两个蛋白质之间的序列相似度低于3 0 ，二者在结构上9 5 区域不一致。如果相似 度大于5 0 ，那么该方法预测的结构与天然结构碳原子之间的r m s d ( r o o tm e a n s q u a r ed e v i a t i o n ) 值一般不大于1 a 。由此可见，基于模板的建模是依赖于已知结构 蛋白质，并对序列相似高于3 0 的蛋白质的预测较为成功，而对于相似度低于3 0 的蛋白质力不从心。 自由建模，又称为从头建模 8 ，9 ，1 0 】( d en o v eo ra bi n i t i om o d e l i n g ) 。如果在已 知蛋白质结构数据库中没有合适的模板，或者是目标蛋白质构象形式在p d b 中不存 在，那么就需要利用从头建模方法。它基于a n f i n s e n 的假设，从蛋白质的一维氨基酸 序列出发，通过反复尝试各种可能的构象最终获得最低自由能的蛋白质结构。自由建 模方法的共同点有：一、不同程度的简化蛋白质的表示方法和离散化蛋白质的构象空 间；二、需要合适的能量函数。通常认为系统能量降低，状态更加稳定，但是目前的 能量函数不能完全反映蛋白质分子的能量状况，所以合适的能量函数对结构的预测 至关重要；三、在构象空间进行搜索。文献【7 ，1 1 ，1 2 ，1 3 指出，蛋白质结构从头预测 有两个关键难点：一、由于有机分子及其内部微粒之间关系的复杂性，目前的能量函 数并不能精确反映分子系统的能量；二、由于蛋白质结构中存在大量的自由度，导致 构象的搜索空间巨大。该方法与基于模板建模法相比，有如下特点：它不依赖于已知 结构蛋白质，也没有同源性的限制。它仅从蛋白质的序列信息就可以预测；由于搜索 空间巨大，导致计算量也增大，所以预测的蛋白质长度不能太长( 一般小于1 5 0 个残 基) ；预测精度相对不高。 由于搜索空间巨大，计算时间随着蛋白质氨基酸的个数呈指数增长，所以精 确算法不能满足需求。既然最优解不能获得，只能用损失最优性来获得实际性。由 于能量函数不能够精确反映蛋白质系统的能量，所以在获得“最好解”的前提下还 要满足解的多样性。这样，优化算法显得尤为重要。蚁群优化( a c o ，a n tc o l o n y o p t i m i z a t i o n ) 算法f 1 4 ，1 5 1 正好满足上述要求，a c o 在学术界已成功的将其应用到不 同的组合优化问题中。在众多的a c o 算法中，最大最小蚂蚁系统( m m a s ，m a x - m i n a n ts y s t e m ) 和蚁群系统( a c s ，a n tc o l o n ys y s t e m ) 是实际应用中性能最好的两 种a c o 算法 1 6 】。并行技术在近几年来发展迅猛，通过将一个问题做合理划分后在 若干个处理器上同时执行，在执行过程中通过数据交换使得性能提高和减少任务开 销。所以并行和优化的结合不仅搜索能力上大有作为并且对优化结果的影响也非常 重大。 由于从头预测难度较大，所以在两年一度的蛋白质结构预测评估大会【1 7 ，1 8 】( c a s pc r i t i c a la s s e s s m e n to ft e c h n i q u e sf o rp r o t e i ns t r u c t u r ep r e d i c t i o n ) 中，将从头 预测作为竞赛中的单独一个类别。c a s p 是世界范围内对蛋白质结构预测技术进行 3 蛋白质二维h p 模型是一种蛋白质预测的简化模型，本文将并行蚁群算法应用 到该问题中，并通过1 1 个测试案例来评价算法性能。 2 并行蚁群优化技术在蛋白质骨架预测中的应用 在优化过程中对蛋白质构象的评价是通过打分机制来实现的。本文采用了 r o s e t t a 3 0 的打分函数，而r o s e t t a 3 0 中打分项众多，且是线性组合，因此，为 了更加合理反应真实的蛋白质折叠过程，本课题在a c o 为主要算法框架的基 础上采用共享信息素的机制，将不同的能量函数分散到不同的线程当中，这样 在预测过程中通过各线程的相互制约，最终达到提高预测质量的目的。除此之 外，另一个直接的原因是，从头预测蛋白质结构花费时间较多，采用并行，显然 能够加快计算速度。 3 聚类分析 在从头预测过程中，能量函数并没有对熵做过多考虑，因此对于双盲的预测， 需要生成大量的候选结构，且为了追求更小的自由能，需要通过聚类来确定最 优构象。所以本文设计了多种聚类方案，通过相互比较来确定最适合的聚类算 法和模型选择方法。 4 并行蚁群优化在蛋白质结构预测中的应用研究 第一章引言 4 应用真实数据集测试 本文采用c a s p 8 中的f m 类别中的1 3 个真实的蛋白质作为数据集，采用并行 优化优化技术作为预测手段，与c a s p 8 公布的预测排名进行比较，同时还与蛋 白质结构预测中最具权威b a k e r r o b e t t a 组的r o s e t t a 和z h a n g - s e r v e r 组 的i - t a s s e r 进行比较。 1 3 研究意义 蛋白质结构预测意义重大，主要体现在以下方面： 1 知道蛋白质结构对生物学或医学都是非常重要的。这不仅有利于认识蛋白质的 功能和蛋白质是如何执行其功能，还能为设计新的蛋白质或改造已有蛋白质提 供可靠的依据。许多药物分子做的靶结构通常是蛋白质酶，其活性部位或结合 部位是药物作用的目标，这些结构只有具有特定的空间构象，才能和特定的药 物小分子相结合，从而发挥药的作用。所以蛋白质空间结构还可以为新的药物 分子设计提供合理的靶分子结构。 2 传统的得到蛋白质结构是通过试验方法x r a y 和n m r 。但是这些方法操作复 杂、花费时间较长，价格也较为昂贵。例如：蛋白质测序需要$ 1 ，0 0 0 $ 4 ，0 0 0 ，而 得到蛋白质结构需要$ 2 5 0 ，0 0 0 - $ 5 0 0 ，0 0 0 。随着基因组的测序的成功，蛋白质序 列数据库的数据积累的速度远远超过了蛋白质结构数据库的速度。就目前而言 蛋白质序列数据库( u n i p r o t k b ) 收录的序列条数为1 1 ，3 8 4 ，8 9 8 条，而p d b 中 收录的结构仅有6 5 ，5 2 7 个( 截止2 0 1 0 年5 月) 。显然用传统试验的方法来确定 所有的蛋白质结构几乎是不可能的。如果采用理论计算方法，借助计算机的强 大处理能力来预测，显然要方便的多。 3 从头预测方法意义更为重要，大规模从头预测能够指导发现新的蛋白质折叠， 并能够对基于模板建模方法不能处理的结构预测进行弥补，还可以通过来自交 叉耦合或其他实验约束进行补充，能够对不容易由x - r a y 和n m r 试验确定结 构的蛋白质提供候选结构。允许基于粗糙结构洞察大量蛋白质功能。 并行优化技术应用与从头预测蛋白质结构的意义主要体现在如下方面： 1 预测蛋白质的结构，需要搜索一个非常巨大的空间，对于构象的搜索一直是该 任务的瓶颈之一。所以迫切需要合适的优化搜索算法。 2 能量打分函数是蛋白质预测的另一瓶颈。由于能量函数较多，引入并行能够将 这些能量函数相互协调，以至于更近似的模拟天然状态下蛋白质的折叠过程。 5 6 从头预测蛋白质结构涉及到蛋白质的表示形式、构象空间和能量函数等等，不同 的预测方法在这些方面有不同的体现。按预测结构的空间表现形式可分为平面结构 预测和立体结构预测；如果按预测的解析度可分为以残基为单位的低解析度预测和 以原子为单位的高解析度预测。本章将先对蛋白质预测相关基础知识做一些简要概 述，然后综述了四种经典的从头预测蛋白质结构方法，详细介绍了r o s e t t a 方法中片 段库的生成过程，最后概述了本文用到的优化算法。 2 1蛋白质相关领域知识概述 蛋白质是生物体内的一种大分子结构，它是由多个氨基酸组成。其中，氨基酸是 由以下部分组成：位于中央的c n 碳原子；由氮原子n 构成的氨基h 3 n + ；由碳和氧 原子构成的羧基c o o 一；氢原子h ；侧链r 。氨基酸之间的差别是由侧链r 的不同 形成的，侧链r 由c 、n 、o 、s 、h 原子构成，侧链上的碳原子依次称为c 口、c - v 等等，如图2 1 所示。常见的氨基酸共有2 0 种，通常用一个大写字母表示。一个氨基 f 毒 ，劈 鼎 g蓐童 3 2l c ih 2 - - c h 2 - - c h ： - - c h 2 - - 彳h _ 扩 + n i - 1 8+ n h 3 跏i 雠 图2 1 ：氨基酸及其侧链的构成 酸中的氨基和另外一个氨基酸的羧基脱水，形成肽链，如图2 2 所示。肽链上的每个 氨基酸脱水后形成残基，每两个残基之间以肽键相连。这样一个多肽链经过自折叠就 形成了蛋白质的三维结构，如图2 3 所示。 蛋白质按层次大体上可以分成一级结构、二级结构、三级结构和四级结构，如图 2 4 所示。 蛋白质的一级结构一般指构成蛋白质残基的序列，也就是构成蛋白质肽链的氨 基酸排列，通常用一串大写字母表示。它没有空间概念，但是它是蛋白质三维结构的 基础，也是决定蛋白质功能的基础。具有不同功能的蛋白质往往一级结构就不相同， 因此基因组学和蛋白质组学的研究基础都是蛋白质的一级结构。蛋白质的二级结构 7 第二章蛋白质结构预测概述 并行蚁群优化在蛋白质结构预测中的应用研究 p r i m a r y s t r u c t u r e a m h 自oa a dr e s i d u e s 啦丘l 泔 一肛r + j 占附0 c r 即一1 卜啪 图2 2 ：两个氨基酸脱水形成肽链 图2 3 ：多 s e c o n d a r y s t 】r u c t u r e 图2 4 ： 宅纩 飞泸 足 几 踏 鼯 彤捧 离禽垦 并行蚁群优化在蛋白质结构预测中的应用研究第二章蛋白质结构预测概述 是由多肽链的骨架借助于氢键或其他化学键沿着一维方向排列成具有周期性的结构。 它是蛋白质的局部空间结构，也是构成蛋白质复杂空间构象的基础。这些局部空间结 构在所有的蛋白质中普遍存在，其中包括q 螺旋( nh e l i x ) 、f l - 折叠( ps h e e t ) 、卷 曲( c o i l ) 、环形( 1 0 0 p ) 等等，如图2 5 所示。这些不同大小、不同数目的二级结构 以不同的方式连接起来构成了完整的蛋白质空间结构，称之为蛋白质的三级结构，又 称蛋白质的空间结构、蛋白质构象等等。它确定了蛋白质骨架和侧链的所有原子的空 间位置。在一些较大的蛋白质中，蛋白质是由多条肽链共同折叠形成的，那么这样的 空间结构称之为蛋白质的四级结构，也可以说多个蛋白质的三级结构组成了蛋白质 的四级结构【2 4 】。除此之外，在这些结构之间还有一些其他公认的过度性结构，比如 超二级结构、模体( m o t i f ) 和结构域等等，在此不做过多讨论。 图2 5 ：二级结构在三级结构中的形式 2 2面向计算机的蛋白质表示方法 蛋白质是生物大分子，其结构非常复杂。为了便于预测，通常将蛋白质做适当的 简化，就目前而言，常用的方法有以下几种： 1 以蛋白质的残基为基本单位，仅仅考虑骨架上c o 原子。残基和残基之间用键连 接，通常在预测中忽略键长的影响，即键长是单位长。能量函数体现在残基与 残基之间的相对位置关系。这种表示方法的优点是操作简单，缺点是模型只能 大体反映蛋白质的折叠趋势，解析度太低，与天然蛋白质结构差别较大。 2 以蛋白质骨架为基本单位，即包括骨架上的c a 、n 、o 和c 原子，而不考虑侧 链上的原子，或者将整个侧链简化为一个原子。由于骨架上原子之间的键长和 健角基本上是保持不变的，所以在键长、健角理想化( i d e a l i z e ) 之后，它们的相 对位置可以用三个扭转角度来表示，它们分别是：c n c 。所在平面与n c n c 所在平面构成的二面角，常用表示；n c 。一c 所在平面与c 。c n 所在的平面 构成的二面角，常用妒表示；c q c n 所在平面与c n c 。所在的平面构成的 9 章蛋白质结构预测概述 并行蚁群优化在蛋白质结构预测中的应用研究 二面角，常用u 表示。其中，u 扭转角稍有特殊，原因是c 口c n - c a 位于一个 平面上，这个平面称为酰平面。理论上u 只有两个取值，即1 8 0 度和1 8 0 度。 实际上这个角度会有轻微的偏转，因此有的方法考虑u 角，有的方法则将这个 角度作为默认值。如图2 6 所示【2 5 】。有文献指出将原子之间的相对位置关系用 笛卡尔坐标( c a r t e s i a nc o o r d i n a t e s ) 来表示，无论是用哪种方法表示只要适应 能量函数的表示方法皆可。这种表示方法最大的好处就是将一个复杂的系统仅 用一连串的扭转角度就可以表示，不仅有效的拟合天然蛋白质结构，还可以减 少计算量，并成为蛋白质全原子模型细化的基础。这种表示方法应用极为广泛， 不仅在蛋白质结构预测上，还应用在蛋白质的基础研究领域，如拉氏图( 又称 r a m a c h a n d r a n 图) 。 图2 6 ：蛋白质骨架原子及扭转角度 3 全原子的表示方法。该方法是在上述表示方法的基础上加入对侧链的考虑。为 了对侧链表示方便，同样是利用扭转角度来表示。氨基酸在侧链上的碳原子的 命名方法是，从侧链上直接连接c 口的碳原子开始，依次称为c 口、c 1 等等，如 图2 1 所示。类似于骨架上的扭转角度，这里依次将扭转角度命名为x 1 、x 2 等 等，如图2 7 所示。由于蛋白质的主要差别体现在侧链上，所以氨基酸之间的侧 链差别较大。比如有些氨基酸的侧链没有x 1 ，而有些氨基酸的侧链则有x 1 和 x 2 。全原子表示法基本等同于天然结构，所以最为实用。然而由于加入侧链使 得计算量剧增，通常的做法是在蛋白质骨架预测出来以后，再做全原子细化( r e f i n e m e n t ) 。 2 3经典的蛋白质结构预测方法 由于蛋白质结构预测意义重大，近些年来以成为研究热点之一，形成了一些经典 的蛋白质结构预测方法。 1 0 并行蚁群优化在蛋白质结构预测中的应用研究 第二章蛋白质结构预测概述 2 3 1h p 模型 图2 7 ：蛋白质侧链原子及扭转角度 d i l l 等人在1 9 8 5 年提出了h p 晶格模型f 2 6 1 ，得到了广泛的认可。它是一种相 当简单的模型，即把残基作为基本单位。h p 晶格模型可描述为：构成蛋白质的氨 基酸可分成两类：一类是疏水氨基酸( h y d r o p h o b i c ，简称h ) ，另外一类是亲水氨基 酸( p o l a r ，简称p ) 。因此氨基酸序列可以用含有h 和p 的字符串来表示。通常为了 方便描述，将h 表示为黑球，p 表示为白球，如图2 8 所示。它的生化意义是蛋白质 构象生成的主要驱动力是残基与溶液的相互作用，也就是说疏水性残基尽量挤在蛋 白质构象的中心，而亲水性残基则是环绕在构象的外围，这样的结构认为是稳定的 结构，能量函数正体现了这一点。所谓晶格，就是残基之间的键长都为单位长，并 且相邻残基之间的角度只能是直角或平角。该问题的数学描述为：给定蛋白质序列 s = s 1 ，s 2 ，s 日，p ，找到一个结构矿，使得e ( c + ) = m i n e ( c ) lc c ( s ) ) ，其中 c ( s 1 是序列s 的所有可行构象的集合。 构象能量函数e 定义为： 玎。廿南f 一1 ，i ，歹均为日且距离为1 ； e = 一a q , i 其中2ij蚓州暑茹_同刖qj=1i j 1 ， 一 k 。 “j ； 习 j 】 气 一- f t l 。_ i 一。u 甲 - l _l - - lr k 一一 - - 1 i i li 龟 l _bc飞rb 小 图2 8 ：h p 模型构象图 1 1 ( 2 1 ) 其中距离记作键角函数，如下所示： j - 1 k j 一1 k = “1 + c 。s 0 1 2 + s i n 巩】2 p k = i + 11 = i + 1k = i + ll = t + 1 是一个关于吼的简单三角函数，如下所示： 呻t ) = 三( 1 - c o s o i ) 其 相 模 残 ( 2 3 ) ( 2 4 ) 并行蚁群优化在蛋白质结构预测中的应用研究 第二章蛋白质结构预测概述 图2 9 ：t o y 模型构象图 2 3 3i - t a s s e r 方法 z h a n g - s e r v e r 组的i - t a s s e r 在2 0 0 4 、2 0 0 6 年举办的c a s p 7 、c a s p 8 服务器类 别的比赛中综合第一名。这种方法在非f m 类别中表现的更为突出，所以是当前蛋白 质结构预测领域中最优秀的方法之一。 i - t a s s e r 方法f 2 2 ，2 3 1 是t a s s e r 方法【