基于遗传算法的基因序列比对算法研究

摘要

序列比对是生物信息学中一个重要和活跃的研究领域，是生物信息学研究的基础内容。DNA是生物体中一种遗传物质，它作为一种媒介，将遗传信息从上一代遗传到下一代。所有的生物（除了极少数病毒）都是通过它们的DNA从共同的祖先进化而来，因此，生物体DNA测序是生物信息学中最重要和最基本的要求之一。然而，现在是由高通量测序机器进行DNA测序，每天产生数十亿的测序碱基数据。新一代测序技术的出现，使得测序DNA序列产生了成倍增长，同时降低了几个数量级的测序成本。绝大部分核苷酸数据库有大量实验生成的原始序列数据冗余。结构测定与测序技术相比费时费力，无法与新一代测序方法相适应，导致序列功能测定和结构分析的进度跟不上测序序列的产生速度。因此，研究各种高性能系统分析方法来提高预测核苷酸序列的结构和功能是一个重要的内容。 序列比对是生物信息学了解一个未知序列分子系统的第一步。研究出更高效、更准确的多序列比对算法是目前生物学研究的一个热点、难点、重点问题。其中，许多研究人员经常使用遗传算法，他们在研究中发现遗传算法在求解多序列比对的效率和准确度上有很大的优化空间，并取得了一定程度上的优化。本文在以上背景下进行多序列比对算法研究，希望为以后的研究者提供一点参考思路和研究成果。 本文对DNA序列比对基础知识进行了介绍，然后分别阐述了遗传算法、模拟退火算法、动态规划算法的相关知识。文中重点对遗传算法进行了研究，在标准遗传算法的基础上，对整个遗传算法的架构重新进行了自己的设计。算法放弃了不适合大量数据编码的二进制编码，采用二维染色体编码方式，交叉方式采用单点横向交叉和多点横向交叉两种横向交叉对比方式取最佳的方法，最后对遗传算法产出的解进行模拟退火操作和动态规划操作。通过分析实验数据，对比改进遗传算法和标准遗传算法以及其他算法的多序列比对效率，找到性能最优的算法。

目录

摘要

1．1课题研究目的及意义

1．2国内外研究现状

1．3论文研究的主要内容及创新点

1．4论文的组织结构

第二章生物信息学基础和算法概述

2．1生物信息学基础知识

2．1．1 DNA介绍

2．1．2变异

2．1．3序列比对介绍

2．1．4空位打分

2．1．5核酸打分矩阵

2．2算法介绍

2．2．1模拟退火算法

2．2．2遗传算法

2．2．3动态规划算法

2．3本章小结

第三章基于遗传算法的基因序列比对算法改进

3．1编码和初始化

3．2选择操作

3．3交叉操作

3．4变异操作

3．5模拟退火操作

3．6本章小结

第四章实验结果与分析

4．1实验资料和实验参数

4．2实验结果与分析

4．3本章小结

5．1总结

5．2展望

参考文献

致谢

声明