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

91–100 of 118 posts

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

#91

Post by Terr_ »

LeifCarrotson wrote: post #83
jefftk wrote: post #19

The FASTA format looks like: > title bases with optional newlines > title bases with optional newlines ... The author is talking about removing the non-semantic optional newlines (hard wrapping), not all the newlines in the file. It makes a lot of sense that this would work: bacteria have many subsequences in common, but if you insert non-semantic newlines at effectively random offsets then compression tools will not…

In case "bases with optional newlines" wasn't obvious to anyone else, a specific example (from Wikipedia) is: ;LCBO - Prolactin precursor - Bovine MDSKGSSQKGSRLLLLLVVSNLLLCQGVVSTPVCPNGPGNCQVSLRDLFDRAVMVSHYIHDLSS EMFNEFDKRYAQGKGFITMALNSCHTSSLPTPEDKEQAQQTHHEVLMSLILGLLRSWNDPLYHL VTEVRGMKGAPDAILSRAIEIEEENKRLLEGMEMIFGQVIPGAKETEPYPVWSGLPSLQTKDED ARYSAFYNLLHCLRRDSSKIDTYLKLLNCRIIYNNNC* where "SS...EM", HL..VT", or "ED..AR" m…

Huh, so in other words: "If you don't arbitrarily interrupt continuous sequences of data with cosmetic noise, they compress better."

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

#92

Post by im3w1l »

fwip wrote: post #88
im3w1l wrote: post #42

As someone with an idle interest in data compression, ss it possible to download the original dataset somewhere to play around with? Or rather a like 20gb subset of it.

The article links to the dataset here: https://ftp.ebi.ac.uk/pub/databases/ENA2018-bacteria-661k/

Ahh, I didn't notice that there were two adjacent links. I must have clicked the first one and gotten the article rather than the ftp.

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

#93

Post by optionalsquid »

FL33TW00D wrote: post #75
jefftk wrote: post #41

Earlier quoted context omitted.

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

https://www.biorxiv.org/content/10.1101/2025.04.08.647863v1....

The fact that these formats are unable to represent degenerate bases (Ns in particular, but also the remaining IUPAC bases), in my experience renders them unusable for many, if not most, use-cases, including for the storage of FASTQ data

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

#94

Post by dwattttt »

boothby wrote: post #58
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.

Spend a few years handling data in arcane, one-off, and proprietary file formats conceived by "brilliant" programmers with strong CS backgrounds and you might reconsider the conclusion you've come to here.

This is a presentation problem, or possibly a lack of tooling problem.

A binary format with a tool that renders it to text works the same as a text format; if the rendering is lossless, you could even consume the text format rather than the binary.

A "text" format is built to be understandable, but that's not a requirement; you could write a text format that isn't descriptive, and you'd have just as much trouble understanding what 'A' means as you would understanding what 'C0' means for a binary format.

Undocumented formats are a pain, whether they're in text or binary.

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

#95

Post by dekhn »

tialaramex wrote: post #86
bede wrote: post #27

Earlier quoted context omitted.

Thank you for clarifying this – yes the non-semantic nature of these particular line breaks is a key detail I omitted.

It might be worth (in some other context) introducing a pre-processing step which handles this at both ends. I'm thinking like PNG - the PNG compression is "just" zlib but for RGBA that wouldn't do a great job, however there's a (per row) filter step first, so e.g. we can store just the difference from the row above, now big areas of block colour or vertical stripes are mostly zeros and those compress well. Guessing…

For one approach to compressing FASTQ (which is a series 3 distinct lines), we broke the distinct lines each into their own streams and then compressed each stream independently. That way the coder for the header line, sequence line, and error line could learn the model of that specific line type and get slightly better compression (not unlike a columnar format, although in this case, we simply combined "blocks" of streams together with a record separator.

I'm still pretty amazed that periodic newlines hurt compression ratios so much, given the compressor can use both a huffman coding and a lookback dictionary.

The best rule in sequence data storage is to store as little of it as possible.

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

#96

Post by dekhn »

mylons wrote: post #74
jefftk wrote: post #19

The FASTA format looks like: > title bases with optional newlines > title bases with optional newlines ... The author is talking about removing the non-semantic optional newlines (hard wrapping), not all the newlines in the file. It makes a lot of sense that this would work: bacteria have many subsequences in common, but if you insert non-semantic newlines at effectively random offsets then compression tools will not…

this is also the insight that the bwa developer had, to use the burrows-wheeler transform which is part of bzip2 due to it's compression properties being particularly good for genomic sequences.

I once had the distinct pleasure of hosting the author of BWA (R. Durbin) at Google, and pointing out "That's Mike Burrows, over there, next to Jeff Dean and Sanjay Ghemawat". That led to an interesting discussion between Durbin and Dean on DNA sequence compression. It's not the first time I've been in a room with a bunch of geniuses and simply kept my mouth shut so nobody would know I'm an idiot.

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

#97

Post by dwattttt »

optionalsquid wrote: post #93
FL33TW00D wrote: post #75

Earlier quoted context omitted.

https://www.biorxiv.org/content/10.1101/2025.04.08.647863v1....

The fact that these formats are unable to represent degenerate bases (Ns in particular, but also the remaining IUPAC bases), in my experience renders them unusable for many, if not most, use-cases, including for the storage of FASTQ data

The question of how to represent things not specified in the original format is a tough one.

At the loosest end a format can leave lots of space for new symbols, and you can just use those to represent something new. But then not everyone agrees on what the new symbol means, and worse multiple groups can use symbols to mean different things.

On the other end of the spectrum, you can be strict about the format, and not leave space for new symbols. Then to represent new things you need a new standard, and people to agree on it.

It's mostly a question of how well code can be updated and agreed upon, how strict you can require your tooling to be w.r.t. formats.

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

#98

Post by kevincox »

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

Size of content does matter. Because the start of your content effectively builds up a dictionary. Once you have built a custom dictionary from the content you are compressing the initial dictionary is no longer relevant. So a dictionary effectively only helps at the start of the content. Exactly what "start" means will depend on your data and the algorithm but as the size of the data you compress grows the relative benefit of the dictionary drops.

Or another way to look at this is that the total bytes saved of the dictionary will plateau. So your dictionary may save 50% of the first MB, 10% of the next MB and 5% of the rest of the first 10MB. It matters a lot if you are compressing 2MB of data (7% savings!) but not so much if you are compressing 1GB (<1%).

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

#99

Post by melagonster »

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…

Yes, If someone want, they can do many analyses by grep!

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

#100

Post by melagonster »

dwattttt wrote: post #97
optionalsquid wrote: post #93

Earlier quoted context omitted.

The fact that these formats are unable to represent degenerate bases (Ns in particular, but also the remaining IUPAC bases), in my experience renders them unusable for many, if not most, use-cases, including for the storage of FASTQ data

The question of how to represent things not specified in the original format is a tough one. At the loosest end a format can leave lots of space for new symbols, and you can just use those to represent something new. But then not everyone agrees on what the new symbol means, and worse multiple groups can use symbols to mean different things. On the other end of the spectrum, you can be strict about the format, and no…

The problem is IUPAC just exists.
Post reply on HN