7 ms·

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

279 points by bede 1y ago

rini17 1y ago
This might in general be a good preprocessing step to check for punctuation repeating in fixed intervals and remove it, and restore after decompression.
- vintermann 1y ago
  That turns in into specialized compression, which DNA already has plenty of. Many forms of specialized compression even allow string-related queries directly on the compressed data.
  - rini17 1y ago
    There are plenty of data formats where data is interspersed with fixed delimiters in fixed intervals.
    - vintermann 1y ago
      In fixed intervals? I'm not so sure about that. Generally if the intervals are fixed, you shouldn't need delimiters, you know where one thing begins and another ends anyway. Anyway, BWT-based compressors like Bzip2 do a good job on "repetition, but with random differences". Better than LZ-based compressors. However, they are not competitive on speed, and it's gotten relatively worse as computers got faster since the Burrows-Wheeler transform can't be parallelized very well and is inherently cache-unfriendly.
      - rini17 1y ago
        All kinds of data - block justified text, database files with fixed row size tables, even HTTP chunked encoding tends to have blocks of same size with same delimiters,... I really don't see how better supporting this "second order repetition" feature in the encoding would cause such a big problem. LZ variants already track repeating strings.
- bede 1y ago
  Yes, it sounds like 7-Zip/LZMA can do this using custom filters, among other more exotic (and slow) statistical compression approaches.
Kim_Bruning 1y ago
Now I'm wondering why this works. DNA clearly has some interesting redundancy strategies. (it might also depend on genome?)
- dwattttt 1y ago
  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 "information" being compressed is the same), except that compression isn't perfect. Newlines are an example of something that's "information" in the text format that isn't relevant, yet the compression scheme didn't know that.
  - hyghjiyhu 1y ago
    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.
    - dwattttt 1y ago
      I was actually under the impression compression algorithms tend to work over a bitstream, but I can't entirely confirm that.
      - vintermann 1y ago
        They output a bitstream, yeah but I don't know of anything general purpose which effectively consumes anything smaller than bytes (unless you count various specialized handlers in general-purpose compression algorithms, e.g. to deal with long lists of floats)
      - 1y ago
leobuskin 1y ago
What about a specialized dict for FASTA? Shouldn't it increase ZSTD compression significantly?
- bede 1y ago
  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.
  - tecleandor 1y ago
    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?
    - leobuskin 1y ago
      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
      - privatelypublic 1y ago
        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.
      - kevincox 1y ago
        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%).
mfld 1y ago
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?
- nolist_policy 1y ago
  It uses more memory (up to +2gb) during decompression as well -> potential DoS.
  - Aachen 1y ago
    Sending a .zip filled with all zeroes, so it compresses extremely well, is a well-known DoS historically (zip bomb, making the server run out of space in trying to read the archive) You always need resource limits when dealing with untrusted data. RAM is one of the obvious ones. They could introduce a memory limit parameter; require passing --long with a value equal to or greater than what the stream requires to successfully decompress; require seeking support for the input stream so they can look back that way (TMTO); fall back to using temp files; or interactively prompt the user if there's a terminal attached. Lots of options, each with pros and cons of course, that would all allow a scenario where the required information for the decoder is stored in the compressed data file
    - dzaima 1y ago
      The decompressed output needn't be in-memory (or even on-disk; it could be directly streamed to analysis) all at the same time, at which point resource limits aren't a problem at all. And I believe --long already is a "grater than or equal to" value, and should also be effectively a memory limit (or pretty close to one at least). Seeking back in the input might theoretically work, but I feel like that could easily get very bad (aka exponential runtime); never mind needing actual seeking.
- lifthrasiir 1y ago
  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-descriptor https://datatracker.ietf.org/doc/html/rfc8878#name-window-de...
ashvardanian 1y ago
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, but surprisingly underused in bioinformatics — most pipelines stick to plain text even when modern data tooling would make things much easier :(
- jltsiren 1y ago
  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 and the money to make it actually happen.
  - vintermann 1y ago
    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.
    - lazide 1y ago
      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.
- bede 1y ago
  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 :-)
