Answers.Body: <p>For the most modern CHM13 assembly (v2.0; Complete T2T reconstruction of a human genome; <a href="https://github.com/marbl/CHM13" rel="nofollow noreferrer">https://github.com/marbl/CHM13</a>), the best known compression without any use of a reference is 567 MB (1.45 bits/bp; 1.80 bits/distinct canonical 31-mer).</p>
  <p>Upper estimates of genome compressibility can be made using standard general or specialized compressors (see, e.g., <a href="https://academic.oup.com/gigascience/article/9/7/giaa072/5867695" rel="nofollow noreferrer">this comparison</a>). In my experience, <code>xz</code> can achieve great compression ratios on genomic sequences, especially when used with the maximum compression level (<code>-9</code>) and a single thread (<code>-T1</code>). The compression performance can be further boosted by using a large dictionary (<code>-e --lzma2=preset=9,dict=512MiB</code>). Importantly, the original FASTA file needs to be cleaned – linebreaks hamper compression as they act as noise; the reformatting can be done by <code>seqtk seq -U</code> (which also converts all nucleotides to the upper case). It the case of the CHM13v2 assembly, <code>xz</code> compresses the human genome to 634 MB.</p>
  <p>However, even better performance can be achieved with specialized compressors, especially if they have particular support for reverse complements and mutational models. Among the best ones is GeCo3, which has been shown to compress CHM13v2, with a particular combination of parameters, to 567 MB <a href="https://github.com/pratas/HumanGenome" rel="nofollow noreferrer">3</a>.</p>
  <p>Lower estimates are impossible in general (we can't reject the existence of a program that would create the whole sequence from small amount of starting conditions), but can be done for particular compression techniques, e.g., particular variants of dictionary compressors. However, this leads to intractable optimization problems (see e.g. the problem of minimal string attractors).</p>
  <p>A useful auxiliary measure for estimating the compressibility of single genomes is the number of distinct k-mers for a &quot;reasonably&quot; selected k (e.g., k=31). The lower bound on the compressibility of k-mer sets can then be roughly approximated by <a href="https://arxiv.org/abs/1401.5383" rel="nofollow noreferrer">2 bits per distinct k-mer</a>, however, this is limited by the embedded structural assumptions, e.g., that single genomes are in principle random strings with occasional (possibly distant) repeats. For instance, the CHM13v2 human genome assembly contains 2,512,390,070 distinct canonical 31-mers, which would then correspond to 628 MB assuming 2bits/kmers, while the best available specialized compressors can compress it down to 567 MB, i.e., by approx 10% better.</p>
  <p><strong>Updates</strong></p>
  <ul>
  <li>May 27, 2022 – updated the upper bound based on the latest results with CHM13v2 (xz &amp; GeCo3), changed the lower bound wording to an auxiliary estimate as the assumptions have shown not to hold</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-20T15:57:44.453Z
Answers.LastActivityDate: 2022-05-27T15:43:05.637Z
Answers.LastEditDate: 2022-05-27T15:43:05.637Z
Answers.UserDisplayName: Karel Břinda
Answers.Body: <p>There's a benchmark that compared dozens of compressors on DNA data, including human genome: <a href="http://kirr.dyndns.org/sequence-compression-benchmark/" rel="nofollow noreferrer">http://kirr.dyndns.org/sequence-compression-benchmark/</a></p>
  <p>In particular, this table shows file size of compressed human genome, produced by the strongest setting of each compressor: <a href="http://kirr.dyndns.org/sequence-compression-benchmark/?d=Homo+sapiens+GCA_000001405.28+%283.31+GB%29&amp;cs=1&amp;cg=1&amp;com=yes&amp;src=all&amp;nt=4&amp;only-best=1&amp;bn=1&amp;bm=size&amp;sm=same&amp;tm0=name&amp;tm1=size&amp;button=Show+table" rel="nofollow noreferrer">http://kirr.dyndns.org/sequence-compression-benchmark/?d=Homo+sapiens+GCA_000001405.28+%283.31+GB%29&amp;cs=1&amp;cg=1&amp;com=yes&amp;src=all&amp;nt=4&amp;only-best=1&amp;bn=1&amp;bm=size&amp;sm=same&amp;tm0=name&amp;tm1=size&amp;button=Show+table</a></p>
  <p>The best result is currently 657 MB on that particular genome build (GCA_000001405.28), when compressed with fastqz.</p>
  <p>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 &quot;cleaned&quot; form.)</p>
  <p>Disclosure: I worked on that benchmark.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-12T17:19:48.593Z
Answers.Text: 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.
Answers.UserDisplayName: Karel Břinda
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-12T17:21:39.873Z
Answers.Text: 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.
Answers.UserDisplayName: Karel Břinda
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-12T18:25:39.937Z
Answers.Text: 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').
Answers.UserDisplayName: Karel Břinda
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-15T20:03:28.427Z
Answers.Text: @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.
Answers.UserDisplayName: Kirr
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-15T20:04:59.050Z
Answers.Text: @Karel Břinda, by the way, it's good idea to tweak xz's dict (dict=512MiB), I should benchmark this setting too. Thanks.
Answers.UserDisplayName: Kirr
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-16T12:14:08.257Z
Answers.Text: Thanks both, although you are right Kirr, that in real-life situation you don't want to lose information about softmasked bases, the OP asked about the number of bites to store the human genome, therefore Karel's approach is completely valid (human genome does not have really softmasked bases, that's just our way how to add there one more layer of information).
  
  Both of you, would you like to update the answers? I think this discussion is really interesting.
Answers.UserDisplayName: Kamil S Jaron
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-17T21:34:35.050Z
Answers.Text: @Kamil S Jaron, I updated the answer. You're right that it's just one way of representing a genome, and also many genomes don't include soft-mask (e.g. prokaryote genomes).
Answers.UserDisplayName: Kirr
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-11T02:04:12.087Z
Answers.LastActivityDate: 2021-06-17T21:30:11.577Z
Answers.LastEditDate: 2021-06-17T21:30:11.577Z
Answers.UserDisplayName: Kirr
Body: <p>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 <a href="https://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="nofollow noreferrer">Kolmogorov complexity</a> 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?</p>
  <p>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.</p>
  <p>I'm agnostic on which human genome, but I would say without polymorphisms to make it simpler.</p>
  <p>The compressed sequence would need to be stand alone, without using a reference (I asked a question on that topic here: <a href="https://bioinformatics.stackexchange.com/questions/12820/compressing-the-human-genome-to-few-megabytes">Compressing the human genome to few megabytes</a>).</p>
  <p>There should be a program able to compress and decompress the genome in a <a href="https://en.wikipedia.org/wiki/Lossless_compression" rel="nofollow noreferrer">lossless way</a>. Apart from that, any kind of modelling and coding is allowed.</p>
  
Tags: <phylogenetics><human-genome>
Title: Theoretical limit of human genome compression
ThreadText: # Theoretical limit of human genome compression
  
  (Asked by: username_0 on 2020-04-04)
  
  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](https://en.wikipedia.org/wiki/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](https://bioinformatics.stackexchange.com/questions/12820/compressing-the-human-genome-to-few-megabytes)).
  
  There should be a program able to compress and decompress the genome in a [lossless way](https://en.wikipedia.org/wiki/Lossless_compression). Apart from that, any kind of modelling and coding is allowed.
  
  **Tags:** phylogenetics, human-genome
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2021-05-20. Score: 9
  
  For the most modern CHM13 assembly (v2.0; Complete T2T reconstruction of a human genome; <https://github.com/marbl/CHM13>), the best known compression without any use of a reference is 567 MB (1.45 bits/bp; 1.80 bits/distinct canonical 31-mer).
  
  Upper estimates of genome compressibility can be made using standard general or specialized compressors (see, e.g., [this comparison](https://academic.oup.com/gigascience/article/9/7/giaa072/5867695)). 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`). The compression performance can be further boosted by using a large dictionary (`-e --lzma2=preset=9,dict=512MiB`). 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 CHM13v2 assembly, `xz` compresses the human genome to 634 MB.
  
  However, even better performance can be achieved with specialized compressors, especially if they have particular support for reverse complements and mutational models. Among the best ones is GeCo3, which has been shown to compress CHM13v2, with a particular combination of parameters, to 567 MB [3](https://github.com/pratas/HumanGenome).
  
  Lower estimates are impossible in general (we can't reject the existence of a program that would create the whole sequence from small amount of starting conditions), but can be done for particular compression techniques, e.g., particular variants of dictionary compressors. However, this leads to intractable optimization problems (see e.g. the problem of minimal string attractors).
  
  A useful auxiliary measure for estimating the compressibility of single genomes is the number of distinct k-mers for a "reasonably" selected k (e.g., k=31). The lower bound on the compressibility of k-mer sets can then be roughly approximated by [2 bits per distinct k-mer](https://arxiv.org/abs/1401.5383), however, this is limited by the embedded structural assumptions, e.g., that single genomes are in principle random strings with occasional (possibly distant) repeats. For instance, the CHM13v2 human genome assembly contains 2,512,390,070 distinct canonical 31-mers, which would then correspond to 628 MB assuming 2bits/kmers, while the best available specialized compressors can compress it down to 567 MB, i.e., by approx 10% better.
  
  **Updates**
  
  * May 27, 2022 – updated the upper bound based on the latest results with CHM13v2 (xz & GeCo3), changed the lower bound wording to an auxiliary estimate as the assumptions have shown not to hold
  
  
  ---
  
  ### Answer by username_2 on 2021-06-11. Score: 5
  
  There's a benchmark that compared dozens of compressors on DNA data, including human genome: <http://username_2.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://username_2.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.
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_1**: 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.  
  > **username_1**: 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').  
  > **username_2**: @username_3, cleaning is one reason, another is that it's just different genome build. Though as you see username_1 obtain similar number with his method.  
  > **username_2**: @username_1, by the way, it's good idea to tweak xz's dict (dict=512MiB), I should benchmark this setting too. Thanks.  
  > **username_3**: Thanks both, although you are right username_2, that in real-life situation you don't want to lose information about softmasked bases, the OP asked about the number of bites to store the human genome, therefore username_1's approach is completely valid (human genome does not have really softmasked bases, that's just our way how to add there one more layer of information).  Both of you, would you like to update the answers? I think this discussion is really interesting.  
  > **username_2**: @username_3, I updated the answer. You're right that it's just one way of representing a genome, and also many genomes don't include soft-mask (e.g. prokaryote genomes).  
  
  ---
  
  