基于模式匹配的DNA多序列比对及相似性分析

论文摘要

随着人类基因组计划（HumanGenomeProj eot, HGP）的顺利实施和信息技术的迅速发展,大量分子序列数据被人们发掘出来。对这些分子序列数据进行科学有效的分析和处理,让它们为人类疾病的诊断和治疗、疫情的预防、新药的开发等领域发挥更大的作用,已经成为人们愈加重视的研究话题,也是生物信息学的重要研究方向。生物信息学是多门学科相融合的新型的交叉学科。在生物信息学中,如何对基因序列进行有效且快速的比对,基因序列的相似性分析和进化关系分析都是其热门课题之一。本文的主要工作是提出一种新的多序列比对算法——基于模式匹配的DNA多序列比对算法,并在其基础上进行基因序列的相似性分析。具体工作概括如下：多序列比对是生物信息学中的一个基本问题。本文在模式匹配和Aho-Corasick搜索算法的理论基础上,深入分析研究了基于关键字树的DNA多序列比对算法,提出了一种新的多序列比对算法——基于模式匹配的DNA多序列比对算法。对该算法通过三组实验进行分析,并与原星比对算法、基于关键字树的DNA多序列比对算法进行比较。当序列相似度相对较低时,虽然该算法所用时间略长于基于关键字树的DNA多序列比对算法,但比对结果要优于基于关键字树的DNA多序列比对算法。当相似度很高的序列进行比对时,其比对的时间复杂度也优于另两种方法。实验结果表明了该算法的有效性。序列相似性分析也是生物信息学中的基本问题之一,其分析结果可广泛应用于物种分类、结构和功能预测、物种进化分析等领域。本文将模式匹配方法应用于序列相似性分析,使用基于模式匹配的多序列比对结果,采用Kimura双参数模型和Neighbor-joining方法构建进化树。实验结果表明该方法得到了与事实相近的结果。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 研究背景与意义
• 1.2 国内外研究现状及发展趋势
• 1.2.1 多序列比对
• 1.2.2 序列相似性分析
• 1.2.3 进化树构建
• 1.3 本文所做的工作
• 1.4 论文结构
• 第2章 生物信息学相关知识
• 2.1 生物信息学基本概念
• 2.1.1 生物信息学的主要研究内容
• 2.1.2 核酸和蛋白质
• 2.1.3 遗传信息传递与表达
• 2.1.4 变异
• 2.1.5 生物信息学的中心法则
• 2.2 序列比对
• 2.2.1 序列比对概述
• 2.2.2 序列比对算法
• 2.3 分子进化
• 2.3.1 分子进化简介
• 2.3.2 系统进化树
• 2.3.3 构建系统进化树
• 2.4 小结
• 第3章 基于模式匹配的DNA多序列比对算法
• 3.1 模式匹配原理及应用
• 3.1.1 模式匹配概述
• 3.1.2 模式匹配分类
• 3.1.3 模式匹配常用算法
• 3.1.4 模式匹配技术在计算生物学中的应用
• 3.2 基于模式匹配的多序列比对算法引入
• 3.3 算法描述
• 3.4 算法复杂性描述
• 3.5 实验结果对比分析
• 3.5.1 实验结果
• 3.5.2 实验结果分析
• 3.6 小结
• 第4章 基于模式匹配的DNA序列相似性分析
• 4.1 常用的序列相似性分析方法
• 4.1.1 信息理论方法
• 4.1.2 序列比对方法
• 4.1.3 统计特征方法
• 4.1.4 基于图形表示的方法
• 4.1.5 聚类分析方法
• 4.2 利用模式匹配的序列相似性分析方法
• 4.2.1 构建进化树
• 4.2.2 Kimura模型
• 4.2.3 Neighbor-joining方法
• 4.2.4 利用模式匹配的序列相似性分析方法的基本步骤
• 4.3 实验结果分析
• 4.4 小结
• 结论
• 参考文献
• 附录A （攻读硕士期间参加的项目）
• 致谢