面向基因組重測(cè)序的BWT索引壓縮算法.pdf

1、隨著新一代高通量測(cè)序技術(shù)的出現(xiàn)，DNA測(cè)序技術(shù)已成為研究生命科學(xué)領(lǐng)域的重要手段，而新一代測(cè)序技術(shù)產(chǎn)生的讀取數(shù)據(jù)長(zhǎng)度較短，并且數(shù)據(jù)通量非常巨大，這給生物信息學(xué)帶來(lái)了新的機(jī)遇和挑戰(zhàn)。其中對(duì)于這些數(shù)據(jù)的分析算法的研究面臨著巨大的挑戰(zhàn)，特別是序列比對(duì)算法和數(shù)據(jù)存儲(chǔ)算法。目前，隨著新一代測(cè)序技術(shù)的不斷普及，基因組重測(cè)序的序列比對(duì)程序（如MAQ、mrFast、SOAP等）越來(lái)越多，而且它們采用的結(jié)構(gòu)也不斷完善，性能上越來(lái)越好。這其中包括哈希表，后綴

2、數(shù)組，后綴樹等結(jié)構(gòu)，而最近幾年出現(xiàn)了使用壓縮模型Burrows-Wheeler變換。由于其空間占有量非常小，而且在查找匹配方面能夠?qū)崿F(xiàn)塊搜索，從而大大提高了拼接算法的時(shí)間和空間利用率。這使得全基因組序列比對(duì)軟件在個(gè)人計(jì)算機(jī)上運(yùn)行成為了可能，并給非專業(yè)研究人員帶來(lái)了研究生物學(xué)眾多問(wèn)題的機(jī)遇。
　　本文面向新一代測(cè)序數(shù)據(jù)，在人類全基因組上利用BWT變換，在保證整個(gè)reads映射過(guò)程的拼接速度不變的情況下，提出了BWT索引壓縮方法，構(gòu)建

3、了一個(gè)新的BWT索引結(jié)構(gòu)。利用該結(jié)構(gòu)構(gòu)建一個(gè)reads映射系統(tǒng)，該系統(tǒng)實(shí)現(xiàn)了reads數(shù)據(jù)快速映射到人類參考基因組序列上。其中通過(guò)構(gòu)建檢查點(diǎn)結(jié)構(gòu)信息來(lái)快速查找映射對(duì)應(yīng)關(guān)系，通過(guò)構(gòu)建位置信息來(lái)快速返回讀取數(shù)據(jù)的拼接位點(diǎn)。由于BWT后綴序列在BWT索引中占據(jù)大量空間，而對(duì)于BWT后綴序列的壓縮存儲(chǔ)直接影響了整個(gè)reads映射過(guò)程的拼接速度?？紤]到BWT后綴序列結(jié)構(gòu)中堿基分布不均勻，堿基序列重復(fù)度比較高，為了提高整個(gè)reads映射過(guò)程的內(nèi)存利