孟 倩

(復(fù)旦大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

基于高通量測序的短序列生物數(shù)據(jù)壓縮研究

孟 倩

(復(fù)旦大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

高通量測序技術(shù)(NGS)的發(fā)展帶來了測序數(shù)據(jù)量的極速增長，給數(shù)據(jù)的存儲和傳輸帶來了極大的壓力。數(shù)據(jù)壓縮技術(shù)是解決這個問題的重要方法。傳統(tǒng)的壓縮方法并沒有很好地利用數(shù)據(jù)本身的特性。因此，計算機(jī)學(xué)者們關(guān)注于NGS測序數(shù)據(jù)專用的壓縮方法。全面總結(jié)針對高通量測序技術(shù)產(chǎn)生的Fastq和Fasta數(shù)據(jù)的壓縮算法，介紹了Fastq和Fasta數(shù)據(jù)的特點(diǎn)，總結(jié)了目前常用的壓縮方法。并通過不同物種、不同測序平臺、不同規(guī)模的測序數(shù)據(jù)對多個具有代表性的壓縮工具進(jìn)行測試，比較它們的壓縮性能并且驗(yàn)證相應(yīng)的工具特點(diǎn)，為研究人員提供工具選擇指導(dǎo)或改善工具性能提供幫助。最后總結(jié)闡述短序列數(shù)據(jù)壓縮工具存在的問題和發(fā)展趨勢。

數(shù)據(jù)壓縮 短序列數(shù)據(jù)壓縮 高通量測序

0 引 言

測序是對生命中的基本元素{ACGT}及其修飾和衍生物進(jìn)行測定和解讀。20世紀(jì)誕生的第一代測序技術(shù)Sanger測序技術(shù)能對幾百到幾千的DNA片段進(jìn)行快速準(zhǔn)確的讀取，這直接促成了人類歷史上一項(xiàng)偉大的計劃—人類基因組計劃(HPG)的誕生，它對人類30億堿基進(jìn)行測序，耗資30億美金，前后耗時10余年，涉及6個國家，最終于2001年公布草圖。2005年以后出現(xiàn)的高通量測序技術(shù)(High-Throughput Sequencing)，也叫下一代測序技術(shù)(Next-Generation Sequencing)或深度測序，是生命科學(xué)領(lǐng)域內(nèi)的一項(xiàng)重要的技術(shù)變革，給個人全基因組測序帶來了可能。主要以Illumina 公司的Solexa基因組分析儀，Roche公司的454測序儀和ABI公司的SOLiD測序儀為代表，又以Illumina應(yīng)用最廣，它可以同時處理幾百萬到幾億的基因數(shù)據(jù)，成本低，效率高，速度快。第三代測序相比于第二代測序在成本和效率上并沒有顯著的提高。因此，市場上還是以第二代測序儀為主。高通量測序的低成本和高效率，也在產(chǎn)生海量的測序數(shù)據(jù)。計算機(jī)是存儲和處理這些數(shù)據(jù)的重要工具。但是數(shù)據(jù)量的增長速度還是遠(yuǎn)超過計算機(jī)的存儲能力，這給數(shù)據(jù)的存儲帶來了極大的壓力。同時，這些測序數(shù)據(jù)需要傳輸，但是帶寬的增長速度也是遠(yuǎn)遠(yuǎn)無法滿足需求。如何存儲與傳輸大量的測序數(shù)據(jù)，已經(jīng)成為了測序領(lǐng)域的重要問題。

數(shù)據(jù)壓縮是有效解決測序數(shù)據(jù)帶來的存儲和傳輸問題的一種重要方法。通用的壓縮方法如bzip、gzip、LZMA等對數(shù)據(jù)的壓縮結(jié)果并不是特別理想，并沒有充分利用生物數(shù)據(jù)本身的特點(diǎn)。因此，計算機(jī)學(xué)者們開始關(guān)注于NGS測序數(shù)據(jù)專用的壓縮方法。

NGS測序數(shù)據(jù)主要包括原始測序數(shù)據(jù)Fastq數(shù)據(jù)，拼接數(shù)據(jù)Fasta和比對數(shù)據(jù)SAM/BAM數(shù)據(jù)，以及變異文件VCF。

本文較全面地對目前流行的NGS的短序列Fastq和Fasta格式的數(shù)據(jù)壓縮方法進(jìn)行分類總結(jié)，并通過真實(shí)的序列數(shù)據(jù)對幾種壓縮方法進(jìn)行測試評估，比較其壓縮性能。最后討論目前的方法存在的問題和未來的發(fā)展趨勢。

1 數(shù)據(jù)格式

1.1 Fastq格式

Fastq格式是NGS測序出來的原始數(shù)據(jù)格式。Fastq格式的序列一般有4行。第一行是元數(shù)據(jù)，由‘@’開始，后面跟著序列的描述信息，通常被認(rèn)為是標(biāo)志行。第二行是序列，由{ACGTN}組成，其中N代表不確定，表示該位置可能是ACG或T。第三行由‘+’開始，后面也可以跟著序列的描述信息，通常和@后面的內(nèi)容一樣。第四行是第二行序列的質(zhì)量評價，因此字符數(shù)和第二行一樣，表示對應(yīng)堿基的錯誤概率的相關(guān)信息，越大代表錯誤概率越低，通常用ASCII表示。對Fastq格式的壓縮包括對元數(shù)據(jù)、序列和質(zhì)量分?jǐn)?shù)三者的壓縮。

