5 ms·
I don't know if there was any strict requirement to use Python, but you mention the difficulty in finding a library to parse regular expressions. One of the ma
by lambda 10y ago
I don't know if there was any strict requirement to use Python, but you mention the difficulty in finding a library to parse regular expressions.
One of the many great features of the Rust regex crate (https://doc.rust-lang.org/regex/regex/index.html https://doc.rust-lang.org/regex/regex/index.html) is that there's actually a regex_syntax crate that provides this parsing support (https://doc.rust-lang.org/regex/regex_syntax/index.html https://doc.rust-lang.org/regex/regex_syntax/index.html), which can be used for purposes like this, to do alternative kinds of matching engines.
Rust's regex library also has pretty good DFA and NFA matching engines, and an Aho-Corasick engine for parts of the regex that can be decomposed into just a set of simple strings to match, as well as some fairly well optimized exact substring search to speed up search for expressions with some substring that must match exactly, so it can be fairly fast for the kinds of matches like your "TAG(A|C|T|G)GG" example.
Another, even more radical change, would be to build a finite state transducer of your data set, which you can then do regex matching on directly by taking a union of an automaton representing the regex and the FST representing your data (which is itself an automaton). I learned about FSTs from the author of the Rust regex crate: http://blog.burntsushi.net/transducers/ http://blog.burntsushi.net/transducers/. An FST is actually used internally for certain types of searches in Elasticsearch/Lucene (https://www.elastic.co/guide/en/elasticsearch/reference/current/search-suggesters-completion.html https://www.elastic.co/guide/en/elasticsearch/reference/curr...). I don't know if these would be suited to this problem as is by just building an FST from your set of sequences, or maybe using the overlapping subsequences idea to make FSTs from a larger number of shorter strings, but it would be an interesting project to explore.
- joshma 10y agoInsanely cool, thanks for sharing - this would be interesting to replace our final filter (if I'm interpreting correctly, a trigram index would still speed up the initial search) 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.
- ersinesen 10y agoThis is such an FST based sequence search engine: http://78.189.139.203/demos/seqbul http://78.189.139.203/demos/seqbul Currently, only viral sequences are supported.
- burntsushi 10y ago> (if I'm interpreting correctly, a trigram index would still speed up the initial search) 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! :-)
- abecedarius 10y agoFor the union of the automata, do you mean intersection? Maybe when I look over the transducers post less quickly I'll see my mistake.
- lambda 10y agoYeah, I meant to write intersection. My mistake.