生物信息學(xué)是對(duì)生物信息進(jìn)行處理的交叉學(xué)科,DNA序列拼接問(wèn)題是其研究的主要內(nèi)容之一。DNA序列長(zhǎng)度少則幾千,多則數(shù)十億,但目前測(cè)序儀的平均讀長(zhǎng)僅在500bp左右,無(wú)法直接測(cè)得生物體的基因組。所以,DNA序列拼接算法應(yīng)運(yùn)而生。該算法首先將目標(biāo)序列打斷成小片段,然后對(duì)這些小片段進(jìn)行分別測(cè)序,最后利用計(jì)算機(jī)技術(shù)根據(jù)片段間的重疊關(guān)系進(jìn)行拼接。目前,序列拼接算法主要分為Overlap-Layout-Consensus拼接算法和de-Bruijin graph 拼接算法。Overlap-Layout-Consensus 拼接算法運(yùn)用 "overlap-layout-consensus"方法基于read片段進(jìn)行拼接處理,雖能保留片段的完整信息,但卻不能有效克服重復(fù)序列的問(wèn)題。de-Bruijin graph拼接算法將read片段進(jìn)行進(jìn)一步拆分,然后基于更小的片段單元進(jìn)行拼接處理,一定程度上克服了重復(fù)序列問(wèn)題,但同時(shí)產(chǎn)生大量的k-mer片段,并且需要生成deBruijin圖,所以,這類算法存在著很大的存儲(chǔ)和時(shí)間上的開銷。另外,對(duì)于實(shí)現(xiàn)平臺(tái)而言,大多數(shù)研究在于單機(jī)環(huán)境下實(shí)現(xiàn)的串行算法,這種算法的瓶頸是空... 

【文章頁(yè)數(shù)】：57 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
縮略語(yǔ)表
1 引言
    1.1 DNA序列拼接概述
    1.2 課題背景
    1.3 國(guó)內(nèi)外研究現(xiàn)狀
    1.4 本文主要內(nèi)容及意義
        1.4.1 課題研究?jī)?nèi)容
        1.4.2 課題研究意義
    1.5 論文章節(jié)安排
2 相關(guān)理論概述
    2.1 DNA測(cè)序技術(shù)
        2.1.1 第一代測(cè)序技術(shù)
        2.1.2 第二代測(cè)序技術(shù)
        2.1.3 第三代測(cè)序技術(shù)
    2.2 序列拼接問(wèn)題描述
        2.2.1 研究DNA拼接算法的目的
        2.2.2 拼接算法難點(diǎn)
    2.3 序列拼接算法介紹
        2.3.1 Greedy-extension拼接算法
        2.3.2 Overlap-Layout-Consensus拼接算法
        2.3.3 de-Bruijin graph拼接算法
        2.3.4 算法優(yōu)缺點(diǎn)對(duì)比
    2.4 拼接算法難點(diǎn)分析
        2.4.1 ARACHNE法
        2.4.2 路徑相容法
        2.4.3 聚類分析法
    2.5 拼接算法并行化研究情況
    2.6 Spark并行框架介紹
        2.6.1 Spark要架構(gòu)
        2.6.2 RDD簡(jiǎn)介
        2.6.3 Spark的任務(wù)處理
        2.6.4 Spark處理數(shù)據(jù)的特點(diǎn)
    2.7 本章小結(jié)
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并行環(huán)境下的DNA序列拼接算法的處理
        3.3.1 read文件生成方式
        3.3.2 read序列的拆分過(guò)程
        3.3.3 Improved SSA-Sparκ算法中k-mer的獲取
        3.3.4 Improved SSA-Spark算法拼接的路徑選擇
        3.3.5 Improved SSA-Spark算法在新平臺(tái)Spark并行框架下的實(shí)現(xiàn)
    3.4 基于Spark的Improved SSA-Spark序列拼接算法步驟描述
    3.5 本章小結(jié)
4 模擬及實(shí)驗(yàn)結(jié)果分析
    4.1 云計(jì)算平臺(tái)配置
    4.2 實(shí)驗(yàn)數(shù)據(jù)的產(chǎn)生
    4.3 實(shí)驗(yàn)設(shè)計(jì)
    4.4 實(shí)驗(yàn)結(jié)果與分析
        4.4.1 基于Spark的序列拼接算法與單機(jī)串行算法的時(shí)間比對(duì)
        4.4.2 基于Spark的序列拼接算法與MapReduce環(huán)境下的算法時(shí)間比對(duì)
        4.4.3 Improved SSA-Spark算法在Spark并行環(huán)境下的性能測(cè)試
        4.4.4 Improved SSA-Spark算法的線程數(shù)量對(duì)運(yùn)行時(shí)間的影響
    4.5 本章小結(jié)
5 總結(jié)與展望
    5.1 總結(jié)
    5.2 展望
致謝
參考文獻(xiàn)
作者簡(jiǎn)介



本文編號(hào)：3654351