# An efficient way to find windows of size m with at least k identities

I have the problem to identify windows in a larger sequence occuring multiple times, with the restriction, that they dont need to be identical but "sufficiently similar".

So for example in a sequence of length $$l=8000$$ characters, identify all windows of size $$m = 20$$ that have at most 2 mismatches (or a smiliarity of $$k=18$$).

As D.W. pointed out, the alphabet size for my specific problem is 4.

There is obviously the naive approach to move a sliding window along the sequence, store all encountered windows, and then compare each window to each other window, but this leads to a binomial number of comparisons $$C$$ of windows, which quickly becomes limiting:

$$C_{naive} = \sum_{c=1}^{l-m}{c} = \binom{l - m+1}{2}$$

Is there a more efficient algorithm to solve this or a similar problem that I could look into?

• Please indicate what the alphabet size is. There are multiple algorithms, and the best algorithm is likely to be sensitive to the specific parameters. Do you want the best algorithm for those particular parameters? If you want the answer in general, I suspect this is expecting too much. I'm not sure this is a research-level question in theoretical CS.
– D.W.
Commented Jun 27 at 6:27
• @D.W. The alphabet size for my specific problem is 4. Could you name some of those algorithms you had in mind? :) Commented Jun 28 at 7:45