Aachen 1y ago
I've also noticed this. Zstandard doesn't see very common patterns For me it was an increasing number (think of unix timestamps in a data logger that stores one entry per second, so you are just counting up until there's a gap in your data), in the article it's a fixed value every 60 bytes Of course, our brains are exceedingly good at finding patterns (to the point where we often find phantom ones). I was just expecting some basic checks like "does it make sense to store the difference instead of the absolute value for some of these bytes here". Seeing as the difference is 0 between every 60th byte in the submitted article, that should fix both our issues Bzip2 performed much better for me but it's also incredibly slow. If it were only the compressor, that might be fine for many applications, but also decompressing is an exercise in patience so I've moved to Zstandard at the standard thing to use
- pajko 1y ago
  Bzip2 performs exactly better because it rearranges the input to achieve better pattern matches: https://en.m.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.m.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_tran...
  - vintermann 1y ago
    A number of identical copies of a string, but with random mutations propagating through it like a word ladder puzzle, is pretty close to best-case for BWT-based compressors. But Bzip2 is also a pretty bad BWT-based compressor. Not only does it use block sizes from a time when 8mb memory was a lot, it does silly things which doesn't help compression at all.
semiinfinitely 1y ago
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.
- semiinfinitely 1y ago
  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.html https://madhadron.com/science/farewell_to_bioinformatics.htm...
  - jakobnissen 1y ago
    SAM is not a bad file format. What's bad about SAM?
    - optionalsquid 1y ago
      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
      - jakobnissen 1y ago
        True. I'd consider these minor flaws. W.r.t. the CIGAR, the spec says you do need to store it as a tag.
jefftk 1y ago
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 be able to use the repetition effectively.
- AndrewOMartin 1y ago
  The compression ratio will likely skyrocket if you sorted the list of bases.
  - shellfishgene 1y ago
    You're joking, but a few bioinformatics tools use the Burrows-Wheeler transform to save memory, which is a bit like sorting the bases.
    - jefftk 1y ago
      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.
- bede 1y ago
  Thank you for clarifying this – yes the non-semantic nature of these particular line breaks is a key detail I omitted.
  - tialaramex 1y ago
    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.
IshKebab 1y ago
Damn surely you stop using ASCII formats before your dataset gets to 2 TB??
- hhh 1y ago
  no, I power thru indefinitely with no recourse
- bede 1y ago
  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 https://github.com/ArcInstitute/binseq
- amelius 1y ago
  People rely on compression for that ;)
- rurban 1y ago
  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.
- deleted 1y ago
  [deleted]
FL33TW00D 1y ago
Looking forward to the relegation of FASTQ and FASTA to the depths of hell where they belong. Incredibly inefficient and poorly designed formats.
- jefftk 1y ago
  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.)
  - fwip 1y ago
    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.
  - FL33TW00D 1y ago
    https://www.biorxiv.org/content/10.1101/2025.04.08.647863v1.full.pdf https://www.biorxiv.org/content/10.1101/2025.04.08.647863v1....
    - optionalsquid 1y ago
      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
im3w1l 1y ago
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.
- fwip 1y ago
  The article links to the dataset here: https://ftp.ebi.ac.uk/pub/databases/ENA2018-bacteria-661k/ https://ftp.ebi.ac.uk/pub/databases/ENA2018-bacteria-661k/
  - im3w1l 1y ago
    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.
nickdothutton 1y ago
How can we represent data or algos such that such optimisations before more obvious?
keketi 1y ago
When you know you're going to be compressing files of particular structure, it's often very beneficial to tweak compression algorithm parameters. In one case when dealing with CSV data, I was able to find a LZMA2 compression level, dictionary size and compression mode that yielded a massive speedup, uses 1/100th the memory and surprisingly even yields better compression ratios, probably from the smaller dictionary size. That's in comparison to the library's default settings.
- ciupicri 1y ago
  Could you please provide more details, perhaps give an example?
totalperspectiv 1y ago
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.
- Gethsemane 1y ago
  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 :)
  - o11c 1y ago
    You can use content-defined chunking to wrap at a predictable place so that compression still works.
  - sharedptr 1y ago
    Is BioPerl still standard, did people move to BioPython? When I was shown BioPerl I was tempted to write a better, C++ version, but was overwhelmed by other university stuff and let it go.
- bede 1y ago
  Thanks for reminding me to benchmark this!
  - totalperspectiv 1y ago
    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!
lutusp 1y ago
> 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.
diimdeep 1y ago
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?
- iijj 1y ago
  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.
- vintermann 1y ago
  What format is the 23andMe data in, by the way?
  - diimdeep 1y ago
    tab delimited file (usually compressed for distribution), containing the fields rsid, chromosome, position, genotype (e.g. rs3094315 1 742429 AG).
