朱澤軒，張永朋，尤著宏，姜 亮，紀(jì) 震

1)深圳市嵌入式系統(tǒng)設(shè)計(jì)重點(diǎn)實(shí)驗(yàn)室，深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院，深圳518060;2)深圳大學(xué)生命科學(xué)學(xué)院，深圳518060

自1977年Sanger［1］發(fā)明基于熒光標(biāo)記的末端終止法DNA測(cè)序技術(shù)以來(lái)，DNA測(cè)序技術(shù)已被廣泛用于生物和醫(yī)學(xué)領(lǐng)域.2005年Margulies等［2］提出基于循環(huán)陣列合成的高通量測(cè)序方法，又稱“下一代測(cè)序(next generation sequencing，NGS)”方法.該方法已在各種實(shí)現(xiàn)平臺(tái)上獲得了超大量的DNA序列數(shù)據(jù).采用非光學(xué)顯微鏡成像［3］或納米孔技術(shù)［4］的單分子測(cè)序技術(shù)有可能改變?nèi)藗冄芯可{(lán)圖的方式.測(cè)序成本的降低和測(cè)序效率的提高，促使人們不斷加強(qiáng)對(duì)DNA測(cè)序的大規(guī)模研究，使得DNA序列數(shù)據(jù)在近年呈爆炸性增長(zhǎng)［5］(圖1).現(xiàn)在，全球最大的DNA序列數(shù)據(jù)中心EBI和NCBI已分別存儲(chǔ)了超過(guò)萬(wàn)億個(gè)堿基對(duì)(base pair，bp).許多大型DNA研究項(xiàng)目，如千人基因組計(jì)劃(1000 Genome Project)、國(guó)際癌癥基因組計(jì)劃(International Cancer Genome Project，ICGC)、DNA 元件百科全書(shū)計(jì)劃(Encyclopedia of DNA Elements，ENCODE)等，正以前所未有的速度產(chǎn)生海量DNA序列.如千人基因組項(xiàng)目采用NGS測(cè)序技術(shù)，在建立后6個(gè)月內(nèi)即獲得了超過(guò)NCBI中心Genbank數(shù)據(jù)庫(kù)累積21年的數(shù)據(jù)量.計(jì)算機(jī)是存儲(chǔ)和處理DNA數(shù)據(jù)的主要工具，其微處理器性能和存儲(chǔ)設(shè)備容量平均18～24個(gè)月翻一番，而DNA測(cè)序數(shù)據(jù)平均4～5個(gè)月就翻一番，DNA測(cè)序數(shù)據(jù)的增長(zhǎng)速度已遠(yuǎn)超計(jì)算機(jī)微處理器和存儲(chǔ)設(shè)備的增長(zhǎng)速度.如何存儲(chǔ)和傳輸高通量DNA測(cè)序產(chǎn)生的數(shù)據(jù)，成為決定DNA研究發(fā)展的重要因素之一.數(shù)據(jù)壓縮是有效解決DNA序列存儲(chǔ)和傳輸?shù)囊环N重要方法.

圖1 DNA測(cè)序成本和序列數(shù)據(jù)量變化趨勢(shì)Fig.1 Changing trends of DNA sequencing cost and data size

1 傳統(tǒng)DNA序列壓縮方法

人類迄今對(duì)DNA序列的功能仍未完全掌握，因此在壓縮過(guò)程必需保證原始數(shù)據(jù)的可靠性和信息的完整性，即在客觀上要求無(wú)損壓縮.DNA序列通常表示為堿基 {A，C，G，T}構(gòu)成的字符串，常見(jiàn)壓縮工具未考慮DNA序列的生物學(xué)特性，對(duì)其數(shù)據(jù)的壓縮效果不甚理想.

