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

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

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

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