基于智能计算的DNA序列比对研究

作     者：陈金灿 

作者单位：山东师范大学 

学位级别：硕士

导师姓名：向来生

授予年度：2012年

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 

主      题：DNA多序列比对 粒子群算法 遗传算法 模拟退火算法 

摘      要：生物信息学是一门综合了数学、信息、生物、计算机等多门学科的新兴学科，它的研究焦点是使用计算机数据库和计算机算法来分析基因和蛋白质序列中所表达的结构和功能的生物信息，期望运用计算机程序来揭示生物分子的结构和功能、疾病的遗传和发生以及进化相关的生物学问题的基本规律。序列比对可以发现生物序列之间存在的结构、功能和进化的关系，它是一种最核心的生物数据处理方法，目前对序列比对的研究已经越来越深入，应用也越来越广泛。 本文主要介绍了生物信息学的基本知识、DNA序列比对问题的基本原理和意义、粒子群算法、遗传算法和模拟退火算法的基本思想。首先介绍了DNA序列比对问题的基本原理，包括基本概念、计分矩阵、空位罚分和目标函数，并对DNA序列比对问题进行了完整的数学描述，然后介绍了序列比对的发展现状，对于双序列比对算法，包括点阵法、Needleman- Wunsch算法、FASTA算法等，对于多序列比对算法，包括精确比对算法、迭代比对算法、启发式算法等。本文针对多序列比对问题，对粒子群算法进行改进，并通过实验证明了该算法的可行性，同时，将模拟退火算法引入到遗传算法的过程中，并将该算法应用在多序列比对中，最后通过实验证明了该算法在计算速度和所得结果的准确率方面都有了显著的提高。 本文在第三章中，首先研究了粒子群算法的算法思想、算法模型和特点，并对算法中的主要运行参数进行了描述，然后针对粒子群算法容易陷入局部极值的缺点，对粒子群算法进行了改进。在改进粒子群算法的基础上设计了与此对应的DNA多序列比对算法PSO-MSA，详细描述了各个参数的具体实现和算法流程。最后，通过实验证实了这种算法的可行性。 本文在第四章中，首先分别研究了遗传算法和模拟退火算法的算法思想、算法流程和优缺点，然后提出针对遗传算法局部搜索能力较差和“早熟的缺陷，对遗传算法和模拟退火算法进行结合的思想，设计了在选择、交叉、变异的过程中利用模拟退火算法的Metropolis准则来接受新解的DNA多序列比对算法，从而使算法的搜索效率大大提高。本章在最后对提出的算法进行了几组仿真实验并分析了产生实验结果的原因。