研究DNA序列的專用壓縮算法始于1993年，Grumbach等［6］提出針對(duì)DNA序列特有的互補(bǔ)回文結(jié)構(gòu)的壓縮方法BioCompress，該方法用Fibonacci編碼對(duì)DNA序列中的直接重復(fù)和互補(bǔ)回文片段進(jìn)行壓縮，可有效降低這部分?jǐn)?shù)據(jù)的冗余，開(kāi)啟了DNA序列壓縮的研究之門(mén).此后，針對(duì)DNA序列的壓縮逐漸引起人們的注意，研究人員提出諸如替代法(又稱字典法)和統(tǒng)計(jì)法［7］等.

替代法尋找重復(fù)出現(xiàn)頻率高的DNA片段并將其編入字典，在原文中將對(duì)應(yīng)片段替換為字典索引編號(hào)或使用更簡(jiǎn)短的編碼方式，達(dá)到壓縮目的.該方法在尋找重復(fù)片段的過(guò)程充分考慮了DNA互補(bǔ)回文和近似匹配等生物學(xué)特性.經(jīng)典的替代壓縮算法 包 括 BioCompress［6］、 CTW-LZ［8］和DNACompress［9］等.統(tǒng)計(jì)法主要通過(guò)統(tǒng)計(jì)各個(gè)堿基符號(hào)出現(xiàn)的概率建立預(yù)測(cè)模型，然后利用預(yù)測(cè)模型對(duì)DNA序列進(jìn)行預(yù)測(cè)并采用算數(shù)編碼進(jìn)行壓縮.代表性的統(tǒng)計(jì)壓縮算法包括 CDNA［10］和XM［11］等.張麗霞等［12］提出的多重壓縮技術(shù)屬該類型.

Giancarlo等［7］對(duì)傳統(tǒng) DNA壓縮法做了綜述，指出上述DNA序列壓縮方法只利用DNA序列自身的冗余信息進(jìn)行壓縮，對(duì)小規(guī)模DNA測(cè)序數(shù)據(jù)的壓縮效果較好，但高通量DNA測(cè)序往往是對(duì)全基因組的大規(guī)模測(cè)序，使用上述方法后的壓縮效率有限，需要專門(mén)針對(duì)高通量測(cè)序數(shù)據(jù)的壓縮技術(shù).

2 高通量DNA測(cè)序數(shù)據(jù)壓縮

現(xiàn)階段高通量DNA測(cè)序數(shù)據(jù)壓縮研究主要針對(duì)全基因組測(cè)序數(shù)據(jù).現(xiàn)有的高通量DNA測(cè)序方法主要基于NGS技術(shù)，常用的NGS平臺(tái)包括Illumina的Genome Analyzer、羅氏454基因測(cè)序儀以及AB Life Technologies的Ion Proton.NGS測(cè)序產(chǎn)生的是短讀(short read，長(zhǎng)度通常在幾十到幾百個(gè)堿基對(duì)的DNA短片段)和質(zhì)量分?jǐn)?shù)(quality score，每個(gè)測(cè)定的堿基提供一個(gè)質(zhì)量分?jǐn)?shù)表明該測(cè)定的可信度).在測(cè)序過(guò)程中為保證數(shù)據(jù)的可靠性，需使短讀對(duì)目標(biāo)序列保持幾十倍的覆蓋率，因此，NGS測(cè)序產(chǎn)生的數(shù)據(jù)量遠(yuǎn)大于傳統(tǒng)Sanger測(cè)序.質(zhì)量分?jǐn)?shù)因其對(duì)短讀拼接(assembly)、糾錯(cuò)及其他后續(xù)相關(guān)研究的重要作用，也必須妥善存儲(chǔ).根據(jù)短讀拼接和組裝模式不同，NGS可分為重測(cè)序(resequencing)［13］和從頭測(cè)序(de novo sequencing)［14］.

2.1 重測(cè)序DNA序列壓縮

重測(cè)序主要針對(duì)已完成測(cè)序物種的不同個(gè)體進(jìn)行測(cè)序.由于疾病研究、設(shè)計(jì)標(biāo)記、人類單核酸多態(tài)(single nucleotide polymorphism，SNP)研究等原因，需對(duì)相同物種的不同個(gè)體測(cè)序.若該物種某些個(gè)體已取得完整基因組序列，則重測(cè)序技術(shù)可將已完成的基因組作為參考樣本，利用NGS技術(shù)產(chǎn)生大規(guī)模DNA短讀高度覆蓋目標(biāo)基因組，然后通過(guò)短讀與參考基因組的映射獲得目標(biāo)基因組數(shù)據(jù).

