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

81–90 of 118 posts

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

#81

Post by jakobnissen »

optionalsquid wrote: post #51
jakobnissen wrote: post #31

Earlier quoted context omitted.

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'…

True. I'd consider these minor flaws. W.r.t. the CIGAR, the spec says you do need to store it as a tag.

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

#82

Post by pkilgore »

To me the most interesting thing here isn't that you can compress something better by removing randomly-distributed semantically-meaningless information. It's why zstd --long does so much better than gzip when you do and the default does worse than gzip.

What lessons can we take from this?

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

#83

Post by LeifCarrotson »

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" may be common subsequences, but the plaintext file arbitrarily wraps at column 65 so it renders on a DEC VT100 terminal from the 70s nicely.

Or, for an even simpler example:

    ; plaintext
    GATTAC
    AGATTA
    CAGATT
    ACCAGA
    TTACAG
    ATTACA
becomes, on disk, something like

    ; plaintext\r\nGATTAC\r\nAGATTA\r\nCAGATT\r\nACCAGA\r\nTTACAG\r\nATTACA\r\n
which is hard to compress, while

    ; plaintext\r\nGATTACAGATTACAGATTACCAGATTACAGATTACA
is just

    "; plaintext\r\n" + "GATTACA" * 7
and then, if you want, you can reflow the text when it's time to render to the screen.

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

#84

Post by chrchang523 »

bede wrote: post #35
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 my…

Note that BGZF solves gzip’s speed problem (libdeflate + parallel compression/decompression) without breaking compatibility, and usually the hit to compression ratio is tolerable.

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

#85

Post by o11c »

Gethsemane wrote: post #57
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 :)

You can use content-defined chunking to wrap at a predictable place so that compression still works.

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

#86

Post by tialaramex »

bede wrote: post #27
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…

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 which PNG filters to use can make a huge difference to compression with only a tiny change to write speed. Or (like Adobe 20+ years ago) you can screw it up and get worse compression and slower speeds. These days brutal "try everything" modes exist which can squeeze out those last few bytes by trying even the unlikeliest combinations.

I can imagine a filter layer which says this textual data comes in 78 character blocks punctuated with \n so we're going to strip those out, then compress and in the opposite direction we decompress then put back the newlines.

For FASTA we can just unconditionally choose to remove the extra newlines but that may not be true for most inputs, so the filters would help there.

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

#87

Post by cogman10 »

pkilgore wrote: post #82

To me the most interesting thing here isn't that you can compress something better by removing randomly-distributed semantically-meaningless information. It's why zstd --long does so much better than gzip when you do and the default does worse than gzip. What lessons can we take from this?

Why it does worse than gzip isn't something that I know. Why --long is so efficient is likely a result of evolution of all things :). A lot of things have common ancestors which means shared genetic patterns across species. --long allows zstd to see a 2gb window of data which means it's likely finding all those genetic similarities across species.

Endogenous retroviruses [1] are interesting bits of genetics that helps link together related species. A virus will inject a bit of it's genetics into the host which can effectively permanently scar the host's DNA and all their offspring's DNA.

[1] https://en.wikipedia.org/wiki/Endogenous_retrovirus

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

#88

Post by fwip »

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/

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

#89

Post by tgtweak »

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…

Feels like it could be an extension to the compression lib (and would retain newlines as such) vs requiring external document tailoring. Also feels like a very specific use case but this optimization might have larger applications outside this narrow field/format.

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

#90

Post by iijj »

diimdeep wrote: post #56

What's current way to accessibly process my 23andme raw data ? It's been synthesized decade ago and SNPedia and Promethease seems abandoned, so what's alternative if there is, and if there is none how we arrived to this?

I was no longer on the scene when it happened, but I’ve been told it became very difficult to get ongoing funding from the National Science Foundation for bioinformatics software around 10 years ago. You could get an initial grant to develop something, but ongoing support was difficult. So websites and ‘databases’ (curated datasets) that made it easy to run the tools faded away.
Post reply on HN