基于网格的蛋白质结构预测的并行实现

【作者】 李春丽；

【导师】 朱红兵；

【作者基本信息】 武汉科技大学 ， 计算机系统结构， 2012， 硕士

【摘要】 蛋白质折叠结构预测问题是当前生物学研究的一个热点。由于其特殊的结构和所使用的模型限制，利用NP问题的求解来求其最小能量值从而推测出折叠结构是这个问题的研究方向之一。许多算法用来解决这个问题，然而由于复杂的计算导致的时间的消耗代价昂贵。遗传退火算法（GAA）是遗传算法和模拟退火算法的结合，同时具备了遗传算法全局搜索能力强和退火算法局部收敛快的优势，因此成为蛋白质折叠结构预测问题常用算法。网格计算是一种分布式并行计算，它致力于利用网络上的闲置资源来解决大规模计算问题。网格并行系统的设计以网格中间件为基础，具备管理性强、安全性高、数据传输方便和扩展性好的特点，从计算的效率、设备的代价来看，适合大规模计算问题的普遍研究。基于MPI的网格编程接口是实现网格并行计算的一种应用。本文利用遗传退火算法来解决蛋白质折叠结构预测问题，将串行算法移植到并行的网格平台中。在并行算法中，种群被分为多个子种群分布到子节点中各自进行演化操作。同时根据实际情况对算法的算子（选择、交叉、变异）进行改进，以求得更好的计算速度和算法效率。更多还原

【Abstract】 Protein structure prediction (PSP) is a hot research topic in current biology. By limits of itsspecial structure and its model, using non-deterministic polynomial (NP) problem to getminimum energy value, which infer to folding structure, is one of the research direction withthis problem. There are many algorithms with this problem, but all of them have long timeconsumption because of the complexity of the calculations. Genetic annealing algorithm (GAA)combining with simulated annealing algorithm and genetic algorithm, which combining withthe advantages of global searching ability of genetic algorithm and local convergence ofannealing algorithm, is a common algorithm for PSP.Grid computing is a kind of distributed parallel computing, it is committed to us ing theidle resources on the network to solve large-scale computing problems. The design of gridsystem based on the grid middleware, which have characteristics of strong management,highsafety, convenient transfer of data and good scalability, is suitable for large-scale computationalproblems in general studies consider to a computational efficiency, equipment cost. Gridprogramming interface based on MPI is an application of the grid computing.This paper aims to solve the problem of PSP with GAA, transplant the serial algorithm toparallel grid platform. In the parallel algorithm, the population is divided into many sub-populations and these sub-populations are distributed to child nodes to do evolutionaryoperation respectively. At the same time we improve the algorithm operator (selection,crossover, mutation) according to the actual situation in order to achieve better computationalspeed and the efficiency of the algorithm.更多还原