1.2 Fasta格式

Fasta格式通常有兩行。第一行由‘@’開始，后面跟著序列的描述信息，通常被認(rèn)為是標(biāo)志行?？赡馨▋x器名，測序平臺，短讀的標(biāo)識等信息。第二行是序列，序列信息通常由ACGT四個堿基組成，有時會有N代表不確定該位置是ACG還是T。僅從數(shù)據(jù)內(nèi)容的格式上而言，相比于Fastq格式數(shù)據(jù)，它缺少了Fastq格式中的第三行和第四行內(nèi)容，因此相比于Fastq格式壓縮，它的壓縮算法主要是集中于對元數(shù)據(jù)和序列的壓縮。

2 NGS數(shù)據(jù)的壓縮技術(shù)

現(xiàn)有的NGS數(shù)據(jù)壓縮算法主要可以分為兩類：基于參考基因組壓縮以及非基于參考基因組壓縮。在對生物數(shù)據(jù)壓縮的過程中，大多數(shù)的壓縮工具采用了對數(shù)據(jù)的各個部分(元數(shù)據(jù))分別壓縮的方式。對每個部分可能采取不同的壓縮策略和方法。常用的壓縮方法可歸類為字典編碼、熵編碼和變換變換。字典編碼是利用字典把每個字符串編碼為一個標(biāo)識，字典保存字符串，可以是靜態(tài)的，也可以是動態(tài)(自適應(yīng))的[1]，如增量編碼、LZ等。熵編碼在NGS中有很多運(yùn)用，典型的熵編碼有：算術(shù)編碼、哈夫曼編碼、游程長度編碼、馬爾可夫模型等。變換編碼包括經(jīng)典的BWT(Burrows-Wheeler Transformation)算法[2]、聚類算法等，通過變換編碼，把相似字符聚集在一起，方便后續(xù)的游程長度編碼或者M(jìn)TF(Move To Front)進(jìn)行壓縮，達(dá)到較好的壓縮率。

2.1 元數(shù)據(jù)

ID部分是數(shù)據(jù)的標(biāo)志行。常常存儲數(shù)據(jù)的編號，測序平臺等信息。有些信息譬如說儀器名等信息會在每個短讀中都大量出現(xiàn)，這就造成了大量冗余。考慮到這些冗余信息，常常把數(shù)據(jù)分為固定的部分和可變部分兩部分進(jìn)行壓縮，采用增量編碼的方式來進(jìn)行，例如QUIP[3]、FQC[4]等都是采用的這種方法。QUIP是把數(shù)據(jù)和上一條數(shù)據(jù)進(jìn)行比較，對完全相同的部分、有規(guī)則的數(shù)字符號和無規(guī)則的數(shù)字符號采用不同的壓縮方案。FASTQZ[5]的快速模式也采用了相似的概念來進(jìn)行壓縮，存儲差異信息，包括差異數(shù)據(jù)的位置和差異類型以及差異數(shù)據(jù)。

