基于多个k值的DNA序列不对齐比对方法的研究

论文摘要

随着下一代基因测序技术的发展,生物学领域产生了大量的数据,对这些生物数据的处理是一个急需解决的问题,同时也是计算机,数学等其他多个领域面临的一个重大挑战,生物信息学在这个背景下产生了。DNA序列之间的比对是生物信息学研究问题之一,并在很多方面有着重要的应用。序列比对旨在发现两条DNA序列之间的相似程度,进而揭示对应物种之间的联系。过去50年里,大量的序列比对方法被提出,目前主要的序列比对方法包括两大类:对齐的方法和不对齐的方法。对齐的方法,往往需要庞大的时间开销,对于两条序列的长度也有一定的要求,无法处理大规模的数据,在当前数据爆炸的环境下已经不适用。不对齐的方法通常是通过从序列中提取长度为k的短序列片段,并统计序列片段的一些统计特征来定义序列相似度。不对齐方法虽然能够快速的得到序列比对结果,但是也面临着两个急需解决的问题:因为这一类方法依赖参数k来提取序列特征,不同的k对于算法的性能影响很大,确定最优的k值往往需要进行大量的实验进行尝试,这给实际应用带来了困难;此外,这一类方法在解决相关问题的准确度上仍然需要进一步提高。本文为解决不对齐比对方法的两个问题,提出综合多个k值的思想。本文使用了两种加权方法用于区分不同k值提取特征的重要性,提高不对齐方法的精度;另外,本文也引入机器学习方法到序列比对领域,处理序列比对相关问题。基于综合多个k值的思想,本文首先对传统的不对齐的D2类型方法上进行了改进,应用了两种不同的加权方案:最大离差法和遗传算法,对序列特征进行加权处理,提出了两种增强的不对齐比对方法。本文设计并实现了两个序列比对任务,实验结果表明,我们提出的方法在没有额外增加时间复杂度的情况下能高效准确地处理大规模的生物DNA序列,并且相较于以前的不对齐方法,我们的方法所获得实验准确率更高。此外,本文也提出一种用于序列比对的机器学习模型,仍然使用多个k值提取序列特征,对特征进行编码后,采用卷积神经网络对序列比对任务进行处理,相关实验结果表明,相较于以前的不对齐方法,使用卷积神经网络的比对模型准确率更高。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 生物信息学
•   1.2 序列比对研究的意义
•   1.3 序列比对的研究现状
•   1.4 论文主要工作
•   1.5 本文的主要贡献
•   1.6 本文的组织结构
• 第二章 生物DNA序列比对概述
•   2.1 DNA序列比对问题
•   2.2 基于对齐的DNA序列比对算法
•   2.3 不对齐的DNA序列比对算法
•   2.4 本章小结
• 第三章 基于最大离差法的多个K值的DNA序列比对
•   3.1 DNA序列中的MARKOV链模型
• 类型的统计度量'>  3.2 D2_类型的统计度量
•   3.3 权重计算方法
•   3.4 最大离差法加权
•   3.5 数据标准化方法
•   3.6 基于最大离差法的多个K值的序列比对方法
•   3.7 时间复杂度
•   3.8 实验与结果分析
•   3.9 本章小节
• 第四章 涉及遗传算法的综合多个K值的不对齐序列比对
•   4.1 遗传算法（GENETIC ALGORITHM,GA）
•   4.2 涉及遗传算法的综合多个K值的不对齐序列比对
•   4.3 时间复杂度分析
•   4.4 实验与结果分析
•   4.5 本章小结
• 第五章 基于CNN的 CRMS序列识别模型
•   5.1 常用的机器学习算法
•   5.2 神经网络
•   5.3 卷积神经网络
•   5.4 神经网络中的一些问题
•   5.5 基于CNN的 CRMS序列识别模型
•   5.6 实验与结果分析
•   5.7 本章小结
• 第六章 总结和展望
•   6.1 总结
•   6.2 展望
• 参考文献
• 致谢
• 附录 攻读学位期间发表的学术论文

文章来源

类型: 硕士论文

作者: 张雨

导师: 钱莹

关键词: 序列比对,最大离差,遗传算法,卷积神经网络

来源: 华东师范大学

年度: 2019

分类: 基础科学,信息科技

专业: 生物学,自动化技术

单位: 华东师范大学

分类号: TP18;Q811.4

总页数: 84

文件大小: 1738K

下载量: 53