dekhn 1y ago
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.
felixhandte 1y ago
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/zstd_ldm.c#L20 https://github.com/facebook/zstd/blob/v1.5.7/lib/compress/zs... (I am one of the maintainers of Zstd.)
- nerpderp82 1y ago
  That is fascinating. I wonder if you could layer a Levenshtein State Machine on the strings so you can apply n-edits to the text to get longer matches. I absolutely adore ZSTD, it has worked so well for me compressing json metadata for a knowledge engine.
  - felixhandte 1y ago
    Zstd has a similar-ish capability called "repetition codes" [0]. The first stage of Zstd does LZ77 matching, which transforms the input into "sequences", a series of instructions each of which describes some literals and one match. The literals component of the instruction says "the next L bytes of the message are these L bytes". The match component says "the next M bytes of the input are the M bytes N bytes ago". If you want to construct a match between two strings that differ by one character, rather than saying "the next N bytes are the N bytes M bytes ago except for this one byte here which is X instead", Zstd just breaks it up into two sequences, the first part of the match, and then a single literal byte describing the changed byte, and then the rest of the match, which is described as being at offset 0. The encoding rules for Zstd define offset 0 to mean "the previously used match offset". This isn't as powerful as a Levenshtein edit, but it's a reasonable approximation. The big advantage of this approach is that it doesn't require much additional machinery on the encoder or decoder, and thus remains very fast. Whereas implementing a whole edit description state machine would (I think) slow down decompression and especially compression enormously. [0] https://datatracker.ietf.org/doc/html/rfc8878#name-repeat-offsets https://datatracker.ietf.org/doc/html/rfc8878#name-repeat-of...
meel-hd 1y ago
https://github.com/meel-hd/DNA https://github.com/meel-hd/DNA
pkilgore 1y ago
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?
- cogman10 1y ago
  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 https://en.wikipedia.org/wiki/Endogenous_retrovirus
a_bonobo 1y ago
There's some discussion here about DNA-specific compression algorithms. I thought I'd raise yesterday's HN discussion on 'The unreasonable effectiveness of modern sort algorithms' https://news.ycombinator.com/item?id=45208828 https://news.ycombinator.com/item?id=45208828 That blog post isn't about DNA per se, but it is about sorting data when you know there are only 4 numbers. I guess DNA has 5 - A,T,G,C,N the unknown base - but there's a huge space of DNA-specific compression research that outperforms ZSTD.

279 points by bede 1y ago

This might in general be a good preprocessing step to check for punctuation repeating in fixed intervals and remove it, and restore after decompression.

vintermann 1y ago
That turns in into specialized compression, which DNA already has plenty of. Many forms of specialized compression even allow string-related queries directly on the compressed data.
- rini17 1y ago
  There are plenty of data formats where data is interspersed with fixed delimiters in fixed intervals.
  - vintermann 1y ago
    In fixed intervals? I'm not so sure about that. Generally if the intervals are fixed, you shouldn't need delimiters, you know where one thing begins and another ends anyway. Anyway, BWT-based compressors like Bzip2 do a good job on "repetition, but with random differences". Better than LZ-based compressors. However, they are not competitive on speed, and it's gotten relatively worse as computers got faster since the Burrows-Wheeler transform can't be parallelized very well and is inherently cache-unfriendly.
    - rini17 1y ago
      All kinds of data - block justified text, database files with fixed row size tables, even HTTP chunked encoding tends to have blocks of same size with same delimiters,... I really don't see how better supporting this "second order repetition" feature in the encoding would cause such a big problem. LZ variants already track repeating strings.
bede 1y ago
Yes, it sounds like 7-Zip/LZMA can do this using custom filters, among other more exotic (and slow) statistical compression approaches.

Kim_Bruning 1y ago

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

dwattttt 1y ago
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 "information" being compressed is the same), except that compression isn't perfect. Newlines are an example of something that's "information" in the text format that isn't relevant, yet the compression scheme didn't know that.
- hyghjiyhu 1y ago
  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.
  - dwattttt 1y ago
    I was actually under the impression compression algorithms tend to work over a bitstream, but I can't entirely confirm that.
    - vintermann 1y ago
      They output a bitstream, yeah but I don't know of anything general purpose which effectively consumes anything smaller than bytes (unless you count various specialized handlers in general-purpose compression algorithms, e.g. to deal with long lists of floats)
    - 1y ago