有些算法采用了K階馬爾科夫模型也叫有限上下文模型的方式來對該部分進(jìn)行壓縮。在使用馬爾科夫模型的時候，要注意階數(shù)的選擇，減少內(nèi)存消耗。階數(shù)越多，對數(shù)據(jù)的預(yù)測準(zhǔn)確率越高，但是對內(nèi)存的消耗也會越大。例如如果字符集為256個字符，K階馬爾科夫模型的每一次預(yù)測都有256k個參數(shù)。因此k的選擇要兼顧到內(nèi)存和壓縮率，需要在兩者之間找到一個平衡點(diǎn)。例如FASTQZ的慢速方法就是采用了混合有限上下文模型，把4種上下文模型按照一定的權(quán)重比例組合起來來減少預(yù)測錯誤率，提高壓縮率。MFCompress[6]算法利用了連續(xù)的元數(shù)據(jù)有極大的關(guān)聯(lián)性的特點(diǎn)，借助于要壓縮元素之前的位置和要壓縮元素所在短讀的上一條短讀的相關(guān)位置的關(guān)聯(lián)性，采用了有限上下文模型。同時考慮到壓縮率和內(nèi)存的平衡，在壓縮前先對元數(shù)據(jù)的不同的元素個數(shù)進(jìn)行了統(tǒng)計，根據(jù)不同元素個數(shù)的大小來確定階數(shù)。準(zhǔn)確地說是大于50時，選擇3階模型，小于時選擇4階模型。

BEETL[7]算法認(rèn)為該部分信息只是作為一個短讀的唯一標(biāo)識，因此為了提高壓縮率，獲得更好的壓縮效果，選擇拋棄這部分信息，改為在解壓縮的時候根據(jù)短讀內(nèi)容生成它的唯一標(biāo)識。DSRC2[8]算法可由用戶選擇對元數(shù)據(jù)采用有損壓縮還是無損壓縮。

2.2 序 列

序列是Fastq數(shù)據(jù)中最核心的信息，不能接受任何的信息損失，因此序列的壓縮都是無損壓縮。對序列的壓縮策略包括：

(1) 利用和質(zhì)量分?jǐn)?shù)的一對一關(guān)系，對序列進(jìn)行處理，使得序列數(shù)據(jù)更容易壓縮。例如Fastqz算法利用了序列中的N和質(zhì)量分?jǐn)?shù)之間的對應(yīng)關(guān)系，N在質(zhì)量分?jǐn)?shù)中一般都為0。因此它在處理序列的時候，直接刪除所有的N元素，解壓縮的時候在質(zhì)量分?jǐn)?shù)中為0的地方在對應(yīng)的序列中插入N。

(2) 利用同一條數(shù)據(jù)間的相關(guān)性，采用k階馬爾科夫模型。QUIP[3]算法直接采用了12階馬爾科夫模型，12階馬爾科夫模型需要32bit來存儲中間參數(shù)。

(3) 用BWT或者聚類算法處理數(shù)據(jù)，使得相似數(shù)據(jù)聚集在一起，更容易被壓縮。BEETL[7]算法是典型的基于BWT算法進(jìn)行改進(jìn)的針對高通量測序技術(shù)的壓縮算法。

更多的算法是對這幾種策略進(jìn)行部分修改后疊加。DSRC[9]以及DSRC2中的一種壓縮策略也是采用了這種方法，把所有的非ACGT都轉(zhuǎn)移到質(zhì)量分?jǐn)?shù)上，這樣序列中只有ACGT四個字符。在接下來的壓縮中，可以采用每個字符用2bit來表示，也可以采用哈夫曼編碼，也可以采用算術(shù)編碼和有限上下文模型。MFCompress[6]先對序列數(shù)據(jù)進(jìn)行預(yù)處理，然后再采用混合有限上下文模型來進(jìn)行壓縮。對數(shù)據(jù)的預(yù)處理是將序列分為2個或者3個流程來單獨(dú)處理。主流程的目的是使得該流程中只有0123四個元素，因此它把ACGT和acgt都替換成0123，所有非ACGT部分全部用0來替換。然后再用extrastream來標(biāo)注所有的0代表的含義，因?yàn)樾蛄兄幸话惴茿CGT部分很少，因此這樣做可以有效減少壓縮量。最后再用一個流程來區(qū)分大小寫。

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

