You're also forgetting that most of the popular formats just store the bases as 1-byte per base "GATC"= 4 bytes, when 2 bits per base would be fine if your data

You're also forgetting that most of the popular formats just store the bases as 1-byte per base "GATC"= 4 bytes, when 2 bits per base would be fine if your data only has the 4 unambiguous bases. You could fairly trivially drop the storage of most of these formats by just encoding as 2 bits per base. Another weird thing is that not all possible k-mers appear in DNA and k-mers of most lengths will repeat somewhere at least once. It would probably be best to just pick some useful k-mer length and build a lookup table and just store the byte-encoded indexes that map to the kmers then just gzip that whole mess. You might be able to save more space if it turns out that the indexes turn out to be reusable across genomes and just leave them out of the file. It may also depend on your application, if all you want to know is "does k-mer==GATTACA" exist in my genome, you can just dump all the kmers into some persistent bloom filter and do searches and lookups really fast. Those would be quite small compared.