论文部分内容阅读
测序技术从一代Sanger测序,经历二代测序(Next-generation Sequencing,NGS),发展到当前已经进入三代测序(Third-generation Sequencing,TGS)时代。现如今伴随着生物信息学研究的深入,三代测序技术已经超越二代测序技术成为主流的研究方向并且促进了生物信息技术的发展。但是三代测序的特点决定它将会带来许多新的挑战,测序生成序列与数据库存储空间不匹配,数据增长速度与计算机容量增长不匹配就是现如今急需解决的难题。为应对测序数据的高速增长,相较于增加存储容量和减少数据生成的方案,针对测序生成的短读数据进行压缩是一个行之有效的方法。通过分析现有的主流二代压缩算法,本文提出专门针对三代重测序数据的压缩算法,在上述算法基础上改进解压缩算法实现局部解压缩技术,并创新性地设计插入压缩算法。论文的主要内容包括:(1)探讨了测序技术的发展历程,对比二代和三代测序技术及其产生数据的特点,分析主流的测序数据保存格式,深入研究基因测序数据的结构和针对生物数据的压缩算法,这为接下来的算法设计打下基础。(2)设计出针对三代重测序数据的压缩框架LYZip,其中详述了LYZip针对不同数据流采用合适的压缩策略。对于重测序数据占比最大的碱基序列,提出了针对该数据流的自索引逆前缀序列变换压缩算法TPBWT,并在该压缩算法基础上改进解压缩过程,提出了部分解压缩算法,这有利于下游软件对于压缩文件的显示和分析。通过实验证明该算法具有很好的压缩性能,为接下来的插入压缩算法做了铺垫。(3)针对重测序数据的排序过慢问题,创新性地提出插入压缩策略并设计了相关算法。在部分解压缩的基础上,通过插入操作省略排序过程,降低了对于测序数据的处理时间和压缩时间。实验证明插入压缩与测序序列排序之后在进行压缩相比减少了压缩时间。本文针对三代重测序(Re-sequencing)DNA序列数据,设计了适用于该类测序数据的压缩框架LYZip。在该算法的基础上实现了部分解压缩技术,并且进一步实现了插入压缩。通过实验证明了这些算法具有很好地压缩性能,从而可以解决DNA测序数据大量增长带来的存储问题,并为三代数据压缩或者将来更先进测序数据的压缩提供了参考。