QUIP采用了4階馬爾可夫模型，主要是因?yàn)橘|(zhì)量分?jǐn)?shù)中有四十多個不同的字符，當(dāng)階數(shù)越高，參數(shù)越多，而這限制了馬爾科夫模型的階數(shù)。KungFq[10]和FQZip[11]采用了采用了游程長度編碼。LWFQZip[12]采用了限制游程長度編碼，限制游程長度編碼是對游程長度編碼的一點(diǎn)改進(jìn)。文獻(xiàn)[13]在質(zhì)量分?jǐn)?shù)的壓縮中，觀察到“#”號出現(xiàn)以后一般后面就不會有別的質(zhì)量分?jǐn)?shù)。因此它去除了所有的“#”號以節(jié)省壓縮數(shù)據(jù)量。同時它考慮到直接運(yùn)用哈夫曼編碼效率不高，因此把質(zhì)量分?jǐn)?shù)切割成k-mer大小的塊，對每一塊進(jìn)行或者哈夫曼或者游程長度編碼，具體由壓縮率來決定。

NGC[14]算法是對匹配成功的質(zhì)量分?jǐn)?shù)和未匹配成功的質(zhì)量分?jǐn)?shù)采用了不同的壓縮方案。FQC算法是采用了有損和無損壓縮兩個選擇，無損壓縮是對數(shù)據(jù)采用游程長度編碼后再采用ppmd[15]壓縮。在有損壓縮中，是直接根據(jù)壓縮率的需求度不同提供了三種壓縮率不同信息損失率不同的壓縮方案，第一級小于0 的用3來代替，大于3的奇數(shù)用偶數(shù)代替。第二級是小于3的用0來代替，大于3 的中每4個數(shù)用第2個數(shù)來代替。第三級是小于7的用0來代替，大于7的每8個數(shù)用第4個數(shù)來代替。但是它還提供了由有損壓縮文件和補(bǔ)充文件還原出原數(shù)據(jù)的方式，把壓縮過程中損失的信息單獨(dú)記錄，然后通過有損壓縮解壓后的文件和補(bǔ)充文件可以還原出原始文件，給后續(xù)數(shù)據(jù)傳輸帶來了極大的方便。QualComp[16]算法是基于率失真理論，對質(zhì)量分?jǐn)?shù)用一個固定的失真指標(biāo)量化到一個特定的比率中，以期望在對后續(xù)分析的影響和壓縮率之間取得一個平衡。

有損壓縮提高了壓縮效率，但是丟失了部分信息，這可能給后續(xù)的數(shù)據(jù)分析帶來挑戰(zhàn)。目前這種壓縮方法仍然面臨著巨大的挑戰(zhàn)。在近期涌現(xiàn)了很多優(yōu)秀的質(zhì)量分?jǐn)?shù)有損壓縮算法，如RQS[17]、QVZ[18]等。

2.4 數(shù)據(jù)轉(zhuǎn)換技術(shù)

數(shù)據(jù)轉(zhuǎn)換技術(shù)主要是指在數(shù)據(jù)壓縮之前，對數(shù)據(jù)進(jìn)行處理的技術(shù)。通過使用Burrows-WheelerTransformation(BWT)或者聚類算法等對數(shù)據(jù)進(jìn)行處理，使得相似的聚集在一起，然后再進(jìn)行壓縮，以達(dá)到提高壓縮率的結(jié)果。BEETL算法使用了BWT對輸入的數(shù)據(jù)先進(jìn)行了處理，使得文件更易于壓縮，然后使用通用的壓縮方法如7-zip，bizp2等對處理后的文件進(jìn)一步壓縮。SCALCE[19]算法通過局部一致性分析LocallyConsistentparsing(LCP)算法對有最大相同子串的數(shù)據(jù)識別后聚類，然后再用gzip等算法對數(shù)據(jù)進(jìn)行后續(xù)壓縮。

