基于格点和关联图模型的蛋白质结构预测与比对算法研究

摘要

后基因组时代研究的核心内容之一就是阐明蛋白质的功能，因为蛋白质是生理功能的执行者以及生命现象的体现者。研究表明，蛋白质的生物功能由蛋白质的结构所决定，因此在研究蛋白质时需要了解蛋白质的空间结构。然而，受到蛋白质结构和功能获取实验技术的限制，已知序列的蛋白质远远多于已知结构和功能的蛋白质。因此理论预测蛋白质结构与功能的方法不断涌现。本文从优化算法设计角度出发，研究了基于格点模型的蛋白质结构预测问题，基于蛋白质关联图的结构预测和结构比对问题。主要工作如下：
　　 基于优化理论的思想，分别建立了二维(2D)和三维(3D)疏水，亲水(HP)格点模型。对于2DHP模型，提出了一种GA-EO混合算法求解蛋白质结构预测问题。算法以遗传算法(Genetic Alagorithm)为框架，极值优化(Extremal Optimization)作为变异算法。对于3DHP模型，提出了一种EO-PERM混合算法求解蛋白质结构预测问题。算法以极值优化(EO)为框架，增长型算法PERM(pruned-enriched Rosenbluth method)为邻域搜索策略。在极值优化算法中，分别给出了适合2DHP和3DHP模型的局部适应度定义。测试的结果表明：在一定规模下，混合算法可以找到测试序列在格点上的最低能量状态。
　　 引入了一种改进的COMAR算法来求解基于关联图的蛋白质结构预测问题。算法首先根据蛋白质关联图和先验知识以半随机的方式生成距离信息，然后根据距离信息得到蛋白质的坐标表示，最后通过坐标修正和摄动使得重构结构的关联图与给定的关联图相一致。结果表明阈值较大的关联图重建的结构比阈值小的要好。此外，改进COMAR算法与原COMAR算法在相同的达代次数下，算法的精度有所提高。基于序列比对中的相似度矩阵，提出了一种蛋白质关联图的相似度矩阵表示，并用Greedy-EO混合算法求解基于关联图的蛋白质结构比对问题(关联图重叠问题CMO)。算法首先基于关联图相似度矩阵，应用贪婪算法得到问题的初始解，然后采用极值优化算法得到问题的近优解。相似度矩阵由蛋白质残基特征的相似度组成，它是产生初始解的重要依据，也是极值优化算法中邻域搜索的准则。一共采用了五种策略定义相似度矩阵。与多项式时间近似算法PTAS方法比较，算法速度快，解的质量也有所提高。与分支缩减算法比较，所得的相似性指标互有高低。受TOPS模型的启发，提出了蛋白质关联图的等价向量表示，并用Hungarian-EO混合算法求解CMO问题。算法首先引入向量集合来等价表示蛋白质关联图，然后计算关联图的相似度矩阵，接着构造基于相似度矩阵的带约束的分派问题，作为CMO问题的初始解，最后采用极值优化算法获得最终解。与Greedy-EO算法的比较结果表明，Hungarian-EO有效提高了解的质量。与DALI的结果比较表明，某些例子混合算法所得的解有所提高，某些例子混合算法所得的解不及DALI。此外，通过绘制蛋白质相似网络来测试混合算法的蛋白质分类效果，选择一定的阈值，蛋白质相似网络可以分为5个子网络对应于5个家族。