重測(cè)序數(shù)據(jù)壓縮主要通過(guò)記錄短讀與參考基因組的差異信息進(jìn)行壓縮，該方法也稱為基于參考基因組壓縮(reference-based compression).由于同源物種基因組之間具有高度相似性，針對(duì)重測(cè)序數(shù)據(jù)的壓縮通常能達(dá)到很高的壓縮比.以人類為例，任何兩個(gè)人的基因組有超過(guò)99%的內(nèi)容是完全相同的，若已獲得參考基因組，則對(duì)于目標(biāo)基因組的儲(chǔ)存，只需存儲(chǔ)1%額外的差異信息［15］.

2.1.1 基于參考基因組壓縮流程及關(guān)鍵技術(shù)

圖2為針對(duì)NGS測(cè)序短讀的基于參考基因組壓縮流程，具體步驟為

1)選定一個(gè)適當(dāng)?shù)膮⒖蓟蚪M作為壓縮參考樣本，通常選用具有高度相似性的同源物種序列作為參考基因組.

2)通過(guò)基于生物學(xué)特性的映射(mapping)過(guò)程，確定短讀與參考基因組的匹配位置、匹配類型、差異位置、差異類型和差異內(nèi)容.

3)對(duì)映射結(jié)果采用高效編碼進(jìn)行壓縮.

重測(cè)序數(shù)據(jù)壓縮涉及幾項(xiàng)關(guān)鍵技術(shù)包括短讀映射、映射結(jié)果編碼和基因組自身壓縮.

短讀映射.NGS技術(shù)的一個(gè)基本特點(diǎn)是測(cè)序產(chǎn)生大量短讀，重測(cè)序過(guò)程中的難題之一是短讀映射，即將短讀與參考基因組進(jìn)行序列比對(duì)(alignment)，找到每條短讀在基因組中的位置和與參考基因組的差異信息.傳統(tǒng)的映射方法如BLAT［16］或BLAST［17］主要用于Sanger測(cè)序，并不適合高通量測(cè)序數(shù)據(jù).目前針對(duì)高通量測(cè)序數(shù)據(jù)的映射算法，主要是基于哈希表的SFE(seed filter extend)［18］算法和基于BWT(burrows wheeler transform)的映射算法［19］.

圖2 基于參考基因組壓縮流程圖Fig.2 Flow chart of reference-based compression

映射結(jié)果壓縮編碼.通過(guò)映射，可獲得短讀在參考基因組上的匹配位置、匹配類型、差異位置、差異類型及差異內(nèi)容［20］，這些映射結(jié)果可用有效的編碼進(jìn)行壓縮存儲(chǔ).例如，已知序列由堿基 {A，C，G，T}構(gòu)成，僅考慮SNP的情況，則短讀映射結(jié)果可歸納如表1.

表1 映射結(jié)果Table1 Mapping results

圖2列舉了直接匹配、鏡像匹配和互補(bǔ)回文3種短讀類型，根據(jù)映射結(jié)果對(duì)短讀進(jìn)行編碼，其長(zhǎng)度會(huì)比直接編碼短讀每個(gè)字符明顯減少.目前映射結(jié)果常用 Golomb、Delta、Elias、Gamma、MOV或Huffman等整數(shù)編碼進(jìn)行壓縮.為提高壓縮率，匹配位置和差異位置一般使用相對(duì)位置［20］.使用具有生物學(xué)特征的匹配類型如鏡像重復(fù)、配對(duì)重復(fù)和互補(bǔ)回文也有助于提高數(shù)據(jù)壓縮比［21］.

