论文部分内容阅读
二十世纪生物信息学迅速发展，在信息的数量和质量上都极大地丰富了生物科学的数据资源。随着生物序列数据的日益增加，数据占用的存储空间日益增大。如何在有限的存储空间中存储更多的生物序列数据是必须面临的问题。就DNA序列数据而言，可使用数据压缩方法解决大量DNA序列数据的存储问题。
本文在研究传统压缩算法和现有的DNA序列数据压缩算法的基础上，以提高DNA序列数据的存储效率为主导思想，对经典的数据压缩算法进行改进，设计并实现适合于DNA序列数据压缩的算法，从而节省数据存储空间和间接增加生物数据库的存储量。
本文主要研究工作有：
(1)综合分析现有的多种传统压缩算法及DNA序列数据压缩算法，指出各算法的优缺点，为设计改进算法提供理论和思想基础。
(2)分析基于字典压缩的LZW算法思想，根据DNA序列数据的特殊性，改进LZW算法的字典映射，引入显式字典的思想并研究字典的数据结构，提出算法改进的可能性。
(3)在对LZW字典的总体改进的基础上，根据不同的改进方向设计两种改进算法：DNA_LZW变长编码算法，DNA_LZW字典压缩算法。
DNA_LZW变长编码算法。引入动态变长编码的思想，提出算法改进的原理并设计算法结构，算法使用动态变长编码对码字进行编码压缩。
DNA_LZW字典压缩算法。引入使用完整LZW字典对DNA序列进行压缩的思想，提出算法改进的原理以及字典压缩的策略，研究最优编码长度的计算方式。算法的核心包括：字典构建、字典压缩和码字编码压缩。
综上所述，本文在分析字典压缩算法LZW基础上，结合DNA序列数据特点，提出两种改进算法。实验结果表明：两种改进算法皆优于原LZW算法，而DNA_LZW字典压缩算法的稳定性较好；两种改进算法的压缩效果均达到预期目标。