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

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

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

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

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

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

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

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

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

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

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

2.1 重測序DNA序列壓縮

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.2 代表算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

展 望

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

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

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

DNA測序技術(shù)不斷推動生物工程和醫(yī)學(xué)等相關(guān)領(lǐng)域的發(fā)展［42］，在高速和低價的前提下，為醫(yī)學(xué)研究和診斷學(xué)等領(lǐng)域的廣泛應(yīng)用提供了可能.基因組學(xué)、功能基因組學(xué)和新病毒機理等領(lǐng)域的進步均得益于DNA測序的發(fā)展［43-45］.解決好高通量DNA測序數(shù)據(jù)存儲和傳輸問題是推動這些領(lǐng)域進一步發(fā)展的前提.未來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］.計算機應(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.