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

发布时间：2021-05-09 02:51

　　下一代测序技术（也可称为大规模并行测序）允许人们在低成本条件下以惊人的吞吐量累积获得海量核酸序列,并提供更短的读数。吞吐量的大量增加和序列读数的减小产生的代价是短读的准确性显著低于传统的测序手段,同时使短读序列和参考序列的匹配在计算速度和精准度上产生了巨大挑战,导致数据转换为可用信息的计算时间变得更长;另外,海量数据也使计算机有限的内存资源相形见绌。短读序列映射过程中数据规模巨大,而目前已经引入的各类索引技术无法高效的利用有限的内存资源,内存占用率较高。对此本文提出了一个新颖的索引数据结构—精简（稀疏）哈希索引数据结构,应用于短读序列匹配来缓解此问题。该数据结构是经典Q-gram索引的变种,通过参数设置决定内存使用率,如对于人类参考基因组内存占用可减少至经典哈希的1/k。同时,实现了一种高效的并行构造方法。另外,短读序列映射过程的时间占了基因数据分析总时间的相当大一部分。针对下一代测序技术吞吐量大量增加导致的短读序列匹配计算速度减慢和匹配精度降低的问题,本文基于新提出的精简哈希索引结构设计了两个选种算法一分组选种和可变长度选种,用于过滤策略中以减少校验次数,从算法层面来提升计算速度。在... 

【文章来源】：山东大学山东省 211工程院校 985工程院校 教育部直属院校

【文章页数】：54 页

【学位级别】：硕士

【文章目录】：
摘要
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 真实数据上的性能
    4.5 步长参数l_(step)的影响
    4.6 候选位置的数量
第5章 总结和展望
    5.1 总结
    5.2 展望
参考文献
致谢
攻读学位期间发表的学术论文目录
攻读学位期间参与的科研项目及获奖情况
学位论文评阅及答辩情况表



本文编号：3176471