And yeah, Python is a strict requirement since the rest of our code is in Python - figured it wasn't worth throwing in another language when a rough parser worked.
Your trigram approach is roughly isomorphic to the FST approach. The main benefit of an FST is that it can store a huge number of keys in a very small amount of space that is still searchable without a separate decompression phase. In the case of trigrams with a low alphabet size, an FST probably isn't a big win. But say if you wanted to increase to a bigger N-gram for some reason, then perhaps an FST might help you out. It's true that Rust's fst library has a way to apply regexes to the FST for very fast search (Lucene also has this), but its subjects are terms in the FST, which in your case corresponds to trigrams. This means you still have to go through the "extract a set of trigrams from a regex to pre-filter on" dance.
And yeah, using the regex-syntax crate from Python would have been a fair amount of work. In particular, it still needs a C API before you can use it from Python, which would probably be a fair amount of grunt work.
In any case, as a computational biologist in a former life, this is very cool work. Nice job! :-)
Currently, only viral sequences are supported.