<p>There are many algorithms.  The best will depend on your specific workload and particular parameters.</p>
<p>For the specific parameters you listed there, one reasonable approach is to find all pairs of positions that have a 6-bit exact match, then check if they correspond to a 20-bit near-match with at most 2 mismatches.  The former can be done with a hashtable or by sorting.  If the string is random, we expect a little under 8000 6-bit exact matches, and then for each you can quickly check each to see whether it is a 20-bit near-match.</p>

CC BY-SA 4.0
2024-06-28T07:50:22.810Z
2024-06-28T07:50:22.810Z
D.W.
<p>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 &quot;sufficiently similar&quot;.</p>
<p>So for example in a sequence of length <span class="math-container">$l=8000$</span> characters, identify all windows of size <span class="math-container">$m = 20$</span> that have at most 2 mismatches (or a smiliarity of <span class="math-container">$k=18$</span>).</p>
<p>As D.W. pointed out, the alphabet size for my specific problem is 4.</p>
<p>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 <span class="math-container">$C$</span> of windows, which quickly becomes limiting:</p>
<p><span class="math-container">$$
C_{naive} = \sum_{c=1}^{l-m}{c} = \binom{l - m+1}{2}
$$</span></p>
<p>Is there a more efficient algorithm to solve this or a similar problem that I could look into?</p>

CC BY-SA 4.0
2024-06-27T06:27:43.703Z
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.
CC BY-SA 4.0
2024-06-28T07:45:56.663Z
@D.W. The alphabet size for my specific problem is 4. Could you name some of those algorithms you had in mind? :)
voiDnyx
<sliding-window>
An efficient way to find windows of size m with at least k identities
voiDnyx
# An efficient way to find windows of size m with at least k identities

(Asked by: username_0 on 2024-06-26)

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 username_1 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?

**Tags:** sliding-window

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 The alphabet size for my specific problem is 4. Could you name some of those algorithms you had in mind? :)  

---

## 1 answers

### Answer by username_1 on 2024-06-28. Score: -2

There are many algorithms. The best will depend on your specific workload and particular parameters.

For the specific parameters you listed there, one reasonable approach is to find all pairs of positions that have a 6-bit exact match, then check if they correspond to a 20-bit near-match with at most 2 mismatches. The former can be done with a hashtable or by sorting. If the string is random, we expect a little under 8000 6-bit exact matches, and then for each you can quickly check each to see whether it is a 20-bit near-match.


---

