高性能生物序列数据处理算法研究与优化

论文摘要

下一代测序技术（也可称为大规模并行测序）允许人们在低成本条件下以惊人的吞吐量累积获得海量核酸序列,并提供更短的读数。吞吐量的大量增加和序列读数的减小产生的代价是短读的准确性显著低于传统的测序手段,同时使短读序列和参考序列的匹配在计算速度和精准度上产生了巨大挑战,导致数据转换为可用信息的计算时间变得更长;另外,海量数据也使计算机有限的内存资源相形见绌。短读序列映射过程中数据规模巨大,而目前已经引入的各类索引技术无法高效的利用有限的内存资源,内存占用率较高。对此本文提出了一个新颖的索引数据结构—精简（稀疏）哈希索引数据结构,应用于短读序列匹配来缓解此问题。该数据结构是经典Q-gram索引的变种,通过参数设置决定内存使用率,如对于人类参考基因组内存占用可减少至经典哈希的1/k。同时,实现了一种高效的并行构造方法。另外,短读序列映射过程的时间占了基因数据分析总时间的相当大一部分。针对下一代测序技术吞吐量大量增加导致的短读序列匹配计算速度减慢和匹配精度降低的问题,本文基于新提出的精简哈希索引结构设计了两个选种算法一分组选种和可变长度选种,用于过滤策略中以减少校验次数,从算法层面来提升计算速度。在此基础上进一步设计了一个快速高效的短读序列完全匹配器—FEM（Fast and Efficient read Mapper）,FEM可以返回在给定编辑距离阈值内短读序列在参考基因组上的所有映射位置。FEM采用了多线程进行数据处理,设计了负载均衡模式以充分利用计算资源,并在算法细节上采用SIMD指令集实现,从体系结构方面进行计算优化。本文实验结果表明FEM是可扩展的,并且在处理速度和内存占用两方面,性能要优于其他目前最前沿的完全匹配器。内存占用方面,精简哈希索引的内存占用率是经典索引的1/k;而处理速度方面,相较于Masai,FEM使用单线程时,要快5倍,而使用多线程能够快两个数量级。还有,FEM 比BitMapper快大约3倍,而和BitMapper2和Hobbes3相比也有快一个数量级的加速比。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
•   1.1 研究背景
•   1.2 国内外研究现状
•   1.3 本文主要工作
•   1.4 本文组织结构
• 第2章 相关工作及问题说明
•   2.1 SRA问题说明
•   2.2 经典哈希索引
•   2.3 Mapping算法和选种算法
•     2.3.1 Mapping算法
•     2.3.2 选种算法
•   2.4 并行应用技术
• 第3章 FEM算法
•   3.1 精简/稀疏哈希索引
•   3.2 分组选种
•   3.3 可变长度选种
•   3.4 FEM工作流程及负载均衡
• 第4章 实验结果和分析
•   4.1 实验配置及概述
•   4.2 索引构建和大小
•   4.3 模拟数据上的性能
•   4.4 真实数据上的性能
• step的影响'>  4.5 步长参数l_step的影响
•   4.6 候选位置的数量
• 第5章 总结和展望
•   5.1 总结
•   5.2 展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录
• 攻读学位期间参与的科研项目及获奖情况
• 学位论文评阅及答辩情况表

文章来源

类型: 硕士论文

作者: 范凯超

导师: 刘卫国

关键词: 下一代测序,短读序列映射,精简哈希索引,分组选种,可变长度选种

来源: 山东大学

年度: 2019

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

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

单位: 山东大学

分类号: TP311.13;Q811.4

总页数: 54

文件大小: 3720K

下载量: 17