高通量测序数据的压缩与索引方法研究

论文摘要

基因测序技术近十余年来发展迅猛,测序成本和测序周期急剧下降。海量的测序数据不仅对网络传输和本地存储提出了更高的要求,还增加了测序数据分析和使用带来了的难度。FASTQ文件格式作为目前最主流测序技术所采用的存储格式之一,现阶段的主流文本压缩索引算法无法很好地解决FASTQ文件的压缩与索引问题。因此针对FASTQ文件设计压缩与索引算法,从而解决测序数据的存储和检索问题,是一项很有价值的工作。本文提出一种FASTQ文件的压缩索引算法EFASTQ,该算法针对FASTQ文件的特性,对文件先进行预处理,再采用压缩算法进行压缩存储;并在压缩文件的基础上构造索引结构,实现了对FASTQ文件的检索。EFASTQ算法采用先将FASTQ文件中包含的短读序列、质量分数序列和标识符序列进行分类提取,再用压缩索引进行压缩的思路。（1）针对短读序列的压缩与索引需求,EFASTQ中采用了本文提出的压缩索引算法FM-EF对短读序列进行压缩,并实现了短读计数算法、短读定位算法和短读提取算法。短读计数算法的时间复杂度为O（plog2|ΣR|）,其中p表示需要计数的短读长度,|ΣR|表示短读数据符号表大小;短读定位算法的时间复杂度为O（occR（log2|ΣR|（log2nR）2/log2log2nR+1））,其中occR为需要定位的位置的数量、nR为短读数据的大小;短读提取算法的算法复杂度为O（log2|ΣR|（（log2nR）2/log2log2nR+lenR））,其中lenR表示提取长度。（2）针对标识符序列由多个不同的字段组成的特点,EFASTQ算法将标识符序列中的字段进行分类,对不同类型的字段采用不同的方式进行编码,对编码后的结果采用了本文提出的压缩索引算法FM-EG进行压缩,并实现了质量分数提取算法,该算法的时间复杂度为O（（lenQ+（log2nQ）2/log2log2nQ）log2|ΣQ|+lenQ）。（3）针对质量分数序列中频繁出现的连续相同字符构成的字符串的特点,设计了游程编码对质量分数序列进行预处理,对编码后的结果采用FM-EG算法进行压缩,并实现了标志符提取算法;该算法的时间复杂度为O（（lenI+（log2nI）2/log2log2nI）log|ΣI|）。在上述算法的基础上,实现了FASTQ提取算法,该算法的时间复杂度为O((len2FQ+(log2nFQ)2/log2log2nFQ)log2|ΣFQ|+lenFQ),其中lenFQ为提取的FASTQ数据组的长度,nFQ为经过预处理后FASTQ文件大小,|ΣFQ|表示预处理过FASTQ文件的字符集大小。另外,在对EFASTQ算法中的检索算法进行优化时,发现索引采用的后缀数组采样策略对定位算法影响较大。针对这一情况,文本采用了值采样策略对后缀数组进行采样,并设计了对应的结构与算法。本文实验内容分为两个部分。第一部分对EFASTQ算法的压缩检索性能进行了评估。在检索性能方面,将EFASTQ算法与FASTQ文件压缩检索算法BEETL-FASTQ算法进行了检索性能方面的实验。实验结果表明在检索性能方面,EFASTQ具有更高的效率,特别是EFASTQ短读计数算法速度是BEETL-FASTQ算法的10倍左右。在压缩性能方面,通过经典文本压缩算法Gzip、行业领先的FASTQ文件压缩算法DSRC2、FASTQ文件压缩检索算法BEETL-FASTQ、FASTQ文件质量分数压缩算法AQUa进行压缩性能实验。实验结果表明,EFASTQ算法的压缩性能与Gzip和BEETL算法相比优势较大,与DSRC2算法和AQUa算法接近。实验第二部分针对两种不同的后缀数组采样策略的定位算法上的性能进行了评估。并通过设计实验对两种采样后缀数组采样策略,对定位算法性能进行比较。实验结果表明,值采样策略能比位置采样策略在检索性能提升15%—20%。

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 研究现状
•     1.2.1 FASTQ文件压缩索引现状
•     1.2.2 通用文本压缩索引现状
•   1.3 本文工作
• 第二章 预备知识
•   2.1 FASTQ文件格式
•   2.2 FASTQ索引问题定义
•   2.3 后缀数组
•   2.4 简明数据结构
•   2.5 BWT变换
•   2.6 小波树
•     2.6.1 小波树的构建
•     2.6.2 小波树的简明操作
•   2.7 FM-index结构
•   2.8 比特串编码
•   2.9 Elias Fano编码
•   2.10 本章小结
• 第三章 压缩索引算法EFASTQ
•   3.1 总体框架
•   3.2 短读序列压缩
•     3.2.1 FM-EF压缩算法
•     3.2.2 空间分析
•   3.3 质量分数序列压缩
•     3.3.1 预处理
•     3.3.2 FM-EG压缩算法
•   3.4 标识符序列压缩
•     3.4.1 预处理
•     3.4.2 压缩
•   3.5 EFASTQ检索算法
•     3.5.1 短读计数算法
•     3.5.2 短读定位算法
•     3.5.3 短读提取算法
•     3.5.4 FASTQ提取算法
•   3.6 本章小结
• 第四章 后缀数组采样策略
•   4.1 位置采样和值采样策略
•   4.2 采样策略性能量化
•   4.3 值采样后缀数组实现
•   4.4 本章小结
• 第五章 实验结果与分析
•   5.1 实验环境及数据源
•   5.2 EFASTQ性能评估
•     5.2.2 压缩性能评估
•   5.3 后缀数组采样策略性能评估
•   5.4 本章小结
• 第六章 总结和展望
•   6.1 总结
•   6.2 展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 硕士论文

作者: 王晨晖

导师: 霍红卫,张小宁

关键词: 格式,压缩,索引,采样策略

来源: 西安电子科技大学

年度: 2019

分类: 基础科学

专业: 生物学

单位: 西安电子科技大学

分类号: Q811.4

DOI: 10.27389/d.cnki.gxadu.2019.002438

总页数: 82

文件大小: 1878K

下载量: 31