壓縮參考基因組.重測(cè)序數(shù)據(jù)壓縮和解壓都必需使用參考基因組.有些物種，如人類，其參考基因組本身就有幾Gbit，為便于存儲(chǔ)和傳輸，必需考慮對(duì)參考基因組自身進(jìn)行壓縮.

2005-2011年，高通量DNA數(shù)據(jù)壓縮有了長(zhǎng)足進(jìn)步［22-26］.其中，Korodi等［22-23］提出基于統(tǒng)計(jì)法的NML算法，首次嘗試對(duì)大型基因組整體壓縮，并提出 GeNML算法.其后，Kuruppu等［24-25］提出基于字典法的RLZ算法，并進(jìn)行改進(jìn).Christley等［15］使用各種不同編碼技術(shù)和外部SNP信息將完整人類基因組壓縮至4 Mbit大小.

2.1.2 代表算法

隨著NGS技術(shù)的不斷發(fā)展，對(duì)于重測(cè)序數(shù)據(jù)壓縮的研究廣受關(guān)注，表2匯集了近年提出的代表算法及其主要特點(diǎn).表中所有算法都是基于參考基因組的壓縮方法.其中，Quip、Cramtools和NGC主要針對(duì)短讀，而DNAzip、BWB和GRS是針對(duì)完整目標(biāo)基因組的壓縮.這些方法各有千秋，在實(shí)際使用中，應(yīng)該充分考慮壓縮對(duì)象、參考基因組和其他輔助數(shù)據(jù)的可獲得性，以及計(jì)算資源來(lái)選擇恰當(dāng)?shù)膲嚎s方法.

表2 重測(cè)序數(shù)據(jù)壓縮代表算法Table2 The state-of-the-art compression algorithms of resequencing data

基于參考基因組的壓縮方法壓縮比很高，但其使用亦有明顯局限，對(duì)于參考序列依賴性太強(qiáng)，但有些測(cè)序數(shù)據(jù)并不存在現(xiàn)成的參考基因組;另外，由于壓縮和解壓縮都需要相同的參考基因組，參考基因組必須事先保存在本地，如果參考基因組缺失將直接影響壓縮數(shù)據(jù)的使用.

2.2 從頭測(cè)序數(shù)據(jù)壓縮

與重測(cè)序不同，從頭測(cè)序不依賴現(xiàn)成的參考基因序列，而是直接對(duì)待測(cè)個(gè)體進(jìn)行測(cè)序，然后對(duì)測(cè)序產(chǎn)生的短讀進(jìn)行從頭拼接和組裝.因此，針對(duì)從頭測(cè)序數(shù)據(jù)的壓縮也無(wú)外部參考序列的支持.對(duì)從頭測(cè)序數(shù)據(jù)的壓縮研究仍處于起步階段，目前其壓縮流程主要分兩個(gè)階段:①用一小部分短讀拼接成疊連群(contigs)作為臨時(shí)參考基因組;②采用基于參考基因組壓縮方法依次進(jìn)行短讀映射，映射結(jié)果壓縮編碼.

由于壓縮過(guò)程中使用的參考基因組不是來(lái)自外部而是由部分短讀拼接獲得，可見(jiàn)其關(guān)鍵步驟是短讀拼接，即通過(guò)短讀再現(xiàn)完整DNA序列的過(guò)程.NGS產(chǎn)生的大部分短讀存在重疊區(qū)域，這為合并短讀提供了必要信息.目前，NGS短讀拼接算法主要有 OLC(overlap layout consensus) 算 法［27］、de Bruijn圖算法［28］和基于OLC或 de Bruijn圖的貪婪算法［29］.除短讀拼接，從頭測(cè)序數(shù)據(jù)壓縮的其他技術(shù)與重測(cè)序數(shù)據(jù)壓縮類似.

目前針對(duì)從頭測(cè)序數(shù)據(jù)壓縮的研究相對(duì)較少，代表性的有Fritz等［13］提出的對(duì)無(wú)法映射短讀采用從頭測(cè)序數(shù)據(jù)壓縮方法和Jones等［14］提出基于拼接的從頭測(cè)序壓縮算法Quip.該算法使用概率數(shù)據(jù)結(jié)構(gòu)極大減少了使用de Bruijn圖進(jìn)行拼接時(shí)的內(nèi)存需求，有效提高了短讀拼接的規(guī)模，為以后從頭測(cè)序數(shù)據(jù)壓縮算法的發(fā)展提供參照.

