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

31–40 of 118 posts

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

#31

Post by jakobnissen »

semiinfinitely wrote: post #21
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.

other file formats that rival fasta in stupidity include fastq pdb bed sam cram vcf. further reading [1] > "intentionally or not, bioinformatics found a way to survive: obfuscation. By making the tools unusable, by inventing file format after file format, by seeking out the most brittle techniques" 1. https://madhadron.com/science/farewell_to_bioinformatics.htm...

SAM is not a bad file format. What's bad about SAM?

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

#32

Post by bede »

IshKebab wrote: post #20

Damn surely you stop using ASCII formats before your dataset gets to 2 TB??

BAM format is widely used but assemblies still tend to be generated and exchanged in FASTA text. BAM is quite a big spec and I think it's fair to say that none of the simpler binary equivalents to FASTA and FASTQ have caught on yet (XKCD competing standards etc.)

e.g. https://github.com/ArcInstitute/binseq

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

#33

Post by jszymborski »

Fraterkes wrote: post #22
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.

I’ll do you the immense favor of taking the bait. What’s so bad about it?

It's a fine format for what it is.

A parser to stream FASTA can be written in like 30 lines [0], much easier than say CSV where the edge cases can get hairy.

If you need something like fast random reads, use the FAIDX format [1], or even better just store it in an LMDB or SQLite embedded db.

People forget FASTA was from 1985, and it sticks around because (1) it's easy to parse and write (2) we have mountains of sequences in that format going back 4 decades.

[O] https://gist.github.com/jszym/9860a2671dabb45424f2673a49e4b5...

[1] https://seqan.readthedocs.io/en/main/Tutorial/InputOutput/In...

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

#34

Post by dwattttt »

hyghjiyhu wrote: post #8
dwattttt wrote: post #5

Earlier quoted context omitted.

The FASTA format stores nucleotides in text form... compression is used to make this tractable at genome sizes, but it's by no means perfect. Depending on what you need to represent, you can get a 4x reduction in data size without compression at all, by just representing a GATC with 2 bits, rather than 8. Compression on top of that "should" result in the same compressed size as the original text (after all, the "info…

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.

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

#35

Post by bede »

ashvardanian wrote: post #16

Nice observation! Took me a while to realize that Grace Blackwell refers to a person and not an Nvidia chip :) I’ve worked with large genomic datasets on my own dime, and the default formats show their limits quickly. With FASTA, the first step for me is usually conversion: unzip headers from sequences, store them in Arrow-like tapes for CPU/GPU processing, and persist as Parquet when needed. It’s straightforward, bu…

Yes, when doing anything intensive with lots of sequences it generally makes sense to liberate them from FASTA as early as possible and index them somehow. But as an interchange format FASTA seems quite sticky. I find the pervasiveness of fastq.gz particularly unfortunate with Gzip being as slow as it is.

> Took me a while to realize that Grace Blackwell refers to a person and not an Nvidia chip :)

I even confused myself about this while writing :-)

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

#36

Post by [deleted] »

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…

[deleted]

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

#38

Post by amelius »

vintermann wrote: post #7
Kim_Bruning wrote: post #4

Now I'm wondering why this works. DNA clearly has some interesting redundancy strategies. (it might also depend on genome?)

This is a dataset of bacterial DNA. Any two related bacteria will have long strings of the same letters. But it won't be neatly aligned, so the line breaks will mess up pattern matching.

And the compressor does not think: "how can I make these two sequences align better without wasting a lot of space?"

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

#39

Post by amelius »

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 was a question that I thought was interesting enough to test ChatGPT with.

Surprisingly, it gave an answer along the lines of the parent comment.

However, it seems it didn't figure this out by itself but it says:

> It’s widely known in bioinformatics that “one-line Fasta” files compress much better with LZ-based algorithms, and this is discussed in forums, papers, and practical guides on storing genomic data.

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

#40

Post by jefftk »

shellfishgene wrote: post #30
AndrewOMartin wrote: post #26

Earlier quoted context omitted.

The compression ratio will likely skyrocket if you sorted the list of bases.

You're joking, but a few bioinformatics tools use the Burrows-Wheeler transform to save memory, which is a bit like sorting the bases.

You can also improve compression by reordering the sequences within the FASTA file, as long as you're using it as a dictionary and not a list of title-sequence pairs.
Post reply on HN