基于Spark的DNA序列拼接算法研究

发布时间：2022-07-02 12:18

　　生物信息学是对生物信息进行处理的交叉学科,DNA序列拼接问题是其研究的主要内容之一。DNA序列长度少则几千,多则数十亿,但目前测序仪的平均读长仅在500bp左右,无法直接测得生物体的基因组。所以,DNA序列拼接算法应运而生。该算法首先将目标序列打断成小片段,然后对这些小片段进行分别测序,最后利用计算机技术根据片段间的重叠关系进行拼接。目前,序列拼接算法主要分为Overlap-Layout-Consensus拼接算法和de-Bruijin graph 拼接算法。Overlap-Layout-Consensus 拼接算法运用 "overlap-layout-consensus"方法基于read片段进行拼接处理,虽能保留片段的完整信息,但却不能有效克服重复序列的问题。de-Bruijin graph拼接算法将read片段进行进一步拆分,然后基于更小的片段单元进行拼接处理,一定程度上克服了重复序列问题,但同时产生大量的k-mer片段,并且需要生成deBruijin图,所以,这类算法存在着很大的存储和时间上的开销。另外,对于实现平台而言,大多数研究在于单机环境下实现的串行算法,这种算法的瓶颈是空... 

【文章页数】：57 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
缩略语表
1 引言
    1.1 DNA序列拼接概述
    1.2 课题背景
    1.3 国内外研究现状
    1.4 本文主要内容及意义
        1.4.1 课题研究内容
        1.4.2 课题研究意义
    1.5 论文章节安排
2 相关理论概述
    2.1 DNA测序技术
        2.1.1 第一代测序技术
        2.1.2 第二代测序技术
        2.1.3 第三代测序技术
    2.2 序列拼接问题描述
        2.2.1 研究DNA拼接算法的目的
        2.2.2 拼接算法难点
    2.3 序列拼接算法介绍
        2.3.1 Greedy-extension拼接算法
        2.3.2 Overlap-Layout-Consensus拼接算法
        2.3.3 de-Bruijin graph拼接算法
        2.3.4 算法优缺点对比
    2.4 拼接算法难点分析
        2.4.1 ARACHNE法
        2.4.2 路径相容法
        2.4.3 聚类分析法
    2.5 拼接算法并行化研究情况
    2.6 Spark并行框架介绍
        2.6.1 Spark要架构
        2.6.2 RDD简介
        2.6.3 Spark的任务处理
        2.6.4 Spark处理数据的特点
    2.7 本章小结
3 基于Spark的Improved SSA-Spark序列拼接算法
    3.1 拼接算法的选择
    3.2 de-Bruijin graph拼接算法具体流程
        3.2.1 k-mer序列的生成
        3.2.2 de-Bruijin图的建立
        3.2.3 拼接路径的选择
    3.3 Spark并行环境下的DNA序列拼接算法的处理
        3.3.1 read文件生成方式
        3.3.2 read序列的拆分过程
        3.3.3 Improved SSA-Sparκ算法中k-mer的获取
        3.3.4 Improved SSA-Spark算法拼接的路径选择
        3.3.5 Improved SSA-Spark算法在新平台Spark并行框架下的实现
    3.4 基于Spark的Improved SSA-Spark序列拼接算法步骤描述
    3.5 本章小结
4 模拟及实验结果分析
    4.1 云计算平台配置
    4.2 实验数据的产生
    4.3 实验设计
    4.4 实验结果与分析
        4.4.1 基于Spark的序列拼接算法与单机串行算法的时间比对
        4.4.2 基于Spark的序列拼接算法与MapReduce环境下的算法时间比对
        4.4.3 Improved SSA-Spark算法在Spark并行环境下的性能测试
        4.4.4 Improved SSA-Spark算法的线程数量对运行时间的影响
    4.5 本章小结
5 总结与展望
    5.1 总结
    5.2 展望
致谢
参考文献
作者简介



本文编号：3654351