與重測(cè)序壓縮相比，從頭測(cè)序壓縮優(yōu)勢(shì)在于它不依賴于外部參考基因組，自完備性好，但它在一定程度上仍受制于拼接技術(shù).從頭測(cè)序壓縮方法也適用于重測(cè)序數(shù)據(jù)，但其壓縮比低于重測(cè)序壓縮方法，如果已獲得適當(dāng)?shù)膮⒖蓟蚪M，則應(yīng)優(yōu)先考慮重測(cè)序壓縮方法.

2.3 質(zhì)量分?jǐn)?shù)的壓縮

質(zhì)量分?jǐn)?shù)伴隨著短讀序列的產(chǎn)生，每一個(gè)堿基對(duì)對(duì)應(yīng)一個(gè)質(zhì)量分?jǐn)?shù)，質(zhì)量分?jǐn)?shù)的保存有利于序列數(shù)據(jù)的后續(xù)分析和使用，因此質(zhì)量分?jǐn)?shù)的壓縮存儲(chǔ)也非常重要.與DNA序列只由4種堿基構(gòu)成不同，質(zhì)量分?jǐn)?shù)由更多字符表示，另外質(zhì)量分?jǐn)?shù)通常擁有很多的冗余信息，對(duì)其編碼通常會(huì)有很高的熵，因此質(zhì)量分?jǐn)?shù)壓縮較DNA序列壓縮更難［14］.目前質(zhì)量分?jǐn)?shù)壓縮有無(wú)損和有損兩種方法.

對(duì)質(zhì)量分?jǐn)?shù)的無(wú)損壓縮主要采用Huffman編碼、LZ77和馬爾科夫鏈技術(shù).Tembe等［30］使用Huffman編碼對(duì)質(zhì)量分?jǐn)?shù)進(jìn)行壓縮，Deorowicz等［31］將數(shù)據(jù)中不同類型的質(zhì)量分?jǐn)?shù)采用不同的編碼方式，如哈希表、游程編碼和Huffman編碼進(jìn)行壓縮.Jones等［14］使用三階馬爾科夫鏈對(duì)質(zhì)量分?jǐn)?shù)進(jìn)行壓縮.

文獻(xiàn)［13，31-32］提出了對(duì)質(zhì)量分?jǐn)?shù)的有損壓縮方法，如用隨機(jī)化湊整的方法減少描述質(zhì)量分?jǐn)?shù)的字符，匹配到參考基因組后丟棄質(zhì)量分?jǐn)?shù)，對(duì)質(zhì)量分?jǐn)?shù)量化等.有損壓縮可以提高壓縮比，但也丟失了部分信息，因此采用這種壓縮方式值得商榷.

2.4 壓縮數(shù)據(jù)檢索

壓縮數(shù)據(jù)可減少存儲(chǔ)空間和傳輸時(shí)間，但對(duì)壓縮數(shù)據(jù)進(jìn)行分析前需進(jìn)行解壓.隨著測(cè)序數(shù)據(jù)量的增大，解壓變得十分耗費(fèi)計(jì)算資源，解壓后的數(shù)據(jù)需被加載入內(nèi)存進(jìn)行分析，這對(duì)內(nèi)存容量也提出了更高要求.如果能讓DNA序列在壓縮狀態(tài)下直接查詢、提取和檢索，將有效減少資源消耗.目前基于壓縮序列數(shù)據(jù)的索引技術(shù)主要有:Burrows-Wheeler索引、壓縮后綴數(shù)組和LZ索引［33］.

