Optimizations in the case of a known, limited alphabet of characters?

[KGerhardt]

Hello,

I've been applying vectorscan to a series of genomics tools which had previously utilized regex searches implemented with the default engines of several languages. I was curious if it was possible to even further increase performance of vectorscan if an alphabet of the characters that will be seen in a string can be specified ahead of time. In genomic contexts, the possible character alphabet will typically be only 4 characters + an unknown sequence character for DNA and RNA and 20 + 1 for protein sequences, and we anticipate all strings to be searched will only include these characters.

Can additional performance gains be obtained if the search alphabet is more limited? If so, is this behavior reasonable to support, or is it outside the scope of vectorscan's development? Is the additional benefit of having only a limited set of characters already implicit in the creation of a search graph for patterns only containing these characters?

Any additional understanding and support you can give me is appreciated,

Kenji

[markos]

Hi @KGerhardt, yes I also have the impression that such a limitation will have a possible impact on performance, however it's hard to tell you exactly without knowing more details, eg. typical size of string searched and pattern checked, which algorithm is used, etc. Depending on the usecase, it might actually make sense to develop a specialized of one or two algorithms for use in genomics. Whether that makes sense to include in Vectorscan or have standalone, depends on the complexity and generality of this algorithm.

[KGerhardt]

I anticipate that the substantially more common use case for this kind of search will be DNA searches. In these cases, it's likely that patterns will be relatively short - in my use, between abut 5 and 50 characters - and fairly numerous, perhaps 1000 to a few thousand. Strings to be searched will typically be fairly large, as they're likely to be the genome sequences for single chromosomes in eukaryotes. Mostly, this will be between ~10 million to low 100s of millions of characters per string.