双序列比对Needleman-Wunsch算法研究
发布时间：2021-06-08 15:21
伴随着人类基因组计划（HGP）的实施,使得生物学的相关数据迅速增长,但是对于这些大量的数据如何被处理,已成为生物科学家的一个难题。目前,基因序列的比较分析是生物信息处理中的最重要的研究内容之一。Needleman-Wunsch算法是根据动态规划算法的思想进行研究与分析的,它也是研究双序列比对问题的一个最根本的算法。该算法虽然可以获得双序列比对时的最优结果,但是它的时间复杂度和空间复杂度较高,均为O（n*m）（其中n和m分别表示两条序列的长度）。因此难以实现实际的生物序列比对问题。本文主要是以基于动态规划思想的Needleman-Wunsch算法为研究对象,对其进行研究与分析,进而提出该算法的改进方法。然后通过大量的实验对改进前后该算法在实现双序列比较时运行所花费的时间进行比较与分析。实验的结果表明,当两条序列比对的得分和准确率不变的情况下,Needleman-Wunsch的改进算法可以有效地降低原来算法的运行时间。本文主要研究的内容和要完成的工作有以下几点:（1）首先了解了双序列比对问题的研究现状。同时,研究Needleman-Wunsch算法实现两条序列比对的结果,从而分析该算法可能...
【文章来源】：内蒙古农业大学内蒙古自治区
【文章页数】：53 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
1 绪论
1.1 论文研究背景和意义
1.1.1 研究背景
1.1.2 研究意义
1.2 双序列比对算法的国内外研究现状
1.3 论文的研究内容
1.4 论文的组织结构
1.5 本章小结
2 双序列比对问题概况
2.1 双序列比对问题
2.1.1 双序列比对问题的描述
2.1.2 双序列比对问题的数学定义
2.1.3 比对得分矩阵和空位罚分
2.2 基于动态规划的Needleman-Wunsch算法
2.2.1 动态规划思想描述
2.2.2 Needleman-Wunsch算法
2.2.2.1 Needleman-Wunsch算法基本思想
2.2.2.2 Needleman-Wunsch算法实现流程及步骤
2.2.3 Needleman-Wunsch算法的优缺点
2.2.3.1 Needleman-Wunsch算法的优点
2.2.3.2 Needleman-Wunsch算法的缺点
2.3 本章小结
3 Needleman-Wunsch算法的改进算法
3.1 Needleman-Wunsch算法改进思路
3.2 改进后Needleman-Wunsch算法的实现流程及步骤
3.3 本章小结
4 实验与分析
4.1 实验环境
4.2 改进前后Needleman-Wunsch算法的实现代码分析
4.3 改进前后Needleman-Wunsch算法实验与分析
4.3.1 基于动物基因的实验结果分析
4.3.2 基于植物基因的实验结果分析
4.4 实验小结
5 总结与展望
5.1 总结
5.2 展望
致谢
参考文献
作者简介
【参考文献】：
期刊论文
[1]《运筹学》课程教学探索与实践[J]. 王小林. 长江大学学报(自然科学版)理工卷. 2010(03)
[2]序列比对算法的并行化研究与应用[J]. 张福祥,周金玲. 潍坊学院学报. 2008(04)
[3]消息传递模型的并行性能研究[J]. 郭红霞,潘斌. 成都大学学报(自然科学版). 2007(01)
[4]生物信息学中一个优化的全局双序列比对算法[J]. 唐玉荣. 计算机应用. 2004(S1)
[5]两序列比对的Hirschberg算法[J]. 张福祥. 潍坊学院学报. 2003(04)
[6]生物信息学的现状与展望[J]. 张春霆. 世界科技研究与发展. 2000(06)
博士论文
[1]生物信息学中多序列比对等算法的研究[D]. 张敏.大连理工大学 2005
[2]生物信息学中的序列比对算法研究[D]. 唐玉荣.中国农业大学 2004
硕士论文
[1]双序列比对Needleman-Wunsch算法的分布式并行优化研究[D]. 冯百龙.内蒙古农业大学 2015
[2]生物序列比对算法的并行优化设计与实现[D]. 李研.哈尔滨工业大学 2015
[3]生物序列比较算法的研究[D]. 郭晓冬.杭州电子科技大学 2012
[4]双序列比对算法研究与并行优化[D]. 李川.西安电子科技大学 2011
[5]基于平衡分割的并行序列比对[D]. 刘淼.西安电子科技大学 2007
[6]并行遗传算法在生物序列比对中的应用研究[D]. 魏静.天津大学 2004
本文编号：3218740
【文章来源】：内蒙古农业大学内蒙古自治区
【文章页数】：53 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
1 绪论
1.1 论文研究背景和意义
1.1.1 研究背景
1.1.2 研究意义
1.2 双序列比对算法的国内外研究现状
1.3 论文的研究内容
1.4 论文的组织结构
1.5 本章小结
2 双序列比对问题概况
2.1 双序列比对问题
2.1.1 双序列比对问题的描述
2.1.2 双序列比对问题的数学定义
2.1.3 比对得分矩阵和空位罚分
2.2 基于动态规划的Needleman-Wunsch算法
2.2.1 动态规划思想描述
2.2.2 Needleman-Wunsch算法
2.2.2.1 Needleman-Wunsch算法基本思想
2.2.2.2 Needleman-Wunsch算法实现流程及步骤
2.2.3 Needleman-Wunsch算法的优缺点
2.2.3.1 Needleman-Wunsch算法的优点
2.2.3.2 Needleman-Wunsch算法的缺点
2.3 本章小结
3 Needleman-Wunsch算法的改进算法
3.1 Needleman-Wunsch算法改进思路
3.2 改进后Needleman-Wunsch算法的实现流程及步骤
3.3 本章小结
4 实验与分析
4.1 实验环境
4.2 改进前后Needleman-Wunsch算法的实现代码分析
4.3 改进前后Needleman-Wunsch算法实验与分析
4.3.1 基于动物基因的实验结果分析
4.3.2 基于植物基因的实验结果分析
4.4 实验小结
5 总结与展望
5.1 总结
5.2 展望
致谢
参考文献
作者简介
【参考文献】：
期刊论文
[1]《运筹学》课程教学探索与实践[J]. 王小林. 长江大学学报(自然科学版)理工卷. 2010(03)
[2]序列比对算法的并行化研究与应用[J]. 张福祥,周金玲. 潍坊学院学报. 2008(04)
[3]消息传递模型的并行性能研究[J]. 郭红霞,潘斌. 成都大学学报(自然科学版). 2007(01)
[4]生物信息学中一个优化的全局双序列比对算法[J]. 唐玉荣. 计算机应用. 2004(S1)
[5]两序列比对的Hirschberg算法[J]. 张福祥. 潍坊学院学报. 2003(04)
[6]生物信息学的现状与展望[J]. 张春霆. 世界科技研究与发展. 2000(06)
博士论文
[1]生物信息学中多序列比对等算法的研究[D]. 张敏.大连理工大学 2005
[2]生物信息学中的序列比对算法研究[D]. 唐玉荣.中国农业大学 2004
硕士论文
[1]双序列比对Needleman-Wunsch算法的分布式并行优化研究[D]. 冯百龙.内蒙古农业大学 2015
[2]生物序列比对算法的并行优化设计与实现[D]. 李研.哈尔滨工业大学 2015
[3]生物序列比较算法的研究[D]. 郭晓冬.杭州电子科技大学 2012
[4]双序列比对算法研究与并行优化[D]. 李川.西安电子科技大学 2011
[5]基于平衡分割的并行序列比对[D]. 刘淼.西安电子科技大学 2007
[6]并行遗传算法在生物序列比对中的应用研究[D]. 魏静.天津大学 2004
本文编号：3218740
本文链接：https://www.wllwen.com/shoufeilunwen/xixikjs/3218740.html