Burrows-Wheeler索引.FM-index［34］被認(rèn)為是第一個(gè)構(gòu)建Burrows-Wheeler索引的算法，使用新的數(shù)據(jù)結(jié)構(gòu)用于搜索和索引，可促進(jìn)壓縮序列上搜索功能的實(shí)施.Makinen等［35］提出FM-index的改進(jìn)版，使RLFM在空間和時(shí)間復(fù)雜度方面有較大提升.

壓縮后綴數(shù)組.Grossi等［36］提出的CSA方法，使用壓縮后綴數(shù)組構(gòu)建壓縮后綴樹(shù)和空間有效的索引機(jī)制.RLCSA算法［37］是CSA的改進(jìn)版，其在壓縮和索引性能上都有一定提升，并允許索引多序列集合.

LZ索引.Ukkonen等［38］嘗試用LZ77算法查詢壓縮數(shù)據(jù)，使用LZ77壓縮字符串引發(fā)k-mer索引.Kreft等［39］提出的LZ-End索引使用LZ77算法解析輸入字符串，在索引高度重復(fù)的序列數(shù)據(jù)中有一定優(yōu)勢(shì).

在壓縮狀態(tài)實(shí)現(xiàn)序列的常規(guī)分析是未來(lái)發(fā)展的主要趨勢(shì).上述索引算法可在不解壓的情況下有效提取和搜索序列子串，為以后壓縮基因組的分析與應(yīng)用提供幫助.

展 望

目前，高通量DNA測(cè)序數(shù)據(jù)的壓縮研究已取得一定成果，但其在計(jì)算資源、壓縮算法和測(cè)序平臺(tái)方面仍面臨巨大挑戰(zhàn)［40］.DNA測(cè)序輸出的數(shù)據(jù)量和計(jì)算機(jī)資源之間的缺口正在不斷加大，處理時(shí)間過(guò)長(zhǎng)已成為DNA測(cè)序數(shù)據(jù)分析不可避免的問(wèn)題.結(jié)合云計(jì)算平臺(tái)的壓縮和分析技術(shù)［41］，有望緩解計(jì)算壓力.

未來(lái)DNA測(cè)序平臺(tái)會(huì)產(chǎn)生更優(yōu)質(zhì)的短讀，如第3代測(cè)序采用基于納米孔的單分子測(cè)序方法［4］，短讀長(zhǎng)度可達(dá)到1～3 kbp，壓縮算法需要不斷順應(yīng)DNA測(cè)序技術(shù)的發(fā)展，提供壓縮序列的檢索功能，適應(yīng)不同應(yīng)用需求.壓縮算法需進(jìn)一步提高效率，可采用平行化策略減少計(jì)算機(jī)內(nèi)存消耗，如GSQZ［30］算法.

不同測(cè)序平臺(tái)產(chǎn)生不同質(zhì)量品質(zhì)和長(zhǎng)度的高通量短讀，對(duì)壓縮算法的選擇也有很大的影響，因此需要統(tǒng)一標(biāo)準(zhǔn)，評(píng)價(jià)不同平臺(tái)的數(shù)據(jù)質(zhì)量.

DNA測(cè)序技術(shù)不斷推動(dòng)生物工程和醫(yī)學(xué)等相關(guān)領(lǐng)域的發(fā)展［42］，在高速和低價(jià)的前提下，為醫(yī)學(xué)研究和診斷學(xué)等領(lǐng)域的廣泛應(yīng)用提供了可能.基因組學(xué)、功能基因組學(xué)和新病毒機(jī)理等領(lǐng)域的進(jìn)步均得益于DNA測(cè)序的發(fā)展［43-45］.解決好高通量DNA測(cè)序數(shù)據(jù)存儲(chǔ)和傳輸問(wèn)題是推動(dòng)這些領(lǐng)域進(jìn)一步發(fā)展的前提.未來(lái)DNA序列的數(shù)據(jù)量可能超乎想象，為迎接挑戰(zhàn)，需發(fā)展全新的DNA序列壓縮算法.

/References:

［1］Sanger F，Nicklen S，Coulson A R.DNA sequencing with chain-terminating inhibitors［J］.Proceedings of the National Academy of Sciences of the United States of A-merica，1977，74(12):5463-5467.

