Let us define:
$U = \left\{ u_j \right\}, 1 \leq j \leq N = 2^{L}$, the set of all different binary sequences of length $L$.
$V = \left\{ v_i \right\}, 1 \leq i \leq M = \binom{L}{k}2^{k}$, the set of all different gapped binary sequences with $k$ known bits and $L-k$ gaps.
We have a score function $f : V \rightarrow R$, that associates a real number $c_i$ to any of $v_i$'s; i.e. $c_i = f(v_i)$.
Given any pair of $u_j$ and $v_i$, we can count the number of mismatches, by counting the known bits of $v_i$ that are different in $u_j$. For example given $L=7, k=4$:
$\text{diff}(\text{"0001100"}, \text{"01...01"}) = 2$,
because the second bit and the last bit are different (gaps can match to any value).
We have a weight associated to the number of mismatches. In general, the number of mismatches can be any number between $0$ and $k$. so we have $k+1$ such weights given by $\left \{ w[0],w[1],\ldots,w[k] \right \}$.
For a given sequence $S$ of $T$ bits, $S = s_0s_1 \ldots s_{T-1}$, we define the total score as the weighted sum of all the $c_i$'s for all the the contiguous $L$-bits subsequences of $S$ weighted by their distance:
$g(S)=\sum_{j=0}^{T-L}\sum_{i=1}^{M} c_i \times w[\text{diff}(v_i, s_js_{j+1} \ldots s_{j+L-1})]$.
the obvious algorithm is as follows:
g:=0; for j:=0 to T-L for i:=0 to M g:=g+c[i]*calcDif(S,j,i)
where calcDif() takes $O(L)$ to count number of mismatches. so the overall time would be in the order of $T*M*L$.
What is a better approach to calculate the total score more efficiently? Typical values are: $L=20, k=10, T=2000$?