面向基因組的高效FM-index構(gòu)造算法.pdf

1、隨著第一條人類DNA被解碼成2.8GB的字符串，許多生物學(xué)的研究都集中在對(duì)DNA序列的分析上。本文選取DNA序列的索引進(jìn)行研究，旨在解決目前DNA序列的FM-index不能夠在普通電腦（4-8G內(nèi)存）上高效構(gòu)造的問題。本文提出的增量式構(gòu)造FM-index的算法框架為繼續(xù)研究高效構(gòu)造FM-index提供了理論基礎(chǔ)。現(xiàn)實(shí)意義上，該算法擴(kuò)展了FM-index的應(yīng)用范圍，節(jié)約了購(gòu)買超級(jí)計(jì)算機(jī)的成本。
　　FM-index是壓縮全文本自索引

2、的一種。通常FM-index的算法框架分為以下步驟：首先，將文本T經(jīng)過BWT變換（Burrow-Wheeler Transform）得到的文本L；然后，采用小波樹（Wavelet-tree）對(duì)文本L進(jìn)行編碼存儲(chǔ)；接著為小波樹的內(nèi)部節(jié)點(diǎn)提供高效的rank查詢結(jié)構(gòu)；最后采樣后綴數(shù)組（SA）和名次數(shù)組（SA-1）。FM-index在這些基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的支持下實(shí)現(xiàn)高效的count，locate和extract操作。它最初最多使用5nHk(T)+o

3、(n)位的空間存儲(chǔ)，其中Hk(T)表示T的k階經(jīng)驗(yàn)熵，n表示文本的長(zhǎng)度。FM-index可在普通電腦內(nèi)存中存儲(chǔ)，然而構(gòu)造過程中過高的峰值內(nèi)存或者過長(zhǎng)的構(gòu)造的時(shí)間均限制了FM-index的應(yīng)用。通過大量閱讀和分析之前的研究成果，深入理解BWT變換的過程，理解SA、SA-1和LF映射的關(guān)系以及rank查詢結(jié)構(gòu)的特點(diǎn)，經(jīng)過大量實(shí)驗(yàn)測(cè)試與分析，最終得到了本文的算法。
　　本文主要分3個(gè)部分進(jìn)行了研究：首先，為了解決DNA數(shù)據(jù)的BWT變換無

4、法在普通電腦上完成的問題，本文提出了LF-BWT算法。該算法理論上在線性時(shí)間內(nèi)利用線性空間完成了DNA數(shù)據(jù)的BWT變換，實(shí)驗(yàn)表明，LF-BWT算法僅需不到原文本1倍的空間就可以快速完成DNA數(shù)據(jù)的BWT變換，并且可以調(diào)整參數(shù)來獲得時(shí)間和空間的權(quán)衡，進(jìn)一步擴(kuò)展了LF-BWT算法的使用范圍。該算法在與最新的主流算法的比較中也表現(xiàn)出了優(yōu)勢(shì)。第二，為了解決LF-BWT算法在構(gòu)造過程沒有獲得SA和SA-1采樣的問題，本文提出了由BWT變換生成的文

5、本通過LF映射在線性時(shí)間內(nèi)獲得SA和SA-1采樣的算法。該算法并不完整存儲(chǔ)SA，而是每次LF映射過程中遇到采樣點(diǎn)就進(jìn)行采樣，這極大的減小了內(nèi)存空間的占用。第三，為了更進(jìn)一步提高FM-index的壓縮率和查詢效率，本文提出了RRR算法的一個(gè)改進(jìn)版本CF算法，它充分結(jié)合了CPU字長(zhǎng)以及數(shù)據(jù)的局部性原理，提高了cache命中率。該算法在保持了與RRR算法的空間和查詢時(shí)間理論復(fù)雜性一致的情況下，提供了更加高效的實(shí)際性能。實(shí)驗(yàn)表明，不管是隨機(jī)數(shù)據(jù)