DNA序列数据压缩算法研究

来源 :南京理工大学 | 被引量 : 0次 | 上传用户:xiaoyuerlga
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
自20世纪末以来,生物测序技术不断的发展,随之产生的各类生物数据,迅速形成了庞大的生物信息数据库。如何有效的分析,管理这些海量的数据,是生物学家和计算机专家们必须着力解决的棘手问题。数据压缩技术是解决这一问题的有效方法。DNA序列数据是一类极其重要的生物数据,具有不同于其他待压缩数据的特征,采用现有的各种通用数据压缩算法,通常不能有效的压缩。因此,研究专门针对DNA序列数据的压缩算法有着重要意义。DNA序列数据的压缩是一项艰巨的任务,很多学者一直致力于这方面的研究,并提出了一些经典算法。其中,压缩效果较好的算法有CTW+LZ, DNACompress, DNAPack。这些算法的共同特点是基于近似匹配压缩的思想,搜索并压缩DNA序列中大量存在的因少数字符的替换、插入或删除而形成的近似匹配片段。然而,搜索近似匹配的时间和空间代价很大,压缩率的提升却不是很显著。鉴于此,本文研究DNA序列中亦大量存在的精确匹配片段(包括互补回文形式)的压缩,设计并实现一种专门压缩DNA序列的算法,称为DNACE (DNA Compression based only on Exact matching),探索精确匹配压缩所能实现的最大压缩率。本文的主要工作:首先,系统的研究现有的多种通用无损压缩算法及各种DNA序列数据压缩算法,分析它们的优缺点以及可以改进的地方;其次,深入的研究DNA序列数据的特点,为更好的设计改进算法提供理论基础;接着,完成]DNACE算法的总体设计,算法结合两种字典压缩思想LZ77和LZ78,动态搜索序列的精确匹配并压缩,对于剩余的不匹配片段则采用基于PPM概率预测模型的算术编码进行压缩;最后,实现并测试算法,完成压缩性能评估。实验表明,DNACE算法实现简单,运行快速,压缩效果达到了常用DNA序列数据压缩算法的水平,为生物信息学的研究提供了基础。
其他文献
随着网络相关技术的发展,越来越多的信息尤其是文本相关数据资料迅速增长,人们需要在海量的信息中及时获取有用的或者自己感兴趣的内容。这是互联网信息内容处理领域急需解决的
相比于单机器人,多机器人系统具有诸多优点,其应用场合遍及城市环境侦察、灾难搜索与救援、仓储管理等方面,但仍然面临着如体系结构设计、任务分配、协调控制等问题。本文围
随着人类的发展和社会的进步,由废塑料产生的环境污染问题和日益严重的能源短缺问题始终困扰着人类。废塑料炼油工业将其收集的废塑料运用在炼油工业中,能有效地缓解环境污染和
随着通信、电子和计算机的发展,工业控制系统也在逐渐发生着变革,并且对实施性能的要求也逐渐增高,例如在信息传递过程中要求快速传递,现场设备要求快速控制,上位机的显示与
学位
随着基因组项目的不断完成,产生了大量有待于分析和解释的生物信息,从而,人们可以从分子水平上了解基因的表达模式和微观层面上研究生命现象。基因芯片技术是生物信息研究的主要
随着网络技术在全球范围内兴起和数字信号处理技术的发展,语音通信技术获得了突破性的发展和更广泛的应用。然而,当语音通信内容涉及到个人隐私、商业机密以及国家秘密时,人们又
低压大电流电源主要应用于电镀、单晶炉加热、励磁等行业。一般要求电源的输出电压较低而电流要很大,并且电源功率要求也比较大。   结合低压大电流直流电源的设计难点及特
在研制伺服系统的过程中,对系统进行调试是十分有必要的,同时在日常维护中也需要对伺服系统进行测试与校验,这些过程能够找出伺服系统需要改进的地方,对提升系统的性能、增加系统稳定性具有重要的意义。伺服系统测试仪就是用来测试分析伺服系统性能的工具,工欲善其事必先利其器,因此设计一种使用方便、功能强大的测试仪对于伺服系统的研制、校验和日常维护工作都有很大的帮助。本文基于ARM及Linux操作系统设计了一种多
伺服系统作为一种能够跟随外界给定输入信号实时变化的控制系统,被广泛应用于各个领域。随着对伺服系统控制精度,响应速度以及鲁棒性要求的不断提高,传统的单级伺服系统难以