面向DNA/RNA大数据的序列比对算法
发布时间：2022-08-13 09:02
随着新一代测序技术的发展,DNA/RNA测序数据已经成为遗传学、生物信息、细胞生物学、系统生物学中最丰富的数据。DNA/RNA测序已经成为研究生命科学的基本手段,然而如何有效利用这些测序数据是一个很大的课题。本文主要研究面向DNA/RNA大数据的序列比对。序列比对领域已有一些广为人知算法,譬如在序列数据库中搜索的BLAST算法,或是用于成对比对的Smith-Waterman算法。但这些标准的算法未必适用于新的测序数据。譬如Smith-Waterman算法受制于内存的限制,无法用于超长序列之间的比对;同时Smith-Waterman算法也无法展示一对序列之间多个匹配段之间的协同关系。为此,本论文研究了如下两方面内容:（1）超长序列之间的比对问题。本文提出了 PAAVLS算法来解决Smith-Waterman算法面临的内存不足问题。PAAVLS算法提出了矩阵骨架的概念,减少了需要保存的信息,降低了对内存的需求,可适用于超长序列之间的比对。（2）包含超长gap的序列比对问题。本文提出了SLGAA算法来研究序列之间的复杂关系。传统的Smith-Waterman算法不能容忍较长的gap,因此只能...
【文章页数】：57 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
第一章 绪论
1.1 背景
1.2 生物序列及序列比对基本知识
1.2.1 生物序列
1.2.2 序列比对
1.2.3 序列比对分类
1.3 测序技术革新产生DNA/RNA大数据
1.4 序列比对的重要性
1.5 本文的结构
第二章 相关知识
2.1 字符串比对的动态规划算法
2.1.1 动态规划算法思想
2.1.2 动态规划算法
2.2 BLAST算法
2.2.1 BLAST软件包介绍
2.2.2 BLAST算法思想
2.3 Needleman-Wunsch算法
2.3.1 Needleman-Wunsch算法思想
2.4 Simith-Waterman算法
2.5 相关算法分析讨论
2.5.1 相关比对算法的特点分析
2.5.2 比对中现存的其它问题
第三章 面向超长序列的比对算法
3.1 超长序列比对问题的背景
3.1.1 序列比对中存在的问题
3.1.2 PAAVLS算法的提出
3.2 超长序列的比对算法
3.2.1 算法思路
3.2.2 算法流程
3.3 回溯函数Trace(Hxy,x,y)
3.3.1 基本思路
3.3.2 算法流程和伪代码
3.4 实验与结果分析
3.4.1 PAAVLS算法实验结果分析
3.4.2 PAAVLS算法的时间复杂度分析
第四章 针对超长Gap的序列比对算法
4.1 序列比对中的超长gap
4.1.1 问题背景
4.1.2 SLGAA算法的提出
4.2 超长gap序列比对算法
4.2.1 基本思路
4.2.2 算法伪代码
4.3 实验与结果分析
4.3.1 SLGAA算法的实验设置
4.3.2 比对中没有超长gap的结果分析
4.3.3 比对中存在超长gap的结果分析
4.3.4 算法的时间复杂度分析
第五章 总结
5.1 主要工作与创新点
5.2 展望
参考文献
发表论文和参加科研情况说明
致谢
【参考文献】：
期刊论文
[1]生物信息学序列比对算法分析[J]. 黄佳琪. 生物技术世界. 2015(11)
[2]字符串匹配算法在DNA序列比对中的应用[J]. 陈建平. 数学建模及其应用. 2015(03)
[3]生物信息学中序列比对技术和算法研究进展[J]. 李美满. 现代计算机(专业版). 2012(26)
[4]基于动态规划的序列比对的并行算法研究[J]. 李大卫. 井冈山大学学报(自然科学版). 2011(03)
[5]生物序列比对算法的研究现状[J]. 杨洁,刘海. 中国科技信息. 2011(09)
[6]多序列比对算法的研究进展[J]. 邹权,郭茂祖,韩英鹏,李文滨. 生物信息学. 2010(04)
[7]生物序列比对算法的研究现状[J]. 文凤春,王邦菊,肖枝洪. 生物信息学. 2010(01)
[8]DNA序列比对数目的算法研究[J]. 徐琛梅,刘晓杰. 大学数学. 2008(01)
[9]生物信息学中的序列比对算法[J]. 张永,王瑞. 电脑知识与技术. 2008(01)
[10]生物信息学中的双序列比对算法[J]. 刘超,马志强,刘帅. 长春工程学院学报(自然科学版). 2006(03)
本文编号：3676735
【文章页数】：57 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
第一章 绪论
1.1 背景
1.2 生物序列及序列比对基本知识
1.2.1 生物序列
1.2.2 序列比对
1.2.3 序列比对分类
1.3 测序技术革新产生DNA/RNA大数据
1.4 序列比对的重要性
1.5 本文的结构
第二章 相关知识
2.1 字符串比对的动态规划算法
2.1.1 动态规划算法思想
2.1.2 动态规划算法
2.2 BLAST算法
2.2.1 BLAST软件包介绍
2.2.2 BLAST算法思想
2.3 Needleman-Wunsch算法
2.3.1 Needleman-Wunsch算法思想
2.4 Simith-Waterman算法
2.5 相关算法分析讨论
2.5.1 相关比对算法的特点分析
2.5.2 比对中现存的其它问题
第三章 面向超长序列的比对算法
3.1 超长序列比对问题的背景
3.1.1 序列比对中存在的问题
3.1.2 PAAVLS算法的提出
3.2 超长序列的比对算法
3.2.1 算法思路
3.2.2 算法流程
3.3 回溯函数Trace(Hxy,x,y)
3.3.1 基本思路
3.3.2 算法流程和伪代码
3.4 实验与结果分析
3.4.1 PAAVLS算法实验结果分析
3.4.2 PAAVLS算法的时间复杂度分析
第四章 针对超长Gap的序列比对算法
4.1 序列比对中的超长gap
4.1.1 问题背景
4.1.2 SLGAA算法的提出
4.2 超长gap序列比对算法
4.2.1 基本思路
4.2.2 算法伪代码
4.3 实验与结果分析
4.3.1 SLGAA算法的实验设置
4.3.2 比对中没有超长gap的结果分析
4.3.3 比对中存在超长gap的结果分析
4.3.4 算法的时间复杂度分析
第五章 总结
5.1 主要工作与创新点
5.2 展望
参考文献
发表论文和参加科研情况说明
致谢
【参考文献】：
期刊论文
[1]生物信息学序列比对算法分析[J]. 黄佳琪. 生物技术世界. 2015(11)
[2]字符串匹配算法在DNA序列比对中的应用[J]. 陈建平. 数学建模及其应用. 2015(03)
[3]生物信息学中序列比对技术和算法研究进展[J]. 李美满. 现代计算机(专业版). 2012(26)
[4]基于动态规划的序列比对的并行算法研究[J]. 李大卫. 井冈山大学学报(自然科学版). 2011(03)
[5]生物序列比对算法的研究现状[J]. 杨洁,刘海. 中国科技信息. 2011(09)
[6]多序列比对算法的研究进展[J]. 邹权,郭茂祖,韩英鹏,李文滨. 生物信息学. 2010(04)
[7]生物序列比对算法的研究现状[J]. 文凤春,王邦菊,肖枝洪. 生物信息学. 2010(01)
[8]DNA序列比对数目的算法研究[J]. 徐琛梅,刘晓杰. 大学数学. 2008(01)
[9]生物信息学中的序列比对算法[J]. 张永,王瑞. 电脑知识与技术. 2008(01)
[10]生物信息学中的双序列比对算法[J]. 刘超,马志强,刘帅. 长春工程学院学报(自然科学版). 2006(03)
本文编号：3676735
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3676735.html
