Re: [Seqan-dev] Approximate Searching in set of strings

["Holtgrewe, Manuel" <manuel.holtgrewe@fu-berlin.de>]

Hi Tilo,

as far as I know, there is no way to do non-heuristic approximate string searching using indices, i.e. something like O(1) lookups. What exactly are you looking for and trying to solve?


SeqAn has implementations of various online algorithms for approximate string searching, e.g. see [1]. Notably, Myer's Bitvector algorithm is very fast for searching single strings with a length up to the machine word width in large strings. Going beyond this limit makes things a bit slower since bits have to migrate over machine words.

Pex, AbndmAlgo and DPSearch also allow for edit distance, DPSearch even allows linear gap and arbitrary substitution scores.


If you are looking for read mapping, i.e. many short reads to be found with Hamming/edit distance in long strings, have a look at RazerS, our read mapping tool. It uses the SWIFT algorithm to first find regions that overlap with epsilon-matches and then uses Myer's Bitvector algorithm or a naive Hamming search to look for the exact positions.


Another possible approach is building a q-gram index of your long string (haystack) and then searching for the q-grams of your short string (needle) in the haystack. You can look at the LAGAN demo to see an application of q-gram indices and seeds in SeqAn. FASTA, BLAST, bowtie and bwa are codes that do kinds of "approximate string searching" and could be implemented with the infrastructure of the SeqAn library.


People around here use Visual Studio, Emacs, XCode and occasionally vim. I have never seen Visual Studio really make sense out of SeqAn style C++, XCode seems to infer symbol names that make sense (which Visual Studio should be able, too). I have not tried to get syntax completion running in either Emacs or XCode.

HTH,
Manuel

[1] http://www.seqan.de/dddoc/html_devel/CLASS_Pattern.html