论文部分内容阅读
DNA是一种存储生物的遗传信息的聚合物,对DNA进行研究已经成为时下的热点问题。随着高通量测序技术的不断发展,测序费用越来越低,测序周期也越来越短,由此而导致的DNA数据规模以指数级方式快速增长,在有限的资源内,用少量空间存储海量DNA数据资源,成为了生物学家以及计算机专家等人面临的一个新的挑战。近年来提出的DNA数据压缩方法,有的是提升了压缩率,有的则是减少了压缩时间。Nour和Amr提出的压缩方法,相对于过往的方法,在压缩时间方面有很大优势,但是只局限于细菌类DNA数据。本文对该方法进行改进,提出了RU(最近被使用)变换和MG(归并)变换,并给出了两种改进的分步压缩方法,每种方法均分为两次压缩。本文主要工作如下:(1)提出RU变换进行DNA数据压缩。第一次压缩时对DNA数据进行一系列操作,先把DNA数据转化成一个只包含0和1的二进制文件以及相邻字符都不相同的碱基序列文件,接下来把这个碱基序列文件通过RU变换转化成小整数序列文件,再用哈弗曼编码思想转化成二进制文件,最后再把所有的二进制文件转化成普通字符文件;第二次压缩时采用通用文本压缩算法LZ77算法对得到的所有普通字符文件统一压缩。(2)提出MG变换进行DNA数据压缩。第一次压缩时对DNA数据进行一系列操作,先把DNA数据转化成一个只包含0和1的二进制文件以及只剩三种字符的碱基序列文件,接下来把这个碱基序列文件通过MG变换转化成二进制文件和长度减半的碱基序列文件,再用哈弗曼编码思想把最终得到的碱基序列文件转化成二进制文件,最后再把所有的二进制文件转化成普通字符文件;第二次压缩时采用通用文本压缩算法LZ77算法对得到的所有普通字符文件统一压缩。针对本文的两个压缩方法,选取了来自于GenBank数据库常用的DNA数据压缩算法测试数据进行实验论证。实验结果表明,和Nour、Amr的方法相比:对于细菌类DNA数据,基于RU变换的DNA数据压缩方法,压缩时间和解压缩时间均节省了70%以上,代价是压缩率平均降低了1.5%,而基于MG变换的DNA数据压缩方法,压缩时间和解压缩时间均节省了50%以上,代价是压缩率平均降低了0.5%;对于非细菌类,两种方法在压缩率得到提升的同时,压缩时间和解压缩时间均节省了20%以上。