Hacker News Reader

Comment by croemer | Hacker News Reader

Yep, I've been advocating zstd since I started working in the field. It compresses and decompresses so much faster than xz and is much much more compact than gzip. All public SARS-CoV-2 consensus sequences are ~300GB uncompressed. If you compress using gzip you end up with ~30GB. With xz/zstd you can get it down to ~2GB. However xz takes ~40min to uncompress, whereas zstd can do it in ~8min.

View on HN

For compressing similar genomes, specialized tools will do better. AGC [1] can compress 620k SARS-CoV-2 genomes (19 GB uncompressed) into tens of MB. More importantly, AGC allows you to extract individual sequences without decompressing the entire file. In addition, zstd/xz wouldn't have a big enough dictionary to compress multiple human genomes efficiently. AGC can compress 300 GB human assemblies to 1.5 GB, a 200-fold compression ratio.

I agree for sequence reads, zstd is better than gzip in almost every aspect. The only problem is that zstd is not as widely available. Many Linux distros don't ship zstd by default but on managed clusters, common users don't have the root permission to install zstd system-wide.

It is worth mentioning that many mainstream bioinformatics tools can read FASTQ over pipes. You can use something like

  mytool <(zstd -dc in.fastq.zst) > output.txt   # bash; also works on multiple zstd input files
  zstd -dc in.fastq.zst | mytool - > output.txt  # general; for multiple input files, use mkfifo

Those who prefer zstd can use it now.

[1] https://www.biorxiv.org/content/10.1101/2022.04.07.487441v1

Unfortunately some bioinformatics tools require multiple passes over the FASTQ. Spades is an example of this.

Fair enough. For the relatively few tools that don’t support streaming, you may generate temporary plain files in your pipeline. Spades itself is a pipeline and writes temporary files. It is anyway not realistic to expect wide adoption of zstd in the near future. If you want to save storage cost now, you have to take some trade off.

Same. If nothing else zstd universally supports compression and decompression with threading across any number of cores. It will even adjust threads dynamically based on the next limiting factor (I/O speed). Meanwhile it's also generally faster and provides significantly better compression ratios (as you describe).

In my mind "always threading, everywhere" is reason enough to always use zstd. Sure there are implementations for other compression algorithms that support threading but the reference zstd implementation from Facebook always does, everywhere.

Curious, how long would Gzip take to uncompress? Is it faster since it is less compact / efficient on the compression side?

The bitstream format for Gzip files (PKZIP's "deflate") was established in 1993. In comparison, the much newer Zstd doesn't represent a different tradeoff between compression time / decompression time / size; it's just better overall. There's a nice graph of the different time/compression tradeoffs both can achieve about 1/3rd of the way into https://engineering.fb.com/2016/08/31/core-data/smaller-and-...

Decompression speed is one of zstd's biggest advantages (in its class, lz4 is obviously faster in return for worse compression ratios). Zstd decompression is generally at least factor 3 faster than gzip.

Since the gzip’ed file is larger, it might well be slower since more IO is required. Depends on the case in question, obviously.

To put that in perspective, consider that a large portion of the file is literally a nucleotide sequence, e.g. "GGGTGATGGCCGCTGCCGATGGCGTCAAATCCCACC" and that the rest of the file format is also fairly repetitive. If we just imagine only the nucleotide sequence, one way to compress that would be to take advantage of going from an 8 bit alphabet (ASCII encoding) to a 4 bit alphabet (CGAT). Naively, you'd expect ~50% compression from that alone, and be left with a bit stream that's still compressible.

Apart from CGAT being a 2-bit alphabet, changing the alphabet does not change the information density. Expect that this kind of transformation has no impact on the compressed result, with most general purpose algorithms.

Unfortunately, however, FASTQ files have more characters than ACGT and (N). They include a second line that encodes sequence quality. In practice, that line is even more compressible, but it complicates things.

(And of course the label on each entry is just standard 7-bit ascii), and also very compressible, but it contains higher complexity text.

> In practice, that line is even more compressible, but it complicates things.

It depends: for some platforms (ex: NextSeq) the quality score in binned and highly compressible, but for others (ex: Nanopore) it's much higher entropy than the sequence.

Yeah, it would seem to me (as an uneducated moron looking from the outside) that if you have domain knowledge about what is being compressed, a specialized compression algorithm would be much better overall than a generic one.

Especially if major portions of the files are repeated.

Oh I wish it was easier to build these custom compression algorithms (or to help the existing ones). Whenever you know something about the file format, content, ranges of data, even sequence information...

Exactly. We have special lossless formats for music and images.

Wouldn't CGAT be a 2-bit alphabet, bringing file size to 25% of the original? Assuming you go for a binary format with length headers, so you don't need to reserve control characters.

Wouldn't you only need two bits to encode C, G, A, and T?

Yes, two bits (assuming you only need to encode those four bases; unfortunately, biological reality requires FASTQ to encode other nucleotide values). There's even a format from UCSC called "2bit" (https://genome.ucsc.edu/goldenPath/help/twoBit.html)

> going from an 8 bit alphabet (ASCII encoding) to a 4 bit alphabet (CGAT).

ASCII in the strict sense is 7-bit, CGAT is 2-bit.

Yeah, 2 bit vs 4 bit is my bad. It doesn't really change much though, except to strengthen the conclusion and just makes gzip's 10:1 compression ratio even less impressive.

I'm counting ASCII as 8 bits because it's still stored as 8 bits regardless of whether you only use 7 of them.

I wonder how well a zstd dictionary will work against these kinds of data sets.

Using a custom dictionary works well if you want to compress single consensus sequences (30kbp), say before putting them into an sqlite db. Then you can get each sequence down to ~200 bytes. If you compress a large dataset, there's no point in using a custom dictionary, the auto-embedded one works just fine.

They're big enough that it shouldn't help. Dictionaries are useful when you're compressing tiny files such that the overhead of the compressor learning the statistics from the input is significant. Basically you hope to save a fraction of the size of the dictionary from each file. From a 2GB file that's negligible. From a 1000 byte file it could be gigantic.

I've never seen a 15x difference in density between gzip and zstd on genomic data in an apples-to-apples comparison; I'd be really curious to learn more about how you achieved that.

hm. Surely SARS-CoV-2 RNA sequence for one virus itself isn't 300gb? does it contain multiple variants or unprocessed and unjoined fragments?

The 300GB is for "all public sequences", as explained.

But to answer your question about "one virus", the initial isolate of SARS-CoV-2 from Wuhan, China has a genome containing 29,903 nucleotides. You can see the full raw sequence by clicking on "FASTA" on this page: https://www.ncbi.nlm.nih.gov/nuccore/1798174254

"All public SARS-CoV-2 consensus sequences"

That seems clear enough.

It's actually ambiguous. It could mean that each sequence is 300GB, or that combined they total 300GB.

Reply on news.ycombinator.com