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

51–60 of 118 posts

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

#51

Post by optionalsquid »

jakobnissen wrote: post #31
semiinfinitely wrote: post #21

Earlier quoted context omitted.

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?

I don't dislike the format, and it is much, much better than what it replaced, but SAM, and its binary sister-format BAM, does have some flaws:

- The original index format could not handle large chromosomes, so now there are two index formats: .bai and .csi

- For BAM, the CIGAR (alignment description) operation count is limited to 16 bits, which means that very long alignments cannot be represented. One workaround I've seen (but thankfully not used) is saving the CIGAR as a string in a tag

- SAM cannot unambiguously represent sequences with only a single base (e.g. after trimming), since a '*' in the quality column can be interpreted either as a single Phred score (9) or as a special value meaning "no qualities". BAM can represent such sequences unambiguously, but most tools output SAM

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

#52

Post by leobuskin »

tecleandor wrote: post #44
bede wrote: post #10

Earlier quoted context omitted.

Yes I'd expect a dict-based approach to do better here. That's probably how it should be done. But --long is compelling for me because using it requires almost no effort, it's still very fast, and yet it can dramatically improve compression ratio.

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

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

#53

Post by rurban »

IshKebab wrote: post #20

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

Ha. it gets worse. Search engines or blacklist processors often use gigantic url lists, which are stored as plain ASCII, which is then fed into a perfect hash generator, which accesses those url's unordered. I.e. they need to create a second ordering index to access the urllist. The perfect hashing guys are mathematicians and so they don't care because their definition of a mphf (minimal perfect hash function) is just a random ordering of unique indices, but they don't care to store the ordering also. So we have ASCII and no index.

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

#54

Post by lutusp »

> I speculated that this poor performance might be caused by the newline bytes (0x0A) punctuating every 60 characters of sequence, breaking the hashes used for long range pattern matching.

If the linefeeds were treated as semantic characters and not allowed to break the hash size, you would get similar results without pre-filtering and post-filtering. It occurs to me that this strategy is so obvious that there must be some reason it won't work.

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

#55

Post by lazide »

vintermann wrote: post #47
jltsiren wrote: post #28

Earlier quoted context omitted.

Basic text formats persist, because everyone supports them. Many tools have better file formats for internal purposes, but they are rarely flexible enough and robust enough for wider use. There are occasional proposals for better general purpose formats, but the people proposing them rarely agree which of the competing proposals should be adopted. And even if they manage to agree, they probably don't have the time an…

Also for historical reasons I think, since Perl used to be the big bioinformatics language, and it is surprisingly hard to compete with in string handling.

Perl+strings really is one of those ‘unreasonably effective’ combinations.

It feels like Benzene in some ways. Use it correctly and gdamn. Just don’t huff it - i mean - use it for your enterprise backend - and it’s worth it.

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

#57

Post by Gethsemane »

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.

Unfortunately, when you write a program that doesn't wrap output FASTAs, you have a bunch of people telling you off because SOME programs (cough bioperl cough) have hard limits on line length :)

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

#58

Post by boothby »

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.
Post reply on HN