3 ms·
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
by vintermann 1y ago
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.
- bede 1y agoExactly. The line breaks break the runs of otherwise identical bits in identical sequences. Unless two identical subsequences are exactly in phase with respect to their line breaks, the hashes used for long range matching are different for otherwise identical subsequences.
- amelius 1y agoAnd the compressor does not think: "how can I make these two sequences align better without wasting a lot of space?"
- tiagod 1y agoThe compressor doesn't think about anything. Also, Zstd doesn't have the goal of reaching the highest possible compression ratio. It's more geared toward lowest overhead, high bandwidth compress/decompress.
- ebolyen 1y agoNo, because alignment, in the general case, is O(n^2). It is ironically one of the more tractable and well solved problems in bioinformatics.