2.5 基于參考基因組壓縮算法

(1)Cpv是指施工項(xiàng)目在考核期內(nèi)，基于擬投入的安全成本，在確保計劃安全保障水平的基礎(chǔ)上安全成本的計劃費(fèi)用值。

同源基因組之間有很高的相似性，甚至可能高達(dá)99%。例如人類基因組，不同的人之間的基因相似度超過99.9%，而這些0.001 的不同就構(gòu)成了不同的個體。相比于相同信息，差異信息是極少量的。如果已經(jīng)有了同源基因組作為參考基因組，在已知參考基因組和差異信息的情況下，顯然可以還原出原始數(shù)據(jù)。因此，在有參考基因組的情況下，對基因組的存儲，就變成了對差異信息的存儲。編碼器只需要存儲差異信息，這極大的提高了壓縮率，節(jié)省了存儲空間和傳輸時間。

參考基因組的選擇可以是同源基因組，也可以是由自身拼接得到，基因組拼接技術(shù)也有很多，文獻(xiàn)[20]是對基因組拼接技術(shù)的綜述。

參考基因組壓縮需要記錄比對信息和差異信息，包括匹配位置、匹配長度、匹配類型、差異位置、差異類型和差異內(nèi)容。差異類型可分為插入、刪除和替代這三類。然后對這些記錄信息壓縮，可以采用哈夫曼編碼、算術(shù)編碼或者游程長度編碼等。

迄今為止，有很多的高通量測序壓縮算法采用了基于參考基因組壓縮的方式，如SlimGene[21]，QUIP，NGC，SAMZIP等。QUIP除了給出了基于參考基因組壓縮的方案，還給出了基于拼接的壓縮方式，是對deBruijin采用了dlCBF(d-leftcountingBloomFilter)改進(jìn)的拼接。基于參考基因組的拼接壓縮理論上而言也是基于參考基因組壓縮的方式。

2.6 并行處理

在對大數(shù)據(jù)進(jìn)行壓縮和解壓縮的時候，時間成為了一個不可忽略的評判因素。MFCompress為了減少數(shù)據(jù)壓縮和解壓縮時間，把數(shù)據(jù)分割成幾塊來并行處理，一般而言壓縮是雙線程處理。但是解壓縮的時候，線程數(shù)量可以由用戶自己來決定。它把數(shù)據(jù)并行處理后再合并處理，達(dá)到了提高壓縮時間的目的，同時也能有效地利用了計算機(jī)資源。

3 壓縮算法性能評估

在這一節(jié)中，我們選擇了4個數(shù)據(jù)用于測試現(xiàn)有的主要的fastq和fasta數(shù)據(jù)壓縮算法的壓縮率和壓縮時間。我們選擇不同物種(人類，小鼠，微生物)，來自于不同的數(shù)據(jù)的數(shù)據(jù)平臺(Illumina,454)和不同的大小(從217MB到12GB)。所有數(shù)據(jù)來自于http://sra.dnanexus.com/，通過sratoolkithttp://trace.ncbi.nlm.nih.gov/Traces/sra/sra.cgi?view=software工具轉(zhuǎn)換成fastq格式。數(shù)據(jù)如表1所示。

表1 測試數(shù)據(jù)集

測試環(huán)境采用64位Ubuntu14.04操作系統(tǒng)，硬件平臺為4核8線程的3.5GHzIntel(R)Core(TM)i7-4770KCPU，16GB內(nèi)存。在測試中盡量不運(yùn)行別的程序。

