101–110 of 118 posts
I thought I'd raise yesterday's HN discussion on 'The unreasonable effectiveness of modern sort algorithms' 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.
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…
[1] See 'release.v16' in the fasta2 release at https://fasta.bioch.virginia.edu/wrpearson/fasta/fasta_versi...
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 :)
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.
Earlier quoted context omitted.
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.
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…
Earlier quoted context omitted.
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.
> Ultimately, Zstd is a byte-oriented compressor that doesn't understand the semantics of the data it compresses
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 expect…
Bzip2 performs exactly better because it rearranges the input to achieve better pattern matches: https://en.m.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_tran...
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.
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?
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 si…
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…
Earlier quoted context omitted.
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.