［2］Margulies M，Egholm M，Altman W E，et al.Genome sequencing in microfabricated high-density picolitre reactors ［J］.Nature，2005，437(7057):376-380.

［3］Kai A.STM and AFM of bio/organic molecules and structures［J］.Surface Science Reports，1996，26(8):263-332.

［4］Hibbs X，Krstic S，Mastrangelo A，et al.The potential and challenges of nanopore sequencing［J］.Nature Biotechnology，2008，26(10):1146-1153.

［5］Kahn S D.On the future of genomic data［J］.Science，2011，331(6018):728-729.

［6］Grumbach S，Tahi F.Compression of DNA sequences［C］//In Proceedings of Data Compression Conference.Snowbird(USA):IEEE Computer Society，1993:340-350.

［7］Giancarlo R，Scaturro D，Utro F.Textual data compression in computational biology:asynopsis［J］.Bioinformatics，2009，25(13):1575-1586.

［8］Matsumoto T，Sadakane K，Imai H.Biological sequence compression algorithms［C］//Proceedings of Genome Informatics Workshop，Tokyo，2000:43-52.

［9］Chen X，Li M，Ma B，et al.DNA compress:fast and effective DNA sequence compression ［J］.Bioinformatics，2002，18(2):1696-1698.

［10］Loewenstern D，Yianilos P N.Significantly lower entropy estimates for natural DNA sequences［J］.Computational Biology，1999，6(1):125-142.

［11］Cao M D，Dix T I，Allison L，et al.A simple statistical algorithm for biological sequence compression［C］//In Proceedings of the Conference on Data Compression，Snowbird(USA):IEEE Computer Society，2007:43-52.

［12］Zhang Lixia， Song Hongzhi. Multiple-compression of DNA sequence data［J］.Journal of Computer Applications，2010，30(5):1379-1382.(in Chinese)張麗霞，宋鴻陟.多重壓縮DNA序列數(shù)據(jù) ［J］.計(jì)算機(jī)應(yīng)用，2007，30(5):1379-1382.

［13］Fritz M H Y，Leinonen R，Cochrane G，et al.Efficient storage of high throughput DNA sequencing data using reference-based compression ［J］.Genome Research，2011，21(5):734-740.

［14］Jones D，Ruzzo W，Peng X，et al.Compression of nextgeneration Sequencing reads aided by highly efficient de novo assembly［J］.Nucleic Acids Research，2012，40(22):e171.

［15］Christley S，Lu Y，Li C，et al.Human genomes as email attachments［J］.Bioinformatics，2009，25(2):274-275.

［16］Kent W J.BLAT:the BLAST-like alignment tool［J］.Genome Research，2002，12(4):656-664.

［17］Altschul S，Gish W，Miller W，et al.Basic local alignment search tool［J］.Journal of Molecular Biology，1990，215(3):403-410.

［18］Li H，Ruan J，Durbin R.Mapping short DNA sequencing reads and calling variants using mapping quality scores［J］.Genome Research，2008，18(11):1851-1858.

［19］Li H，Durbin R.Fast and accurate short read alignment with burrows-wheelertransform ［J］.Bioinformatics，2009，25(14):1754-1760.

［20］Brandon M C，Wallace D C，Baldi P.Data structures and compression algorithms for genomic sequence data［J］.Bioinformatics，2009，25(14):1731-1738.

［21］Zhu Z，Zhou J，Ji Z，et al.DNA sequence compression using adaptive particle swarm optimization-based memetic algorithm ［J］.IEEE Transactions on Evolutionary Computation，2011，15(5):643-658.

［22］Korodi G，Tabus I.An efficient normalized maximum likelihood algorithm for DNA sequence compression ［J］.ACM Transactions on Information Systems，2005，23(1):3-34.

［23］Korodi G，Tabus I.Normalized maximum likelihood model of order-1 for the compression of DNA sequences［C］// Data Compression Conference. Snowbird(USA):IEEE Computer Society，2007:33-42.

