7
$\begingroup$

How small can a compressed file containing the human genome be? I'm aware that this question cannot actually be answered, since it is asking for the Kolmogorov complexity of the human genome, which is not computable. So reformulating: What is the largest known lower bound that we can put on the size of a file containing the human genome?

An example answer could be: on average we know that the human genome contain at least this amount X of randomness, therefore it is not possible to do better than Y bytes.

I'm agnostic on which human genome, but I would say without polymorphisms to make it simpler.

The compressed sequence would need to be stand alone, without using a reference (I asked a question on that topic here: Compressing the human genome to few megabytes).

There should be a program able to compress and decompress the genome in a lossless way. Apart from that, any kind of modelling and coding is allowed.

$\endgroup$
0
8
+250
$\begingroup$

TLDR; For the most modern CHM13 assembly (v1.1; Complete T2T reconstruction of a human genome; https://github.com/marbl/CHM13), the best compression without any use of a reference would be between 624 MB and 641 MB.

Upper estimates of genome compressibility can be made using standard compressors (see, e.g., this comparison). In my experience, xz can achieve great compression ratios on genomic sequences, especially when used with the maximum compression level (-9) and a single thread (-T1). Importantly, the original FASTA file needs to be cleaned – linebreaks hamper compression as they act as noise; the reformatting can be done by seqtk seq -U (which also converts all nucleotides to the upper case). It the case of the CHM13 assembly, xz compresses the human genome to 641,369,600 bytes.

Lower estimates are trickier. The most straightforward approach is through the number of distinct k-mers. Since k-mer sets contain less information than the original assemblies, we can use them for determining the lower bounds of genome compressibility. The lower bound on the compressibility of k-mer sets is 2 bits per distinct k-mer (under certain assumptions that I believe are satisfied in our case). The CHM13 human genome assembly contains 2,497,988,809 distinct canonical 31-mers, which corresponds to 624,497,203 bytes.

Overall, xz does a great job at compressing single human genomes, and the resulting size is very close to the optimum. The full analysis from this post can be found on http://github.com/karel-brinda/human-genome-compression. The resulting files are here: https://zenodo.org/record/4776580.

$\endgroup$
5
$\begingroup$

There's a benchmark that compared dozens of compressors on DNA data, including human genome: http://kirr.dyndns.org/sequence-compression-benchmark/

In particular, this table shows file size of compressed human genome, produced by the strongest setting of each compressor: http://kirr.dyndns.org/sequence-compression-benchmark/?d=Homo+sapiens+GCA_000001405.28+%283.31+GB%29&cs=1&cg=1&com=yes&src=all&nt=4&only-best=1&bn=1&bm=size&sm=same&tm0=name&tm1=size&button=Show+table

The best result is currently 657 MB on that particular genome build (GCA_000001405.28), when compressed with fastqz.

By the way, xz (mentioned in another answer) is currently number 20 in that table. (Though the genome is un-modified straight from the database, not the "cleaned" form.)

Disclosure: I worked on that benchmark.

Note: What is being compressed here is a FASTA file containing a particular assembly of a human genome. Compared to an actual genome it has this extra content: Sequence names and brakes between contigs, end of line characters, N characters representing unknown bases, and soft-masked repeats (represented as lowercase). On the other hand, it also misses some information from the actual genome: 1. It's an unphased haploid sequence, while the real genome is diploid (two copies of each chromosome). 2. It includes no epigenetic information (DNA methylation, histone modifications), nucleosome positioning, 3D structure of packed DNA, etc. So, it's just a digital model of a genome with a certain degree of accuracy, that is useful, simple, and relatively affordable to obtain. It's a format commonly used for representing genomes in databases.

$\endgroup$
7
  • 1
    $\begingroup$ I quickly tested xz on this build (GCA_000001405.28) in the same way as in my reply (seqtk seq -U; xz -9 -T1) and got 667 MB, which is very close to fastqz-slow in the referenced table (657 MB). With general compressors, it's important to remove eols in the sequences, as well as to convert all bases to the upper case. Note that none of these steps modify the genome in any way – fastas can always be converted to a fixed width, and the upper/lower case info are usually just masked repeats. $\endgroup$ Jun 12 at 17:19
  • 1
    $\begingroup$ As the table above says 770 MB (i.e., +103 MB) for xz with similar parameters (-e9), I assume the file probably wasn't in a form that would facilitate compression using general compressors, and the observed gain of specialized compressors came mainly from removing the eols/upper case conversion. $\endgroup$ Jun 12 at 17:21
  • 1
    $\begingroup$ An additional experiment: I verified if xz could outcompete even fastqz-slow, and it indeed can. GCA_000001405.28 can be compressed down to 652 MB by 'xz -T1 -e --lzma2=preset=9,dict=512MiB' (again, after 'seqtk seq -U'). $\endgroup$ Jun 12 at 18:25
  • 1
    $\begingroup$ @Kamil S Jaron, cleaning is one reason, another is that it's just different genome build. Though as you see Karel obtain similar number with his method. $\endgroup$
    – Kirr
    Jun 15 at 20:03
  • 1
    $\begingroup$ @Karel Břinda, by the way, it's good idea to tweak xz's dict (dict=512MiB), I should benchmark this setting too. Thanks. $\endgroup$
    – Kirr
    Jun 15 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.