leobuskin 1y ago

What about a specialized dict for FASTA? Shouldn't it increase ZSTD compression significantly?

bede 1y ago
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.
- tecleandor 1y ago
  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?
  - leobuskin 1y ago
    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
    - privatelypublic 1y ago
      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.
    - kevincox 1y ago
      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%).

mfld 1y ago

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?

nolist_policy 1y ago
It uses more memory (up to +2gb) during decompression as well -> potential DoS.
- Aachen 1y ago
  Sending a .zip filled with all zeroes, so it compresses extremely well, is a well-known DoS historically (zip bomb, making the server run out of space in trying to read the archive) You always need resource limits when dealing with untrusted data. RAM is one of the obvious ones. They could introduce a memory limit parameter; require passing --long with a value equal to or greater than what the stream requires to successfully decompress; require seeking support for the input stream so they can look back that way (TMTO); fall back to using temp files; or interactively prompt the user if there's a terminal attached. Lots of options, each with pros and cons of course, that would all allow a scenario where the required information for the decoder is stored in the compressed data file
  - dzaima 1y ago
    The decompressed output needn't be in-memory (or even on-disk; it could be directly streamed to analysis) all at the same time, at which point resource limits aren't a problem at all. And I believe --long already is a "grater than or equal to" value, and should also be effectively a memory limit (or pretty close to one at least). Seeking back in the input might theoretically work, but I feel like that could easily get very bad (aka exponential runtime); never mind needing actual seeking.
lifthrasiir 1y ago
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-descriptor https://datatracker.ietf.org/doc/html/rfc8878#name-window-de...

ashvardanian 1y ago

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, but surprisingly underused in bioinformatics — most pipelines stick to plain text even when modern data tooling would make things much easier :(

jltsiren 1y ago
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 and the money to make it actually happen.
- vintermann 1y ago
  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.
  - lazide 1y ago
    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.
bede 1y ago
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 :-)

Aachen 1y ago

I've also noticed this. Zstandard doesn't see very common patterns For me it was an increasing number (think of unix timestamps in a data logger that stores one entry per second, so you are just counting up until there's a gap in your data), in the article it's a fixed value every 60 bytes Of course, our brains are exceedingly good at finding patterns (to the point where we often find phantom ones). I was just expecting some basic checks like "does it make sense to store the difference instead of the absolute value for some of these bytes here". Seeing as the difference is 0 between every 60th byte in the submitted article, that should fix both our issues Bzip2 performed much better for me but it's also incredibly slow. If it were only the compressor, that might be fine for many applications, but also decompressing is an exercise in patience so I've moved to Zstandard at the standard thing to use

pajko 1y ago
Bzip2 performs exactly better because it rearranges the input to achieve better pattern matches: https://en.m.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.m.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_tran...
- vintermann 1y ago
  A number of identical copies of a string, but with random mutations propagating through it like a word ladder puzzle, is pretty close to best-case for BWT-based compressors. But Bzip2 is also a pretty bad BWT-based compressor. Not only does it use block sizes from a time when 8mb memory was a lot, it does silly things which doesn't help compression at all.

semiinfinitely 1y ago

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.

semiinfinitely 1y ago
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.html https://madhadron.com/science/farewell_to_bioinformatics.htm...
- jakobnissen 1y ago
  SAM is not a bad file format. What's bad about SAM?
  - optionalsquid 1y ago
    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
    - jakobnissen 1y ago
      True. I'd consider these minor flaws. W.r.t. the CIGAR, the spec says you do need to store it as a tag.

jefftk 1y ago

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 be able to use the repetition effectively.

AndrewOMartin 1y ago
The compression ratio will likely skyrocket if you sorted the list of bases.
- shellfishgene 1y ago
  You're joking, but a few bioinformatics tools use the Burrows-Wheeler transform to save memory, which is a bit like sorting the bases.
  - jefftk 1y ago
    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.
bede 1y ago
Thank you for clarifying this – yes the non-semantic nature of these particular line breaks is a key detail I omitted.
- tialaramex 1y ago
  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.

IshKebab 1y ago

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

hhh 1y ago
no, I power thru indefinitely with no recourse
bede 1y ago
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 https://github.com/ArcInstitute/binseq
amelius 1y ago
People rely on compression for that ;)
rurban 1y ago
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.
deleted 1y ago
[deleted]

FL33TW00D 1y ago

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