［24］Kuruppu S，Puglisi S J，Zobel J.Relative Lempel-Ziv compression ofgenomes forlarge-scale storage and retrieval［C］//in proceedings of the 17th International Symposium on String Processing and Information Retrieval.Los Cabos:Springer，2010:201-206.

［25］Kuruppu S，Puglisi S J，Zobel J.Optimized relative Lempel-Ziv compression of genomes［C］//Proceedings of Australasian Computer Science Conference.Perth(Australia):Australasian Computer Science，2011:91-98.

［26］Wang C，Zhang D.A novel compression tool for efficient storage of genome resequencing data［J］.Nucleic Acids Research，2011，39(7):E45-U74.

［27］Miller J R，Koren S，Sutton G.Assembly algorithms for next generation sequencing data ［J］.Genomics，2010，95(6):315-327.

［28］Pevzner P A，Tang H，Waterman M S.An Eulerian path approach to DNA fragment assembly ［J］.PNAS，2001，98(17):9748-9753.

［29］Li R Q，Zhu H M，Ruan J，et al.De novo assembly of human genomes with massively parallel short read sequencing ［J］.Genome Research，2010，20(2)，265-272.

［30］Tembe W，Lowey J，Suh E.G-SQZ:compact encoding of genomic sequence and quality data［J］.Bioinformatics，2010，26(17):2192-2194.

［31］Deorowicz S，Grabowski S.Compression of DNA sequence reads in FASTQ format［J］.Bioinformatics，20 11，27(6):860-862.

［32］Popitsch N，Haeseler A V.NGC:lossless and lossy compression of aligned high throughput sequencing data［J］.Nucleic Acids Research，2012，41(1):e27.

［33］Kuruppu S S.Compression of Large DNA Databases［D］.Melbourne:Melbourne School of Engineering，2012.

［34］FerraginaP，Manzini G.Opportunistic data structures with applications［C］//Proceedings of the 41st Annual Symposium on Foundations of Computer Science.Redondo Beach:IEEE Computer Society，2000:390-398.

［35］Makinen V，Navarro G.Succinct suffix arrays based on run-length encoding［C］//In Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching.Jeju Island(Korea):Springer，2005:40-66.

［36］Grossi R，Vitter J S.Compressed suffix arrays and suffix trees with applications to text indexing and string matching［J］.SIAM Journal on Computing，2005，35(2):378-407.

［37］Siren J，Valimaki N，Makinen V，et al.Run-length compressed indexes are superior for highly repetitive sequence collections［C］//String Processing and Information Retrieval.Berlin:Springer，2009:164-175.

［38］Karkkainen E，Ukkonen.Lempel-Ziv parsing and sublinearsize index structures for string matching［C］//Proceedings of the 3rd South American Workshop on String Processing.Belo Horizonte(Brazil):World Scientific Publishing Company Incorporated，1996:141-155.

［39］Kreft S，Navarro G.Self-Indexing based on LZ77 ［C］//In Proceedings of the 22th Annual Symposium on Combinational PatternMatching. Palermo(Italy):Springer，2011:41-54.

［40］Bao S，Jiang R，Kwan W，et al.Evaluation of nextgeneration sequencing software in mapping and assembly［J］.Journal of Human Genetics，2011，56(9):406-414.

［41］SteinL D.The case for cloud computing in genome informatics ［J］.Genome Biology，2010，11(5):207.

［42］Ansorge W J.Next-generation DNA sequencing techniques［J］.New Biotechnology，2009，25(4):195-203.

［43］Horner D S，Pavesi G，Castrignano T，et al.Bioinformatics approaches for genomics and post genomics applications of next generation sequencing［J］.Briefings in Bioinformatics，2010，11(2):181-197.

［44］Morozova O，Marra M A.Applications of next-generation sequencing technologies in functional genomics［J］.Genomics，92(5):255-264.

［45］Yang X，Charlebois P，Gnerre S，et al.De novo assembly ofhighly diverse viralpopulations［J］.BMC Genomics，2012，13:475.