首先我們對FASTQZ、QUIP、DSRC2、SCALCE和BEETL方法進(jìn)行了壓縮。表2展示的是對fastq格式數(shù)據(jù)壓縮的結(jié)果，未做標(biāo)注的都是采用默認(rèn)壓縮模式。SRR001540是由變長的454 數(shù)據(jù)組成，BEETL不能壓縮變長的數(shù)據(jù)。也就是不能壓縮SRR001540。但是我們對數(shù)據(jù)進(jìn)行了格式化處理，所有短讀統(tǒng)一長度為200。SOLiD數(shù)據(jù)格式和Illumina數(shù)據(jù)格式不一樣，它含有的是Colorspace而并不是堿基ACGT。很多算法都不支持SOLiD格式數(shù)據(jù)，例如QUIP方法，這里我們沒有選擇SOLiD格式數(shù)據(jù)做測試數(shù)據(jù)。所有的壓縮算法都支持Illumina平臺測序的fastq格式數(shù)據(jù)。表中，我們對DSRC2 的三種運(yùn)行模式都跑了一遍，三種模式分別對應(yīng)速度最快、居中以及壓縮率最好。從表中可以看出來，在FASTQZ、SCALCE、QUIP、DSRC2，BEETL這幾個壓縮方法里面，BEETL的壓縮效率相比于別的幾個壓縮算法，壓縮率有個很明顯的不正常，這主要是因?yàn)锽EETL采用的是ASCII碼格式存儲。BEETL算法提供了兩種存儲格式，另一種存儲格式的壓縮率很好，大約是ASCII碼格式的1/8，但是解壓縮需要還原成ASCII碼格式后才可以。同時BEETL壓縮解壓縮以后，我們發(fā)現(xiàn)它是元數(shù)據(jù)有損的無損壓縮。除了元數(shù)據(jù)部分以外，序列和質(zhì)量分?jǐn)?shù)都是無損。其他的幾種算法都是無損壓縮，經(jīng)過壓縮和解壓縮還原以后的數(shù)據(jù)和原數(shù)據(jù)完全一致。同時，在實(shí)際運(yùn)行中，發(fā)現(xiàn)BEETL對內(nèi)存消耗很大。SCALCE算法結(jié)果也對整個數(shù)據(jù)進(jìn)行了修改，元數(shù)據(jù)部分被改變了，同時解壓后的文件是以序列和對應(yīng)的質(zhì)量分?jǐn)?shù)為一組的亂序排列，盡管數(shù)據(jù)本身除了元數(shù)據(jù)部分以外并沒有丟失。幾種算法中FASTQZ壓縮效果最好，可能是因?yàn)镕ASTQZ中采用了很高效的混合有限上下文模式，并且在采用這個模式之前還對數(shù)據(jù)進(jìn)行了處理，把所有的”N” 都傳遞給質(zhì)量分?jǐn)?shù)進(jìn)行壓縮，減少了對數(shù)據(jù)N的壓縮，而這有效地提高了壓縮效率。

表2 FASTQ格式數(shù)據(jù)壓縮算法的壓縮率結(jié)果圖

表3是針對Fasta格式進(jìn)行壓縮的壓縮率實(shí)驗(yàn)結(jié)果。BEETL因?yàn)橥瑯拥脑蛩詨嚎s率看起來比較差。在剩下來的兩種方法中，我們可以明顯看出MFCompress的壓縮效果要好于Deliminate方法?？赡苁且?yàn)镸FCompress方法本身也是在應(yīng)用混合的有限上下文壓縮之前先對數(shù)據(jù)進(jìn)行了處理，有效減少了要壓縮的數(shù)據(jù)量。而無論是混合有限上下文模型還是數(shù)據(jù)預(yù)處理，都對壓縮率的提高帶來了極大的幫助。MFCompress壓縮的三種模式的壓縮率不同也證明了階數(shù)越高，壓縮率越好。

表3 FASTA格式數(shù)據(jù)壓縮的壓縮率結(jié)果

我們還選取DSRC2來比較有損壓縮和無損壓縮的區(qū)別。如表4所示。相比于無損壓縮，有損壓縮的壓縮率表現(xiàn)會好很多。

表4 DSRC2的有損和無損壓縮結(jié)果

在某些場景下，比如數(shù)據(jù)只是存儲在本地，同時需要不斷地壓縮和解壓縮的時候，壓縮時間比壓縮率更重要。在壓縮率上，表5和表6展示了各個壓縮方案的壓縮時間結(jié)果圖。時間是采用Linux命令time直接得到得的real時間，單位為秒。