jefftk 1y ago
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.)
- fwip 1y ago
  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.
- FL33TW00D 1y ago
  https://www.biorxiv.org/content/10.1101/2025.04.08.647863v1.full.pdf https://www.biorxiv.org/content/10.1101/2025.04.08.647863v1....
  - optionalsquid 1y ago
    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

im3w1l 1y ago

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.

fwip 1y ago
The article links to the dataset here: https://ftp.ebi.ac.uk/pub/databases/ENA2018-bacteria-661k/ https://ftp.ebi.ac.uk/pub/databases/ENA2018-bacteria-661k/
- im3w1l 1y ago
  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.

nickdothutton 1y ago

How can we represent data or algos such that such optimisations before more obvious?

keketi 1y ago

When you know you're going to be compressing files of particular structure, it's often very beneficial to tweak compression algorithm parameters. In one case when dealing with CSV data, I was able to find a LZMA2 compression level, dictionary size and compression mode that yielded a massive speedup, uses 1/100th the memory and surprisingly even yields better compression ratios, probably from the smaller dictionary size. That's in comparison to the library's default settings.

ciupicri 1y ago
Could you please provide more details, perhaps give an example?

totalperspectiv 1y ago

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.

Gethsemane 1y ago
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 :)
- o11c 1y ago
  You can use content-defined chunking to wrap at a predictable place so that compression still works.
- sharedptr 1y ago
  Is BioPerl still standard, did people move to BioPython? When I was shown BioPerl I was tempted to write a better, C++ version, but was overwhelmed by other university stuff and let it go.
bede 1y ago
Thanks for reminding me to benchmark this!
- totalperspectiv 1y ago
  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!

lutusp 1y ago

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

diimdeep 1y ago

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?

iijj 1y ago
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.
vintermann 1y ago
What format is the 23andMe data in, by the way?
- diimdeep 1y ago
  tab delimited file (usually compressed for distribution), containing the fields rsid, chromosome, position, genotype (e.g. rs3094315 1 742429 AG).

dekhn 1y ago

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.

felixhandte 1y ago

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/zstd_ldm.c#L20 https://github.com/facebook/zstd/blob/v1.5.7/lib/compress/zs... (I am one of the maintainers of Zstd.)

nerpderp82 1y ago
That is fascinating. I wonder if you could layer a Levenshtein State Machine on the strings so you can apply n-edits to the text to get longer matches. I absolutely adore ZSTD, it has worked so well for me compressing json metadata for a knowledge engine.
- felixhandte 1y ago
  Zstd has a similar-ish capability called "repetition codes" [0]. The first stage of Zstd does LZ77 matching, which transforms the input into "sequences", a series of instructions each of which describes some literals and one match. The literals component of the instruction says "the next L bytes of the message are these L bytes". The match component says "the next M bytes of the input are the M bytes N bytes ago". If you want to construct a match between two strings that differ by one character, rather than saying "the next N bytes are the N bytes M bytes ago except for this one byte here which is X instead", Zstd just breaks it up into two sequences, the first part of the match, and then a single literal byte describing the changed byte, and then the rest of the match, which is described as being at offset 0. The encoding rules for Zstd define offset 0 to mean "the previously used match offset". This isn't as powerful as a Levenshtein edit, but it's a reasonable approximation. The big advantage of this approach is that it doesn't require much additional machinery on the encoder or decoder, and thus remains very fast. Whereas implementing a whole edit description state machine would (I think) slow down decompression and especially compression enormously. [0] https://datatracker.ietf.org/doc/html/rfc8878#name-repeat-offsets https://datatracker.ietf.org/doc/html/rfc8878#name-repeat-of...

meel-hd 1y ago

https://github.com/meel-hd/DNA https://github.com/meel-hd/DNA

pkilgore 1y ago

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?

cogman10 1y ago
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 https://en.wikipedia.org/wiki/Endogenous_retrovirus

a_bonobo 1y ago

There's some discussion here about DNA-specific compression algorithms. I thought I'd raise yesterday's HN discussion on 'The unreasonable effectiveness of modern sort algorithms' https://news.ycombinator.com/item?id=45208828 https://news.ycombinator.com/item?id=45208828 That blog post isn't about DNA per se, but it is about sorting data when you know there are only 4 numbers. I guess DNA has 5 - A,T,G,C,N the unknown base - but there's a huge space of DNA-specific compression research that outperforms ZSTD.