A framework for a general-purpose sequence compression pipeline: a centroid based compression

摘要

DNA sequence data accumulate at an overwhelmingly fast speed, overtaking the speed of the increase of disk storage and creating enormous challenges to data storage, processing, and analysis. Taking advantage of the fact that two human genomes differ by less than 0.1%, we and other groups previously proposed a reference based compression algorithm to compress genomic data. However, the reference based sequence compression only works when there is a reference genome. Many large-scale sequencing projects such as metagenomics data do not have any reference genomes readily available. Therefore, we need a compression method that can be applied in these cases. This project addresses the problem by introducing a centroid based compression algorithm. The centroid based compression algorithm involves taking in large-scale next generation sequencing data and clustering similar sequences into groups. Within each group a "centroid" sequence is identified, and the differences that each sequence has from its respective centroid sequence is encoded. Results show that the method is advantageous when there exists many redundant sequences within the dataset - in particular, the high coverage nature of next generation sequencing data and meta-genomics data. The framework developed here is for a general-purpose compression pipeline that can be theoretically applied to many cases.