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

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

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

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

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 研究背景
    1.2 國(guó)內(nèi)外研究現(xiàn)狀
    1.3 本文主要工作
    1.4 本文組織結(jié)構(gòu)
第2章 相關(guān)工作及問(wèn)題說(shuō)明
    2.1 SRA問(wèn)題說(shuō)明
    2.2 經(jīng)典哈希索引
    2.3 Mapping算法和選種算法
        2.3.1 Mapping算法
        2.3.2 選種算法
    2.4 并行應(yīng)用技術(shù)
第3章 FEM算法
    3.1 精簡(jiǎn)/稀疏哈希索引
    3.2 分組選種
    3.3 可變長(zhǎng)度選種
    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 步長(zhǎng)參數(shù)l_(step)的影響
    4.6 候選位置的數(shù)量
第5章 總結(jié)和展望
    5.1 總結(jié)
    5.2 展望
參考文獻(xiàn)
致謝
攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄
攻讀學(xué)位期間參與的科研項(xiàng)目及獲獎(jiǎng)情況
學(xué)位論文評(píng)閱及答辯情況表



本文編號(hào)：3176471