Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Removing newlines in FASTA file increases ZSTD compression ratio by 10x

log.bede.im

Post reply on HN
Print view View original

61–70 of 118 posts

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#61

Post by mfld »

lifthrasiir wrote: post #15
mfld wrote: post #11

Using larger-than-default window sizes has the drawback of requiring that the same --long=xx argument be passed during decompression reducing compatibility somewhat. Interesting. Any idea why this can't be stored in the metadata of the compressed file?

It is stored in the metadata [1], but anything larger than 8 MiB is not guaranteed to be supported. So there has to be an out-of-band agreement between compressor and decompressor. [1] https://datatracker.ietf.org/doc/html/rfc8878#name-window-de...

Thanks! So the --long essentially signals the decoder "I am willing to accept the potentially large memory requirements implied by the given window size"

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#62

Post by fwip »

jefftk wrote: post #41
FL33TW00D wrote: post #25

Looking forward to the relegation of FASTQ and FASTA to the depths of hell where they belong. Incredibly inefficient and poorly designed formats.

How so? As long as you remove the hard wrapping and use compression aren't they in the same range as other options? (I currently store a lot of data as FASTQ, and smaller file sizes could save us a bunch of money. But FASTQ + zstd is very good.)

There's a few options out there that have noticeably better compression, with the downside of being less widely-compatible with tools. zstd also has the benefit of being very fast (depending on your settings, of course).

CRAM compresses unmapped fastq pretty well, and can do even better with reference-based compression. If your institution is okay with it, you can see additional savings by quantizing quality scores (modern Illumina sequencers already do this for you). If you're aligning your data anyways, probably retaining just the compressed CRAM file with unmapped reads included is your best bet.

There are also other fasta/fastq specific tools like fqzcomp or MZPAQ. Last I checked, both of these could about halve the size of our fastq.gz files.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#63

Post by totalperspectiv »

bede wrote: post #60
totalperspectiv wrote: post #49

Removing the wrapping newline from the FASTA/FASTQ convention also dramatically improves parsing perf when you don't have to do as much lookahead to find record ends.

Thanks for reminding me to benchmark this!

I've only tested this when writing my own parser where I could skip the record end checks, so idk if this improves perf on a existing parser. Excited to see what you find!

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#65

Post by fwip »

semiinfinitely wrote: post #18

FASTA is a candidate for the stupidest file format ever invented and a testament to the massive gap in perceived vs actual programming ability of the average bioinformatician.

It might be the stupidest, but stupid in the sense of "the simplest thing that could possibly work."

When FASTA was invented, Sanger sequencing reads would be around a thousand bases in length. Even back then, disk space wasn't so precious that you couldn't spend several kilobytes on the results of your experiment. Plus, being able to view your results with `more` is a useful feature when you're working with data of that size.

And, despite its simplicity, it has worked for forty years.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#66

Post by privatelypublic »

leobuskin wrote: post #52
tecleandor wrote: post #44

Earlier quoted context omitted.

From what I've read (although I haven't tested and I can't find my source from when I read it), dictionaries aren't very useful when dataset is big, and just by using '--long' you can cover that improvement. Have any of you tested it?

I don’t think the size of content matters, it’s all about patterns (and their repetitiveness) within, and FASTA is a great target, if I understand the format correctly

I tried building a zstd dictionary for something(compressing many instances of the same Mono(.net) binary serialized class, mostly identical), and in this case it provided no real advantage. Honestly, I didn't dig into it too much, but will give --long a try shortly.

PS: what the author implicitly suggests cannot be replaced with zstd tweaks. It'll be interesting to look at the file in imhex- especially if I can find an existing Pattern File.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#67

Post by Sesse__ »

dwattttt wrote: post #34
hyghjiyhu wrote: post #8

Earlier quoted context omitted.

I think one important factor you missed to account for is frameshifting. Compression algorithms work on bytes - 8 bits. Imagine that you have the exact same sequence but they occur at different offsets mod 4. Then your encoding will give completely different results, and the compression algorithm will be unable to make use of the repetition.

I was actually under the impression compression algorithms tend to work over a bitstream, but I can't entirely confirm that.

Some are bit-by-bit (e.g. the PPM family of compressors[1]), but the normal input granularity for most compressors is a byte. (There are even specialized ones that work on e.g. 32 bits at a time.)

[1] Many of the context models in a typical PPM compressor will be byte-by-byte, so even that isn't fully clear-cut.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#68

Post by dekhn »

I've explored alternatives to FASTA and FASTQ but in most cases I found that simply not storing sequence data is the best option of all, but if I have to do it, columnar formats with compression are usually the best alternative when considering all of (my) the constraints.

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#69

Post by felixhandte »

This is because Zstd's long-distance matcher looks for matching sequences of 64 bytes [0]. Because long matching sequences of the data will likely have the newlines inserted in different offsets in the run, this totally breaks Zstd's ability to find the long-distance match.

Ultimately, Zstd is a byte-oriented compressor that doesn't understand the semantics of the data it compresses. Improvements are certainly possible if you can recognize and separate that framing to recover a contiguous view of the underlying data.

[0] https://github.com/facebook/zstd/blob/v1.5.7/lib/compress/zs...

(I am one of the maintainers of Zstd.)

Re: Removing newlines in FASTA file increases ZSTD compression ratio by 10x

#70

Post by michaelhoffman »

fwip wrote: post #65
semiinfinitely wrote: post #18

FASTA is a candidate for the stupidest file format ever invented and a testament to the massive gap in perceived vs actual programming ability of the average bioinformatician.

It might be the stupidest, but stupid in the sense of "the simplest thing that could possibly work." When FASTA was invented, Sanger sequencing reads would be around a thousand bases in length. Even back then, disk space wasn't so precious that you couldn't spend several kilobytes on the results of your experiment. Plus, being able to view your results with `more` is a useful feature when you're working with data of…

When FASTA was invented in 1985, generally sequencing reads would be about half that.

The simplicity of FASTA seems like a dream compared to the GenBank flat file format used before then. And around the year 2000, less computationally-inclined scientists were storing sequence in Microsoft Word binary .doc files.

A lot of file formats (including bioinformatics formats!) have come and gone in that time period. I don't think many would design it this way today, but it has a lot of nice features like the ones you point out that led to its longevity.

Post reply on HN