Hm, unless I'm misunderstanding, the bottleneck here isn't running regex over all the sequences - it's in filtering out a large % of sequences before running a regex over the remaining ones. You're storing trigrams (3-byte keys) in an inverted index - compressing them won't get you much other than space savings. Re: caching, we're using Elasticsearch's bitmap caching to speed things up. If you search for something twice, the second time it'll take the cached bitmap from the first search and use that instead.

We use fast languages when we need them. Python is just parsing a regex to generate constraints - for DNA search, parsing a 1000-char regex is super fast and rarely an issue.

In this case, we're already at sub 100ms searches (usually sub 50ms) so I don't see much benefit from playing around with L1 caches and JIT-ing when higher-level structure already gives the perf characteristics we need.

You do need more than 2 bits. DNA can be modified (5-methyl-C is the most well known, but there are lots of other modifications known). You also have degeneracy where the exact base at a position is not known and these are represented in the data as additional letters [1]. To cover all these you need 4 bits and if you want to cover the modifications you need at least 5 bits.

1. https://en.m.wikipedia.org/wiki/Nucleic_acid_notation

I was assuming Python because big data analysts generally use one of two languages: Python and R.

ElasticSearch is a wrapper around Lucene, and Lucene does a tremendous amount of compression in its indices.