蛋白质构象预测算法研究.pdf

国内图书分类号:
国际图书分类号:


工学硕士学位论文

蛋白质构象预测算法的研究








硕士研究生: 曲毅
导师:唐好选副教授
申请学位: 工学硕士
学科、专业: 计算机科学与技术
所在单位: 计算机科学与技术学院
答辩日期: 2007 年 7 月
授予学位单位: 哈尔滨工业大学
Classified Index:
.:


Dissertation for the Master Degree in Engineering

RESEARCH ON ALGORITHMS OF
PROTEIN STRUCTURE PREDICTION








Candidate: Qu Yi
Supervisor: Associate Prof. Tang Haoxuan
Academic Degree Applied for: Master of Engineering
Specialty: Computer Science and Technology
Affiliation: School puter Science and Technology
Date of Defence: July, 2007
Degree-Conferring-Institution: Harbin Institute of Technology
哈尔滨工业大学工学硕士学位论文
摘要
蛋白质的天然构象是由其氨基酸序列确定的,而蛋白质的生物学功能在
很大程度上又依赖于其构象,因此蛋白质构象预测是蛋白质研究中发展已久
但仍具有挑战性的问题,是后基因组时代生命科学中重大的研究课题之一。
研究发现,蛋白质的天然构象形式完全包含在组成其分子的氨基酸序列
的信息之中,这一观点奠定了蛋白质构象预测的理论计算基础。事实上,目
前已有许多基于 HP 模型求解蛋白质构象预测问题的算法,而且取得了一定
的成果,其中最具代表性的有蒙特卡罗算法、遗传算法、近似算法、基于重
要性抽样的 SISPER 算法以及基于裁减复制策略的 PERM 算法等,但从求解
效率来看,此类算法还存在较大的提升空间。本文分别将改进的蚁群优化算
法和模拟退火算法应用于两种蛋白质构象简化 HP 模型的预测问题,使问题
的求解效率得到了进一步提高。
本文采用改进的蚁群优化算法求解基于格点模型的蛋白质构象预测问
题。针对以往算法中存在容易产生非法构象和算法运行时间长的问题,本文
提出用“克隆”的方法处理非法构象;用“单点变异并向前重构”的方法用
于局部搜索阶段来缩短算法运行的时间。通过实验证明,这两点改进在算法
中的应用是正确有效的。
基于非格点模型的蛋白质构象预测问题,可以视为一个连续函数优化问
题,因此本文采用改进的模拟退火算法对其进行求解。针对模拟退火算法的
特点提出了三点改进方法:增加记忆功能,限制接受退化解向量以及邻域的
再次搜索。数值实验结果表明,算法结构简单,达到最优解的效率高,是一
种较好的启发式连续全局优化算法。
从上述两种算法得到的构象模型可以看出,HP 模型虽然简单,但能够
反映出蛋白质折叠构象的一些简单性质,即在蛋白质天然构象中,疏水氨基
酸残基总是被极性氨基酸残基所包围,形成一个疏水核心。由此表明两种改
进算法用于蛋白质构象预测是可行有效的。
最后,本文实现了一个简单的蛋白质折叠构象的图形模拟系统,进一步
验证了论文中给出的两种算法的可行性和有效性。

关键词蛋白质构象预测;格点模型;非格点模型;蚁群优化算法;模拟退
火算法
- I -
哈尔滨工业大学工学硕士学位论文
Abstract
The protein natural structure is decided by its amino-acid sequence, and its
biological functions are dependent on this structure extensively. So prediction of
protein structure is a long historic task, and still a challenge in the research of
protein, which is ing an important research domain in the life science on