下一代測序技術(shù)（也可稱為大規(guī)模并行測序）允許人們在低成本條件下以驚人的吞吐量累積獲得海量核酸序列,并提供更短的讀數(shù)。吞吐量的大量增加和序列讀數(shù)的減小產(chǎn)生的代價是短讀的準(zhǔn)確性顯著低于傳統(tǒng)的測序手段,同時使短讀序列和參考序列的匹配在計算速度和精準(zhǔn)度上產(chǎn)生了巨大挑戰(zhàn),導(dǎo)致數(shù)據(jù)轉(zhuǎn)換為可用信息的計算時間變得更長;另外,海量數(shù)據(jù)也使計算機(jī)有限的內(nèi)存資源相形見絀。短讀序列映射過程中數(shù)據(jù)規(guī)模巨大,而目前已經(jīng)引入的各類索引技術(shù)無法高效的利用有限的內(nèi)存資源,內(nèi)存占用率較高。對此本文提出了一個新穎的索引數(shù)據(jù)結(jié)構(gòu)—精簡（稀疏）哈希索引數(shù)據(jù)結(jié)構(gòu),應(yīng)用于短讀序列匹配來緩解此問題。該數(shù)據(jù)結(jié)構(gòu)是經(jīng)典Q-gram索引的變種,通過參數(shù)設(shè)置決定內(nèi)存使用率,如對于人類參考基因組內(nèi)存占用可減少至經(jīng)典哈希的1/k。同時,實(shí)現(xiàn)了一種高效的并行構(gòu)造方法。另外,短讀序列映射過程的時間占了基因數(shù)據(jù)分析總時間的相當(dāng)大一部分。針對下一代測序技術(shù)吞吐量大量增加導(dǎo)致的短讀序列匹配計算速度減慢和匹配精度降低的問題,本文基于新提出的精簡哈希索引結(jié)構(gòu)設(shè)計了兩個選種算法一分組選種和可變長度選種,用于過濾策略中以減少校驗(yàn)次數(shù),從算法層面來提升計算速度。在... 

【文章來源】：山東大學(xué)山東省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：54 頁

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

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 研究背景
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 本文主要工作
    1.4 本文組織結(jié)構(gòu)
第2章 相關(guān)工作及問題說明
    2.1 SRA問題說明
    2.2 經(jīng)典哈希索引
    2.3 Mapping算法和選種算法
        2.3.1 Mapping算法
        2.3.2 選種算法
    2.4 并行應(yīng)用技術(shù)
第3章 FEM算法
    3.1 精簡/稀疏哈希索引
    3.2 分組選種
    3.3 可變長度選種
    3.4 FEM工作流程及負(fù)載均衡
第4章 實(shí)驗(yàn)結(jié)果和分析
    4.1 實(shí)驗(yàn)配置及概述
    4.2 索引構(gòu)建和大小
    4.3 模擬數(shù)據(jù)上的性能
    4.4 真實(shí)數(shù)據(jù)上的性能
    4.5 步長參數(shù)l_(step)的影響
    4.6 候選位置的數(shù)量
第5章 總結(jié)和展望
    5.1 總結(jié)
    5.2 展望
參考文獻(xiàn)
致謝
攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄
攻讀學(xué)位期間參與的科研項(xiàng)目及獲獎情況
學(xué)位論文評閱及答辯情況表



本文編號：3176471