节点文献
模拟退火遗传算法在生物多序列比对中的应用研究
Application Research on Biology Multiple Sequence Alignment Based on Genetic Simulated Annealing Algorithm
【作者】 向昌盛；
【导师】 周建军；
【作者基本信息】 湖南农业大学 ， 生物物理学， 2008， 硕士
【摘要】 序列比对是生物信息学中一项重要的基础性研究课题,最基本任务之一是进行多序列比对,目前还没有一个通用且最佳的多序列比对算法。本文提出使用遗传算法和模拟退火算法相结合来解决多序列比对问题,并对此进行了深入研究和探讨,主要研究结果如下:1、在分析传统遗传算法(Genetic Algorithm)、模拟退火算法(Simulated AnnealingAlgorithm)的优缺点基础上,将模拟退火算法引入遗传算法的选择策略和生存策略,通过模拟退火算法来减轻遗传算法的选择压力,利用模拟退火算法的BoltZman控制来接收交叉和变异后的个体,构建了一种模拟退火遗传算法。2、将模拟退火遗传算法应用到多序列比对问题中,提出了多序列比对的模拟退火遗传算法(MSA-GASA),建立了数学模型,利用MSA-GASA对BAliBASE数据库中的数据集进行了测试,对测试的试验结果和ClustalX的结果进行比较分析,结果表明,MSA-GASA比ClustalX的比对结果准确度更高,具有更好的敏感性,和传统遗传算法相比,MSA-GASA的收敛性相应加快,时间复杂度相对较小,总之MSA-GASA改善了多序列比对的质量,提高了算法的稳定性。
【Abstract】 Sequence alignment of bioinformatics is an important fundament subject in bioinformatics research, one of its most basic task is multiple sequence alignments. Still there is not an optimal algorithm for multiple sequence alignments. This paper had proposeds a method, which use genetic algorithm and simulated annealing algorithm to solve the problems of multiple sequence alignments, The main work was summarized as follows:Firstly, we had analyzed of the traditional genetic algorithm and simulated annealing algorithm, exposed their the potential strengths and weaknesses. The simulated annealing algorithm was imported into the culling strategy and the subsistence strategy of genetic algorithm. By using simulated annealing algorithm into mitigate the stress of culling genetic algorithm and utilizing the Boltzmann mechanism of simulated annealing algorithm to control the acceptance of the individuals generated by crossovered and varied, a genetic stimulated annealing algorithm is proposed.Secondly, we had built up corresponding mathematical model and designed and developed a multiple sequence analysis procedures based on improved adaptive genetic algorithm. Then we had applied Genetic Simulated Annealing Algorithm to more specific nucleic acid and protein multiple sequences, to the experimental data, compared with the traditional genetic algorithm and ClustalX algorithm to achieve the sequence of procedures, it showed new algorithm had faster quality and stability of multiple sequence alignment, the results proved the feasibility and validity of the simulated annealing and genetic algorithm.