FASTQ文件无损压缩算法研究

发布时间：2020-06-07 09:11

【摘要】：基因测序技术的迅猛发展使得测序成本直线下降,测序数据规模急剧攀升,为数据分析及使用带来诸多不便。FASTQ格式是目前应用最广泛的测序数据存储格式之一,因此有必要设计针对FASTQ格式文件的压缩算法,从而实现测序数据的高效存储及传输。本文提出一种FASTQ文件无损压缩算法FTComp,该算法分两阶段处理FASTQ文件。第一阶段是FASTQ文件的预处理部分,算法根据文件格式特征,对数据进行分类提取,生成标识符序列、DNA序列以及质量分数序列。针对标识符序列,算法对所有标识符序列进行分区,根据区域文本特征为其匹配相应数据处理方式;针对DNA序列,FTComp算法结合分组编码以及游程编码对序列进行编码处理;针对质量分数序列,算法使用游程编码思想对序列进行预处理。FTComp算法在第二阶段使用本文提出的无损压缩算法HyBWT作为压缩器,对第一阶段产生的数据进行二次压缩。HyBWT算法首先对文本进行BWT变换,并对变换后的文本构建小波树以进行简明表示,最后算法使用混合编码压缩小波树节点,从而完成FTComp算法第二阶段的数据压缩及存储。本文实验内容分为两部分,包括算法参数对文件压缩比的影响以及FTComp算法与其他算法的性能对比测试。实验首先测试小波树的树形及其节点位向量块大小对文件压缩比的影响。实验结果表明,由于FASTQ文件所包含的三种序列数据特征不同,应分别为其选择合适的参数设置以达到较高的文件压缩比。算法性能对比测试所选五种算法包括两种经典的文本压缩算法Gzip和Bzip2,以及三种目前行业领先的针对FASTQ文件的无损压缩算法DSRC2、Quip以及LFQC。实验对比六种算法在八组FASTQ文件数据中的文件压缩比、压缩速度以及解压缩速度。实验结果表明,FTComp算法在文件压缩比方面表现较为优异,压缩后空间占用平均减少约80%,该结果与LFQC算法十分接近,并且超过DSRC2以及Quip这两种达到工业级的FASTQ文件无损压缩算法,经典的文本压缩算法Gzip以及Bzip2表现不佳,FTComp算法与之相比优势明显;在压缩速度以及解压缩速度方面,FTComp算法均表现稳定,并且远超LFQC算法,约是其5至10倍。
【图文】：

FASTQ文件无损压缩算法研究

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 举例说明算法 3.2 过程，对于 F7中的值 x = 1716(10)= 11010110100(2)，入其第 0 到第 6 位，即 curleft7 = 00110100(2)，将 x 右移 7 比特，，得到 curval001101(2)，curvalue 不为 0，因此当前字节 curleft7 的最高位写入 1，即 curle110100(2)，将该字节存入字符串 ans；重复上述操作，此时 curleft7 = 00001101value = 0，则当前字节的最高位写入 0，可得 curleft7 = 00001101(2)，ans += cur0110100(2)+ 00001101(2)，程序结束。
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.4

【相似文献】