基于参考的基因组序列数据压缩算法研究

发布时间：2020-11-14 17:06

　　 随着下一代测序技术(Next Generation Sequencing,NGS)的发展和逐步普及,基因测序变得越来越快速,费用也越来越亲民。基因组序列数据正以爆炸性的速度扩增,因而产生了海量基因组序列数据。传输,存储,处理和分析这些数据的时耗和费用日渐成为制约基因组学和生物医学发展的瓶颈。虽然现有许多通用的数据压缩算法和软件,但由于不能考虑和处理基因组序列数据的固有特性,它们不能高效地压缩基因组序列数据。因此研发有针对性的,快速有效的基因组序列数据压缩技术已经成为了一项重要而紧迫的课题。本文提出了一种高压缩率的基于参考的无损基因组序列数据压缩算法。利用相同物种间基因组的高度相似性,将待压缩目标基因组序列匹配到参考基因组序列中,以匹配结果(即两序列相同子序列的位置及长度)和目标序列的不匹配部分,代替目标基因组序列。本文创新性地设计了匹配策略选择机制,有效地结合了以有无匹配位置的限制为区分的两种主流匹配策略,即基于分段的局部匹配和全局匹配。根据参考基因组和目标基因组序列的相似程度而应用不同的匹配策略,借助哈希方法搜索两序列间相同的子序列,并评估子序列的匹配位置和匹配长度对匹配效率的影响,以确定相同子序列的匹配位置。有效地处理了基因组序列数据中的各类字符,以进一步提高匹配效率。最后借助高效的熵编码压缩器对保存匹配结果的中间文件完成压缩。实验结果表明,本文压缩算法可在至多18分钟内对FASTA格式的约3GB大小的人类完整基因组序列数据完成压缩,56组人类基因组序列测试数据压缩后的大小为4.45MB至40.67MB。本文压缩算法的平均压缩率优于现有同类型先进的基因组序列数据压缩算法,具有更好的鲁棒性,且时空复杂度与现有先进的算法处于同一数量级,具有较强的实际应用价值。本文还设计了对应的高效解压缩算法,可由已压缩文件和参考基因组序列数据快速,无损的复原目标基因组数据。完整人类基因组数据解压缩的耗时被控制在2分钟以内。
【学位单位】：云南大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：Q811.4
【部分图文】：

后是序列数据行，以回车符结尾。序列信息描述行通过第一列中的大于符（“＞”）??与序列数据行进行区分，并建议所有序列数据行的长度小于８０个字符。ＦＡＳＴＡ数??据格式的一个示例序列数据如图２－３所示，是某记录编码某蝴蛛猴的Ｇ－ｇａｍｍａ－??ｇｌｏｂｉｎ蛋白的ＤＮＡ序列的ＦＡＳＴＡ文件。鉴于ＦＡＳＴＡ数据格式的广泛使用及其适??用性，本文将针对该格式的基因组序列数据设计专用的压缩算法。??１３??

本文算法的压缩部分分别按功能设计了六个模块，即预处理模块，??基于分段的局部匹配模块，全局匹配模块，匹配策略选择模块，后处理及熵编码模??块。本文算法的主要流程如图３－１所示。??１７??

３．?５匹配策略选择机制??本文设计了有效且复杂度较低的匹配策略选择机制，以实现针对相似度不同??的目标与参考基因组序列组合采用不同的匹配策略，其简要示意如图３－２所示。??输入目标序列片段??＾■和参考序列片段＜??局部匹配操作??否?＾￣—??Ｉ－是一？不匹配数＋丨？?１??后处理等操作?否?否??是???Ｉ???全局匹配策略??Ｖ??后处理等操作??图３－２：匹配策略简要流程示意框图??如前文所言，当目标序列与参考序列显著不同时，就应釆用全局匹配策略??２２??
【相似文献】

相关期刊论文 前10条

1 冯志全,范平,张少白,王玉茹,成谢锋;一种无失真图像数据压缩算法[J];计算机应用;2001年S1期

2 包冬梅;;数据压缩算法研究[J];无线互联科技;2019年21期

3 李锦明;张文栋;毛海央;李林;林娟;马游春;;实时无损数据压缩算法硬件实现的研究[J];哈尔滨工业大学学报;2006年02期

4 张楠;几种处理ECG信号的数据压缩算法的比较[J];医疗卫生装备;2003年09期

5 曾玲,饶志宏;几种数据压缩算法的比较[J];通信技术;2002年09期

6 冯志全,成谢锋,王玉茹;一种无失真多媒体数据压缩算法[J];济南大学学报(自然科学版);2001年03期

7 尹志喜;甄国涌;;曲线数据压缩算法研究与应用[J];计算机系统应用;2010年03期

8 郭静;;海量数据归档系统数据压缩算法选择方法研究[J];中国电子科学研究院学报;2019年07期

9 季姝;俞静;;基于冗余数据压缩算法的经济信用风险研究[J];电子设计工程;2017年07期

10 赵巾金;张雯晶;陈晓丽;曹芳婷;车琳琳;;心电信号数据压缩算法的研究[J];中国科技信息;2012年04期

相关博士学位论文 前2条

1 潘志刚;低比特率合成孔径雷达数据压缩算法研究[D];中国科学院研究生院（电子学研究所）;2006年

2 曾尚春;SAR数据压缩算法研究[D];南京航空航天大学;2007年

相关硕士学位论文 前10条

1 史伟;基于参考的基因组序列数据压缩算法研究[D];云南大学;2019年

2 常晓明;基于无线传输的焊接监测系统设计与实时数据压缩算法研究[D];天津工业大学;2019年

3 荣河江;基于自索引结构的高通量基因组重测序数据压缩算法[D];哈尔滨工业大学;2018年

4 陈耀立;GPS数据压缩算法的研究与应用[D];湖南大学;2015年

5 孙超;面向网络传输数据压缩算法的研究与实现[D];合肥工业大学;2012年

6 徐慧;实时数据库中数据压缩算法的研究[D];浙江大学;2006年

7 张辉;基于支持列存储的数据压缩算法研究[D];南京理工大学;2010年

8 白文武;面向云存储的数据压缩算法研究[D];西安电子科技大学;2017年

9 刘锁;振动信号无线监测的数据压缩算法与能效分析[D];华北电力大学(北京);2016年

10 曹芳彤;声波测井数据压缩算法的嵌入式开发与实现[D];西安科技大学;2015年

本文编号：2883722