表5 FASTQ格式數(shù)據(jù)壓縮時間

表6 FASTA格式數(shù)據(jù)壓縮時間

從表5 中我們可以看到DSRC2的壓縮耗時明顯小于別的幾個壓縮算法，相比于通用壓縮算法gzip，DSRC2所耗時間也并不遜色。表6中可以看到這幾種壓縮算法的耗時都很長。尤其是BEETL方法，可能是因?yàn)锽EETL是基于BWT算法改進(jìn)的壓縮方法，BWT 算法耗時很長，內(nèi)存消耗也很大。

總體上而言，如果注重壓縮率，不太重視壓縮和解壓縮時間，比如數(shù)據(jù)需要進(jìn)行傳輸，或者數(shù)據(jù)壓縮解壓縮的次數(shù)比較少，針對fastq格式壓縮，可以考慮FASTQZ方法或者BEETL方法，具體的可以根據(jù)需求來選擇。如果注重壓縮時間，可以采用DSRC2方法。在對FASTA格式進(jìn)行壓縮，可以考慮MFCompress的不同參數(shù)來選擇偏向壓縮時間還是壓縮率?；蛘咭部梢圆捎肂EETL方法。

4 結(jié) 語

針對高通量測序技術(shù)產(chǎn)生的fastq格式短序列生物數(shù)據(jù)，計算機(jī)學(xué)者們開發(fā)了很多相應(yīng)的壓縮工具并取得了一定的成果。本文對現(xiàn)有的壓縮方法進(jìn)行了介紹并比較了它們的壓縮性能。生物學(xué)者可以根據(jù)各自的需求選擇相應(yīng)的壓縮工具。但是可以看出現(xiàn)有的壓縮工具仍然存在著問題，計算機(jī)資源和數(shù)據(jù)存儲量之間的不匹配問題也仍然存在。下面是對這些問題的闡述以及可能的解決途徑：

(1) 壓縮和解壓縮時間問題。目前的壓縮工具在壓縮/解壓縮時間上耗時過大，并行處理可以很好地提高壓縮速率。但是仍然需要計算機(jī)學(xué)者們提供一個速度快，壓縮率高的壓縮算法。

(2) 發(fā)展性問題。如同sanger測序發(fā)展到高通量測序技術(shù)，測序技術(shù)在不斷更新，第三代測序采用了基于納米孔的單分子測序方法，這將會產(chǎn)生更優(yōu)質(zhì)的短片段序列，壓縮算法也需要不斷適應(yīng)生物測序技術(shù)的發(fā)展。

(3) 計算機(jī)資源消耗問題。數(shù)據(jù)的增大對計算資源帶來了挑戰(zhàn)，在數(shù)據(jù)壓縮狀態(tài)進(jìn)行數(shù)據(jù)的查詢、提取和檢索分析將極大的緩解對資源的壓力。

測序技術(shù)推動著生物醫(yī)學(xué)領(lǐng)域的發(fā)展，是生命科學(xué)領(lǐng)域內(nèi)一項(xiàng)重要的技術(shù)變革。生物數(shù)據(jù)壓縮的發(fā)展能很好地解決計算機(jī)資源和生物數(shù)據(jù)量不匹配的問題，減少存儲和傳輸?shù)南?，推動生物醫(yī)學(xué)領(lǐng)域的進(jìn)一步發(fā)展。但是現(xiàn)在面臨的挑戰(zhàn)仍然很多，仍需要更好的短序列壓縮方法，來解決這些問題。

[1] Salomon D.Data Compression:The Complete Reference[M].Springer-Verlag New York,Inc.,2000.

[2] Burrows M.A block-sorting lossless data compression algorithm[J].Technical Report Digital Src Research Report,1994,57(4):425.

[3] Jones D C,Ruzzo W L,Xinxia P,et al.Compression of next-generation sequencing reads aided by highly efficient de novo assembly[J].Nucleic Acids Research,2012,40(22):2364-2367.

[4] Anirban Dutta,Mohammed Monzoorul Haque,Tungadri Bose,et al.FQC:A novel approach for efficient compression,archival,and dissemination of fastq datasets[J].Journal of Bioinformatics & Computational Biology,2015,13(3).

