【摘要】：基因測(cè)序技術(shù)的迅猛發(fā)展使得測(cè)序成本直線下降,測(cè)序數(shù)據(jù)規(guī)模急劇攀升,為數(shù)據(jù)分析及使用帶來(lái)諸多不便。FASTQ格式是目前應(yīng)用最廣泛的測(cè)序數(shù)據(jù)存儲(chǔ)格式之一,因此有必要設(shè)計(jì)針對(duì)FASTQ格式文件的壓縮算法,從而實(shí)現(xiàn)測(cè)序數(shù)據(jù)的高效存儲(chǔ)及傳輸。本文提出一種FASTQ文件無(wú)損壓縮算法FTComp,該算法分兩階段處理FASTQ文件。第一階段是FASTQ文件的預(yù)處理部分,算法根據(jù)文件格式特征,對(duì)數(shù)據(jù)進(jìn)行分類提取,生成標(biāo)識(shí)符序列、DNA序列以及質(zhì)量分?jǐn)?shù)序列。針對(duì)標(biāo)識(shí)符序列,算法對(duì)所有標(biāo)識(shí)符序列進(jìn)行分區(qū),根據(jù)區(qū)域文本特征為其匹配相應(yīng)數(shù)據(jù)處理方式;針對(duì)DNA序列,FTComp算法結(jié)合分組編碼以及游程編碼對(duì)序列進(jìn)行編碼處理;針對(duì)質(zhì)量分?jǐn)?shù)序列,算法使用游程編碼思想對(duì)序列進(jìn)行預(yù)處理。FTComp算法在第二階段使用本文提出的無(wú)損壓縮算法HyBWT作為壓縮器,對(duì)第一階段產(chǎn)生的數(shù)據(jù)進(jìn)行二次壓縮。HyBWT算法首先對(duì)文本進(jìn)行BWT變換,并對(duì)變換后的文本構(gòu)建小波樹以進(jìn)行簡(jiǎn)明表示,最后算法使用混合編碼壓縮小波樹節(jié)點(diǎn),從而完成FTComp算法第二階段的數(shù)據(jù)壓縮及存儲(chǔ)。本文實(shí)驗(yàn)內(nèi)容分為兩部分,包括算法參數(shù)對(duì)文件壓縮比的影響以及FTComp算法與其他算法的性能對(duì)比測(cè)試。實(shí)驗(yàn)首先測(cè)試小波樹的樹形及其節(jié)點(diǎn)位向量塊大小對(duì)文件壓縮比的影響。實(shí)驗(yàn)結(jié)果表明,由于FASTQ文件所包含的三種序列數(shù)據(jù)特征不同,應(yīng)分別為其選擇合適的參數(shù)設(shè)置以達(dá)到較高的文件壓縮比。算法性能對(duì)比測(cè)試所選五種算法包括兩種經(jīng)典的文本壓縮算法Gzip和Bzip2,以及三種目前行業(yè)領(lǐng)先的針對(duì)FASTQ文件的無(wú)損壓縮算法DSRC2、Quip以及LFQC。實(shí)驗(yàn)對(duì)比六種算法在八組FASTQ文件數(shù)據(jù)中的文件壓縮比、壓縮速度以及解壓縮速度。實(shí)驗(yàn)結(jié)果表明,FTComp算法在文件壓縮比方面表現(xiàn)較為優(yōu)異,壓縮后空間占用平均減少約80%,該結(jié)果與LFQC算法十分接近,并且超過(guò)DSRC2以及Quip這兩種達(dá)到工業(yè)級(jí)的FASTQ文件無(wú)損壓縮算法,經(jīng)典的文本壓縮算法Gzip以及Bzip2表現(xiàn)不佳,FTComp算法與之相比優(yōu)勢(shì)明顯;在壓縮速度以及解壓縮速度方面,FTComp算法均表現(xiàn)穩(wěn)定,并且遠(yuǎn)超LFQC算法,約是其5至10倍。
【圖文】：

FTCnmn登沙樁擎

Algorithm 3.2 7bitCompress(x)1 curvalue x, ans 02 for i 1 to 5 do3 curleft7 curvalue & 0x3f4 curvalue curvalue >> 75 if (curvalue = 0) then6 ans ans + curleft77 return ans8 else ans ans + (curleft7 + 128)圖 3.3 舉例說(shuō)明算法 3.2 過(guò)程，對(duì)于 F7中的值 x = 1716(10)= 11010110100(2)，入其第 0 到第 6 位，即 curleft7 = 00110100(2)，將 x 右移 7 比特，，得到 curval001101(2)，curvalue 不為 0，因此當(dāng)前字節(jié) curleft7 的最高位寫入 1，即 curle110100(2)，將該字節(jié)存入字符串 ans；重復(fù)上述操作，此時(shí) curleft7 = 00001101value = 0，則當(dāng)前字節(jié)的最高位寫入 0，可得 curleft7 = 00001101(2)，ans += cur0110100(2)+ 00001101(2)，程序結(jié)束。
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：O157.4

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張偉鋒;郭建利;;測(cè)繪矢量數(shù)據(jù)無(wú)損壓縮算法的實(shí)驗(yàn)研究[J];科技信息;2011年14期

