High efficiency referential genome compression algorithm
High efficiency referential genome compression algorithm
复制标题
高效参考基因组压缩算法
DOI：
10.1093/bioinformatics/bty934
复制
发表时间：
2019-06-15
期刊：
影响因子：
5.8
通讯作者：
Chen, Min
中科院分区：
文献类型：
--
作者：
Shi, Wei;Chen, Jianhua;Chen, Min
随着新一代测序技术（NGS）的发展和逐步普及应用，基因组测序的速度越来越快，成本越来越低，产生了大量的基因组序列数据，并且这些数据仍在以爆炸式的速度增长。这些遗传数据的传输、存储、处理和分析的时间和成本已经成为阻碍遗传学和生物医学发展的瓶颈。虽然有许多常见的数据压缩算法，但由于无法考虑和利用基因组序列数据的固有特性，它们对基因组序列的压缩效果并不理想。因此，开发一种针对基因组数据的快速高效的压缩算法是一个重要而紧迫的问题。结果我们开发了一种参考性无损基因组数据压缩算法，其性能优于已有的算法。通过精心设计的匹配策略选择机制，将局部匹配和全局匹配的优势合理结合起来，提高了匹配子字符串的描述效率。同时考虑了匹配子串的长度和位置对压缩效率的影响。该算法可以在18min左右压缩3GB左右的人类全基因组FASTA数据。压缩文件的大小从几兆到大约40兆不等。平均压缩比高于最先进的基因组压缩算法，时间复杂度与最知名的算法处于同一数量级。可用性和实施https://github.com/jhchen5/SCCGSupplementary information补充数据可在Bioinformatics在线获取。
Motivation With the development and the gradually popularized application of next-generation sequencing technologies (NGS), genome sequencing has been becoming faster and cheaper, creating a massive amount of genome sequence data which still grows at an explosive rate. The time and cost of transmission, storage, processing and analysis of these genetic data have become bottlenecks that hinder the development of genetics and biomedicine. Although there are many common data compression algorithms, they are not effective for genome sequences due to their inability to consider and exploit the inherent characteristics of genome sequence data. Therefore, the development of a fast and efficient compression algorithm specific to genome data is an important and pressing issue.Results We have developed a referential lossless genome data compression algorithm with better performance than previous algorithms. According to a carefully designed matching strategy selection mechanism, the advantages of local matching and global matching are reasonably combined together to improve the description efficiency of the matched sub-strings. The effects of the length and the position of matched sub-strings to the compression efficiency are jointly taken into consideration. The proposed algorithm can compress the FASTA data of complete human genomes, each of which is about 3GB, in about 18min. The compressed file sizes are ranging from a few megabytes to about forty megabytes. The averaged compression ratio is higher than that of the state-of-the-art genome compression algorithms, the time complexity is at the same order of the best-known algorithms.Availability and implementationhttps://github.com/jhchen5/SCCGSupplementary informationSupplementary data are available at Bioinformatics online.