论文部分内容阅读
随着下一代测序(NGS)技术的发展,DNA数据迅速增长,这使得对DNA数据的存储、传输和分析都遇到严峻的挑战。对基因文件进行压缩对于解决该问题有着很好的前景,但现行基因库大多是使用通用的压缩算法进行压缩处理之后再进行存储,这无论在压缩率还是压缩速度方面均已经无法满足呈指数形式增长的基因数据。本文利用基因文件格式特点,在数据索引方面进行了深入研究,设计并实现了一个针对基因文件的分布式压缩系统,提高了基因数据的压缩率和压缩速度。 本文的主要工作和贡献如下: (1)对于FASTQ格式文件,本文提出了一种基于字典树形索引结构的数据压缩算法,以提高序列部分的压缩效果。通过构建字典树结构来对序列部分进行查询匹配,相对于哈希表,字典树可以避免碰撞、实现部分匹配,同时能最大程度减少不必要的字符串比较操作,使其查询效率更高。对于字典树占用内存空间过大的问题,本文采用了取样索引的策略,从而有效地减少了内存占用空间,同时在查询过程中使用了懒惰匹配以提高匹配率;此外还根据序列部分对应的质量分值高低决定是否将该序列部分加入到索引结构中,使得字典树结构中的子串具有更高的被匹配概率。 (2)本文设计并实现了一个分布式基因文件压缩系统:DNA-DCS,并进行了压缩率、压缩速度和吞吐率方面的测评。在FASTQ文件的压缩方面,DNA-DCS的压缩率比GZip提升了50%左右,和DSRC相当;压缩速度比GZip提升了3~6倍,比DSRC提升了55%左右。随着压缩节点的增多,DNA-DCS在压缩率保持平稳的情况下,压缩速度呈接近线性增长;在吞吐率方面,单节点带宽达200MB/s,并基本可保持线性增长,表现出了良好的扩展性能。