面向三代测序的序列比对算法研究与优化

论文摘要

近年来,三代测序技术的发展为基因组学带来了重大变革和影响。但由于三代测序序列具有平均长度长、错误率高的特性,现有的三代测序序列比对算法在数据分析的工作流中占据了大量的时间。因此,如何快速、准确地将大规模的测序序列比对到参考基因组上是三代测序序列比对面临的一大挑战。目前主流算法大多采用种子扩展（seed-and-extend）方法,包括过滤出候选位置和进行比对验证两个阶段。过滤和验证是影响算法性能的关键环节,为了加快序列比对的速度,本文对过滤方法的特征选取和验证阶段的索引技术进行了较为深入的研究,主要工作和贡献如下:（1）过滤方法设计及优化对已有过滤方法进行分析,它们使用全部种子来过滤候选位置,如此要处理的种子数很多且针对性不强,导致过滤时间过长。我们的实验表明过滤时低频率的种子往往具有更高的区分度,同时低频种子也可以有效地减少计算量。基于此,本文提出了一种基于低频种子的过滤方法,根据基因组的规模动态地选取低频率的种子,使用低频种子进行投票定位候选区域。过滤得到的候选区域数目也是过滤方法的重要衡量标准。为了进一步减少候选区域的数目,我们对过滤方法进行了优化,提出了相邻窗口合并、候选窗口验证判断、变换种子区域三个启发式策略,在保证敏感度的前提下对候选位置进行再过滤。实验结果表明,当种子频率范围设置为20%时,本文提出的过滤方法可以大幅减少过滤阶段的时间消耗,比现有过滤方法快10倍左右。同时,优化后的过滤方法可以减少约70%的候选位置。（2）索引改造及验证方法改进验证阶段需要对候选区域进行扩展验证以获得最终的比对结果,现有方法通常借助索引构建最优覆盖链来减少比对的范围。但由于三代测序序列长度较长,使用全局索引时,串链阶段需要处理大量错位的无效锚点。针对这个问题,本文设计了一种分段哈希索引,并提出了基于分段哈希索引的验证方法,分别对索引和候选区域进行分段划分,利用位置关系的限制减少无效锚点的数目,加速串链过程,进而减少验证阶段的时间消耗。实验结果表明,改进后的验证方法可将验证时间提升30%以上;将本文提出的过滤方法与验证方法相结合,在拟南芥基因组和人类基因组上进行序列比对的全过程实验,与现有的三代测序序列比对算法进行了比较,整体速度提升了2-5倍。

论文目录

文章来源

类型: 硕士论文

作者: 宋思怡

导师: 徐云

关键词: 三代测序,序列比对,种子扩展法,低频种子,索引

来源: 中国科学技术大学

年度: 2019

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

专业: 生物学,计算机软件及计算机应用

单位: 中国科学技术大学

分类号: Q811.4;TP391.41

总页数: 77

文件大小: 4939K

下载量: 195

相关论文文献

• [1].双序列比对算法的研究与改进[J]. 电子技术与软件工程 2017(18)
• [2].基于蚁群算法的双序列比对及其实现[J]. 电子技术与软件工程 2018(01)
• [3].基于局部序列比对的漏洞挖掘技术研究[J]. 微型机与应用 2017(03)
• [4].基于布尔逻辑的双序列比对协处理器的设计与实现[J]. 西北工业大学学报 2011(01)
• [5].生物信息学中的序列比对算法[J]. 电脑知识与技术 2008(01)
• [6].参数序列比对算法研究(英文)[J]. 生物信息学 2008(02)
• [7].生物序列比对算法的研究现状[J]. 中国科技信息 2011(09)
• [8].蛋白质序列比对算法在众核结构上的并行优化[J]. 软件学报 2010(12)
• [9].基于混合行为的蚁群双序列比对方法[J]. 计算机工程与应用 2009(11)
• [10].双序列比对的算法研究[J]. 计算机工程与应用 2008(36)
• [11].BLAST序列比对脱机移植研究[J]. 内蒙古师范大学学报(自然科学汉文版) 2020(04)
• [12].基于动态规划的基因双序列比对研究[J]. 现代计算机(专业版) 2017(32)
• [13].多重序列比对的模型与算法[J]. 才智 2010(14)
• [14].异构机群系统中序列比对并行算法进展[J]. 福建电脑 2019(04)
• [15].四种常用的生物序列比对软件比较[J]. 生物信息学 2016(01)
• [16].两种带约束的序列比对算法[J]. 江南大学学报(自然科学版) 2009(06)
• [17].生物信息学双序列比对算法加速器设计与实现[J]. 计算机科学与探索 2008(05)
• [18].双兔傍地走,安能辨雄雌——双序列比对工具介绍[J]. 高校生物学教学研究(电子版) 2016(01)
• [19].始发保优的序列比对[J]. 小型微型计算机系统 2020(05)
• [20].基于序列比对的勒索病毒同源性分析[J]. 计算机与现代化 2018(02)
• [21].最优搜索机制下寻找最优插入-删除种子[J]. 电子科技大学学报 2011(02)
• [22].启发式序列比对算法种子长度及其灵敏度研究[J]. 计算机技术与发展 2013(02)
• [23].基于区域过滤的测序序列比对算法研究[J]. 信息技术与网络安全 2018(04)
• [24].基于序列比对的行人过街风险识别研究[J]. 交通运输系统工程与信息 2018(03)
• [25].基于大规模序列比对软件的并行优化方案[J]. 计算机工程 2009(03)
• [26].基于动态规划的双序列比对算法构件设计与实现[J]. 计算机研究与发展 2019(09)
• [27].一种基于低频种子的三代测序序列比对方法[J]. 计算机工程与科学 2019(09)
• [28].DNA双序列比对问题的算法[J]. 计算机系统应用 2015(09)
• [29].基于序列比对算法的地质剖面图自动生成[J]. 铁道勘测与设计 2010(05)
• [30].面向OpenCL架构的大规模生物序列比对[J]. 小型微型计算机系统 2012(02)

标签：三代测序论文;  序列比对论文;  种子扩展法论文;  低频种子论文;  索引论文;