超长DNA序列的高效压缩算法研究  

An Efficient Compression Algorithm for Huge DNA Sequence

作　　者：欧阳继超 冯萍[1] 康继昌[1] 

机构地区：[1]西北工业大学计算机学院,陕西西安710072

出　　处：《计算机技术与发展》2013年第12期1-4,10,共5页Computer Technology and Development

基　　金：国家"863"高技术发展计划项目(2003AA001018);航空科学基金(02F53031)

摘　　要：DNA序列虽然只由四个碱基组成,但数据量却非常巨大。有效的压缩DNA数据能大量节省传输的时间开销。目前已经有一些DNA序列专用的压缩算法,如Biocompress,DNACompress和CTW+LZ。虽然这些算法可以获得较好的压缩比,但是由于采用了传统的CTW算法或LZ系列的字典替换,导致花费太多的时间。为了解决这一问题,提出使用改进的RLE,差分编码和可变长整形等一系列编码方式进行多重压缩的高效压缩算法Dzip。标准DNA Benchmark数据测试的实验数据表明,该算法与现行DNA专用压缩算法相比,加速比至少为28。The DNA sequence is composed of only four base,but has lots of data. The effective compression for DNA data can save much time. There are several DNA sequence oriented compression methods like Biocompress,DNACompress and CTW＋LZ. These algorithms can achieve good compression ratio,but has sacrificed too much time searching for similar areas. In order to solve the problem, a new al- gorithm Dzip was presented, by means of multiple layers compression techniques like improved RLE, delta encoding, variable integers. In comparison with current DNA sequence oriented compression methods,the standard DNA benchmark results indicate that the new algo- rithm can achieve at least 28 times faster in running time.

关 键 词：双序列比对 DNA数据压缩 可编程门阵列 差分编码 可变长整形 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]