This is a test version of Biostars. For the public version, visit https://www.biostars.org.
Efficient implementation of Fuzzy set operations on sets of sequences?

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.

fuzzy mismatch
• 1,822 views • link
updated by Michael Dondrup Michael Dondrup • written by m.aljaff90 • m.aljaff90

1 answer

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.

• 1 views • link
written by Michael Dondrup Michael Dondrup

Log in to answer this question.

More posts like this