2 鄭凱梅,余生晨;基于小波變換的心電信號(hào)準(zhǔn)無(wú)損壓縮算法[J];山東生物醫(yī)學(xué)工程;2003年02期

3 段然;趙榮;;點(diǎn)類幾何數(shù)據(jù)無(wú)損壓縮算法的研究[J];電腦知識(shí)與技術(shù);2010年22期

4 李雷定;馬鐵華;尤文斌;;常用數(shù)據(jù)無(wú)損壓縮算法分析[J];電子設(shè)計(jì)工程;2009年01期

5 孔月萍;耿燁;;有序抖動(dòng)半調(diào)圖像的無(wú)損壓縮算法[J];光子學(xué)報(bào);2009年05期

6 胡穎;姜建國(guó);;改進(jìn)的無(wú)損壓縮算法在軟電話中的研究與應(yīng)用[J];計(jì)算機(jī)工程;2007年22期

7 張寧,章毓晉,劉青棣,林行剛;基于灰度指紋圖像信噪特征的無(wú)損壓縮算法[J];電子學(xué)報(bào);2001年04期

8 鄧富博;李墨豪;溫愷林;張朝璇;陳晨;;基于不同信源的三種常用無(wú)損壓縮算法的研究[J];電子世界;2016年09期

9 王鵬杰;潘志庚;徐明亮;劉勇奎;;基于局部最小生成樹的點(diǎn)模型快速無(wú)損壓縮算法[J];計(jì)算機(jī)研究與發(fā)展;2011年07期

10 陳永紅;史澤林;李德強(qiáng);;基于3DLMS預(yù)測(cè)的高光譜圖像無(wú)損壓縮算法[J];儀器儀表學(xué)報(bào);2009年10期

相關(guān)會(huì)議論文 前2條

1 況軍;羅建書;黃志雄;;基于三維自適應(yīng)預(yù)測(cè)的多光譜圖像的無(wú)損壓縮算法[A];計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展·2007——全國(guó)第18屆計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集[C];2007年

2 張海波;蒙應(yīng)杰;楊金濤;;LZW無(wú)損壓縮算法的Java語(yǔ)言實(shí)現(xiàn)與研究[A];2006“數(shù)學(xué)技術(shù)應(yīng)用科學(xué)”[C];2006年

相關(guān)重要報(bào)紙文章 前2條

1 龍哥;軟件應(yīng)用問(wèn)答[N];中國(guó)計(jì)算機(jī)報(bào);2004年

2 馬璇;“高才”云集潛心教學(xué)與科研[N];深圳特區(qū)報(bào);2011年

相關(guān)博士學(xué)位論文 前2條

1 任學(xué)軍;基于熵降變換的無(wú)線傳感網(wǎng)感知數(shù)據(jù)無(wú)損壓縮算法研究[D];西北大學(xué);2011年

2 高放;高光譜圖像無(wú)損預(yù)測(cè)壓縮技術(shù)研究[D];吉林大學(xué);2016年

相關(guān)碩士學(xué)位論文 前10條

1 柳曦;FASTQ文件無(wú)損壓縮算法研究[D];西安電子科技大學(xué);2018年

2 王松;面向快速解壓應(yīng)用的無(wú)損壓縮算法研究與實(shí)現(xiàn)[D];電子科技大學(xué);2017年

3 劉粵;面向太陽(yáng)全日面磁場(chǎng)圖像的無(wú)損壓縮算法及關(guān)鍵技術(shù)研究[D];北京交通大學(xué);2018年

4 顧巍;基于FPGA的LZ4無(wú)損壓縮算法優(yōu)化設(shè)計(jì)[D];東南大學(xué);2017年

5 李長(zhǎng)興;基于FPGA實(shí)現(xiàn)JPEG-LS無(wú)損壓縮算法的研究[D];沈陽(yáng)航空航天大學(xué);2018年

6 宋秉璽;高效無(wú)損壓縮算法的研究與實(shí)現(xiàn)[D];西安電子科技大學(xué);2014年

7 汪磊;基于FPGA的視頻無(wú)損壓縮算法研究與實(shí)現(xiàn)[D];浙江工業(yè)大學(xué);2013年

8 裴遠(yuǎn);嵌入式平臺(tái)上快速無(wú)損壓縮算法的研究[D];西安電子科技大學(xué);2014年

9 馬智忠;基于位圖的彩色圖像無(wú)損壓縮算法研究[D];蘭州大學(xué);2017年

10 張萍;有序抖動(dòng)圖像的無(wú)損壓縮算法研究[D];西安建筑科技大學(xué);2012年

本文編號(hào)：2701190