Hacker News Reader

Comment by actually_a_dog | Hacker News Reader

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.

View on HN

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.

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

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...

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.

Reply on news.ycombinator.com