Efficient implementation of Fuzzy set operations on sets of sequences?

Question

[m.aljaff90]

Hi! In need of some assistance.

Let A and B be two sets of sequences where all are, say 30bp long. So my problem is that not only do I want i) the intersection of A and B, i.e. all sequences which are both in A and also in B. Let's call the this set C. Additionally, I aslo require ii) FOR EACH found sequence S in C, I would also like all the sequences in (A OR B) which have a Levenshtein distance less than x from S.

Do you possible know of an efficient way to do this? Mind you that in my case, A and B are huge (>10 m). So far I've approached this problem by creating two tables in MYSQL (one for A and B) and doing some set operations there. However, the "fuzzy/mismatch" aspect of the problem makes it run very very very slow. I really would appreciate any directions.

Thanks in advance.

Answer 1

[Michael]

What about using agrep (bitap algorithm) for the fuzzy matching step?

If the search is eventually repeated, an indexing based method like suffix arrays might become an advantage, but I am not sure if they would be applicable to your case. You have many small text bits to search, while indexing is designed for a large text to be searched by a shorter pattern.