在過(guò)去的數(shù)年中,高通量測(cè)序在極大的拓展了測(cè)序技術(shù)應(yīng)用領(lǐng)域的同時(shí)也產(chǎn)生了海量的測(cè)序數(shù)據(jù)集。如何將這些海量的測(cè)序序列數(shù)據(jù)快速的比對(duì)到基因組上,準(zhǔn)確的找出它們的原始位置是許多生物醫(yī)學(xué)領(lǐng)域研究的前提和至關(guān)重要的一步,因此已有許多序列比對(duì)工具被開(kāi)發(fā)出來(lái)專(zhuān)門(mén)用于短序列比對(duì)。然而隨著高通量測(cè)序技術(shù)的不斷發(fā)展,生成的序列長(zhǎng)度已由最初的36bp增加到100¹50bp,一些針對(duì)短序列開(kāi)發(fā)出的基于BWT索引結(jié)構(gòu)的比對(duì)工具在使用回溯算法實(shí)現(xiàn)模糊比對(duì)時(shí)會(huì)帶來(lái)候選解占用空間過(guò)大,搜索替換占用時(shí)間過(guò)長(zhǎng)的問(wèn)題。因此,一些后期開(kāi)發(fā)的高通量測(cè)序比對(duì)軟件普遍開(kāi)始通過(guò)從序列中選取種子優(yōu)先進(jìn)行比對(duì)的策略來(lái)尋找整個(gè)序列在基因組上的比對(duì)位置。然而由于一般情況下種子的長(zhǎng)度較短,在參考基因組上擁有大量的候選位置,因此或是需要耗費(fèi)數(shù)倍于參考基因組大小的空間來(lái)存儲(chǔ)這些數(shù)據(jù)或是需要相當(dāng)?shù)臅r(shí)間進(jìn)行反復(fù)查找。為了更好的滿足高通量測(cè)序序列比對(duì)的新要求,我們?cè)贐WT索引結(jié)構(gòu)的基礎(chǔ)上結(jié)合了哈希索引的策略,提出了一種基于改進(jìn)索引結(jié)構(gòu)的比對(duì)算法,能夠很好的達(dá)到時(shí)間與空間的平衡。具體工作如下:(1)本文首先對(duì)近幾年發(fā)布的,面向100<...

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

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

【文章目錄】：
摘要
abstract
第一章 緒論
    1.1 研究背景
    1.2 研究的目的及意義
    1.3 國(guó)內(nèi)外研究現(xiàn)狀
        1.3.1 基于哈希索引的比對(duì)算法
        1.3.2 基于前綴/后綴索引的比對(duì)算法
    1.4 本文主要研究?jī)?nèi)容
        1.4.1 面向中長(zhǎng)序列比對(duì)算法索引結(jié)構(gòu)的研究及改進(jìn)
        1.4.2 找最佳模式下種子選取及候選位置過(guò)濾的研究
        1.4.3 比對(duì)系統(tǒng)的實(shí)現(xiàn)
    1.5 論文組織結(jié)構(gòu)
第二章 高通量測(cè)序序列比對(duì)相關(guān)介紹
    2.1 引言
    2.2 高通量測(cè)序平臺(tái)
        2.2.1Roche454
        2.2.2 Illumina
        2.2.3 SOLiD
        2.2.4 PacBioRSII第三代測(cè)序
    2.3 序列比對(duì)中使用和生成的數(shù)據(jù)格式
        2.3.1 FASTA/FASTQ格式
        2.3.2 SAM格式
    2.4 序列比對(duì)的定義與基本方法
        2.4.1 精確匹配
        2.4.2 近似匹配
    2.5 序列比對(duì)算法的評(píng)價(jià)標(biāo)準(zhǔn)
    2.6 本章小結(jié)
第三章 面向中長(zhǎng)序列比對(duì)算法的索引結(jié)構(gòu)研究及改進(jìn)
    3.1 引言
    3.2 基于Burrows-WheelerTransform(BWT)索引結(jié)構(gòu)的搜索算法
        3.2.1 BWT的基本原理
        3.2.2 基于BWT的FM-Index搜索算法
    3.3 改進(jìn)的索引結(jié)構(gòu)設(shè)計(jì)與算法
        3.3.1 改進(jìn)的索引結(jié)構(gòu)總體設(shè)計(jì)
        3.3.2 改進(jìn)的索引結(jié)構(gòu)定位算法
        3.3.3 改進(jìn)的索引結(jié)構(gòu)算法性能分析
    3.4 實(shí)驗(yàn)結(jié)果與討論
    3.5 本章小結(jié)
第四章 找最佳模式下種子選取及候選位置過(guò)濾的研究
    4.1 引言
    4.2 種子選取及候選位置過(guò)濾的研究
        4.2.1 固定長(zhǎng)度種子的選取及過(guò)濾
        4.2.2 可變長(zhǎng)度種子的選取及過(guò)濾
    4.3 找最佳模式下種子選取及候選位置過(guò)濾算法
        4.3.1 種子的選取
        4.3.2 最優(yōu)覆蓋鏈接算法
    4.4 比對(duì)系統(tǒng)的整體流程與實(shí)現(xiàn)
    4.5 系統(tǒng)測(cè)試
    4.6 本章小結(jié)
第五章 總結(jié)與展望
    5.1 本文工作總結(jié)
    5.2 后續(xù)工作展望
附錄一 基于改進(jìn)索引結(jié)構(gòu)的分塊定位算法偽代碼
附錄二 軟件參數(shù)設(shè)置
附錄三 部分核心代碼
參考文獻(xiàn)
致謝
在學(xué)期間的研究成果及學(xué)術(shù)論文情況



本文編號(hào)：3743884