【作者】 何莲莲；

【导师】 石峰；

【作者基本信息】 武汉大学 ， 计算数学， 2005， 硕士

【摘要】 从蛋白质的氨基酸序列预测其结构是现代计算生物学中最重要的问题之一,该问题的难点主要是计算量非常大。解决问题的办法有两种:一是用新颖的搜索方法,如遗传算法,模拟退火算法等;另外一种是对蛋白质结构做出合理的假设,如简化模型。 论文主要研究两种典型的群体智能算法——蚁群算法和微粒群算法——在蛋白质结构的两种简化模型预测方面的应用。在格模型方面,提出了一种改进的蚁群算法;在非格模型方面,首次用微粒群算法进行了预测。 全文分四章。作为基础,第一、二章介绍了该课题研究的意义及现有研究成果,阐述了该课题研究的基础知识,包括氨基酸分类、蛋白质的分子结构、格模型及非格模型的原理及实现。第三、四章是本文的主要工作,分为两个部分:第一部分针对格模型提出了一种改进的蚁群算法,在算法的搜索阶段采用了牵引移动的方法。改进后的算法具有较快的收敛速度,对于长度大于50的序列,得到相同的解原算法最少要2个小时,最多则要十几个小时;而改进后的算法最多只要三十几分钟。文中详细描述了该算法,并给出了数值实验结果。第二部分介绍了微粒群算法,并首次用于非格模型结构预测,给出的数值实验结果表明微粒群算法是一种有效的搜索方法,并且一定程度上非格模型能够近似真实蛋白质。更多还原

【Abstract】 The prediction of a protein’s structure from its amino-acid sequence is one of the most important problems in modern computational biology. Main problem in computational methods is the huge computational task. There are two kinds of efforts having been done to solve the problem: one is using novel searching methods, such as Genetic algorithm, Simulated Annealing Algorithm etc; the other is to make reasonable simplification of protein structure, such as simplification model.This paper applies two typical swarm intelligence algorithms, Ant Colony Optimization (ACO) Algorithm and Particle Swarm Optimization (PSO) Algorithm, to the protein structure prediction in two kinds of simple exact model. We present an improved ACO to solve lattice model, and introduce PSO for off-lattice model.The paper consists of four chapters. As the basic part, Charter 1 and Charter 2 introduce the importance of the research, the current works, the basic knowledge for this research, including the amino acid classification, protein molecular structure, the lattice model and off-lattice model. Chapter 3 and Chapter 4 is our primary work, and it includes two parts: In part one, an improved ACO is proposed for lattice model, we modified the local search mechanism by using pull moves. It can quicken the convergence rate, and the experiments show that our algorithm can observably decrease computing time with the same result of previous ACO algorithm. In part two, we introduce PSO for off-lattice model and demonstrate its ability to solve artificial data and real protein data. To our best knowledge, this is the first application of PSO to the highly relevant problem from bioinformatics. The results indicate PSO is really a good searching method and off-lattice model can simulate real protein to some extent, but it still need further improvement.更多还原