[5] Bonfield J K,Mahoney M V.Compression of FASTQ and SAM Format Sequencing Data[J].Plos One,2013,8(3):1453-1456.

[6] Pinho A J,Diogo P.MFCompress:a compression tool for FASTA and multi-FASTA data[J].Bioinformatics,2014,30(1):117-118.

[7] Cox A J,Bauer M J,Jakobi T,et al.Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform[J].Bioinformatics,2012,28(11):1415-9.

[9] Deorowicz S,Grabowski S.Compression of DNA sequence reads in FASTQ format[J].Bioinformatics,2011,27(6):860-862.

[10] Grassi E,Di Gregorio F,Molineris I.KungFQ:A simple and powerful approach to compress fastq files[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB),2012,9(6):1837-1842.

[11] Zhang Y,Li L,Xiao J,et al.FQZip:Lossless Reference-Based Compression of Next Generation Sequencing Data in FASTQ Format[C]//Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems-Volume 2.Springer International Publishing,2015:127-135.

[12] Zhang Y,Li L,Yang Y,et al.Light-weight reference-based compression of FASTQ data[J].Bmc Bioinformatics,2015,16(1):1-8.

[13] Nicolae M,Pathak S,Rajasekaran S.LFQC:a lossless compression algorithm for FASTQ files[J].Bioinformatics,2014,31(20).

[14] Popitsch N,von Haeseler A.NGC:lossless and lossy compression of aligned high-throughput sequencing data[J].Nucleic acids research,2013,41(1):e27-e27.

[15] Shkarin D.PPM:One step to practicality[C]//Data Compression Conference,2002.Proceedings.DCC 2002.IEEE,2002:202-211.

[16] Ochoa I,Asnani H,Bharadia D,et al.QualComp:a new lossy compressor for quality scores based on rate distortion theory[J].Bmc Bioinformatics,2013,14(1):1-16.

[17] Wan R,Anh V N,Asai K.Transformations for the compression of FASTQ quality scores of next-generation sequencing data[J].Bioinformatics,2012,28(5):628-635.

[18] Malysa G,Hernaez M,Ochoa I,et al.QVZ:lossy compression of quality values[J].Bioinformatics,2015,31(19):3122.

[19] Hach F,Numanagic I,Alkan C,et al.SCALCE:boosting sequence compression algorithms using locally consistent encoding[J].Bioinformatics,2012,28(23):3051-3057.

[20] 曾培龍.基于reads引導(dǎo)的基因組序列拼接[D].哈爾濱工業(yè)大學(xué),2012.

[21] Kozanitis C,Saunders C,Kruglyak S,et al.Compressing Genomic Sequence Fragments Using SlimGene[J].Journal of Computational Biology,2011,18(3):310-324.

RESEARCH ON DATA COMPRESSION OF SHORT-SEQUENCE BIOLOGICAL DATA BASED ON NEXT-GENERATION SEQUENCING

Meng Qian

(SchoolofComputerScience,FudanUniversty,Shanghai200433,China)

Due to the development of next-generation sequencing technology (NGS), the rapid growth of sequential data has brought a heavy pressure to data storage and transmission. The data compression technique is an important method to solve this problem, but traditional compression methods do not exploit the characteristics of the data well. Therefore, scholars begin to focus on the compression algorithm which is the special one for NGS data. In this paper, we present a comprehensive summary of compression algorithms for the Fastq and Fasta data obtained from NGS. We introduce the features of Fastq and Fasta, and summarize the commonly used methods of sequential data compression. Then we evaluate these representative compression tools through tests on several data sets from various scales, species and sequencing platforms, in order to compare the compression performance and validate the characteristics so that they can support researchers as a guide for algorithm selection and improvement. Finally, some problems and the trends of short-sequence data compression algorithms are also proposed in this paper.

Data compression Short-sequence data compression Next-generation sequencing

2016-03-05。孟倩，碩士生，主研領(lǐng)域：生物信息學(xué)。

TP391

A

10.3969/j.issn.1000-386x.2017.04.005