an efficient algorithm for mismatch profile We have M=10000 binary sequences of length N=1000.

given length L=15, for each pair of sequences, $S_1$ and $S_2$, we define the mismatch profile, mp($S_1$,$S_2$,$L$)[$m$], for m=0,1,...,L as following: 

mp($S_1$,$S_2$,$L$)[$m$] = number of all substrings of length $L$ in $S_1$ and $S_2$ that exactly differ in m positions. 

for example:

$\begin{array}{ccc}
L=5    \\
N=7    \\
S1=&#39;1010101&#39; \\
S2=&#39;1011000&#39; 
 
\end{array}$

set of all L-mers in $S_1$ is { 10101, 01010, 10101} and 
set of all L-mers in $S_2$ is { 10110, 01100, 11000}

All the pairs of L-mers (one from S1 and the other from S2) are (with the number of mismatches for each pair in the parenthesis): 

$\begin{array}{ccc}
10101 &amp; 10110 &amp; (2) \\
10101 &amp; 01100 &amp; (3) \\
10101 &amp; 11000 &amp; (3) \\

01010 &amp; 10110 &amp; (3) \\
01010 &amp; 01100 &amp; (2) \\
01010 &amp; 11000 &amp; (2) \\

10101 &amp; 10110 &amp; (2) \\
10101 &amp; 01100 &amp; (3) \\
10101 &amp; 11000 &amp; (3) 
\end{array}$

hence the mismatch profile for $S_1$ and $S_2$ for this example is: 
mp($S_1$,$S_2$,$L$)[0]= 0
mp($S_1$,$S_2$,$L$)[1]= 0
mp($S_1$,$S_2$,$L$)[2]= 4
mp($S_1$,$S_2$,$L$)[3]= 5
mp($S_1$,$S_2$,$L$)[4]= 0
mp($S_1$,$S_2$,$L$)[5]= 0

what is a fast algorithm to calculate the mismatch profile for every pair of sequences. The trivial algorithm would be $O(N^2 M^2)$ . can we make this better ?
Upd: Space complexity improved to just $O(2^LML)$ which makes the solution much more practical.

The problem can be solved at least in $O(M^2NL + 2^L MNL)$ time and $O(2^L ML)$ additional memory as follows.

Let's denote by $S^j$ the prefix $s_1 s_2 \ldots s_j$ of $S$. First, for each binary string $s$ of length $L$ precompute mismatch profile $mp&#39;(s, i, j, k) = mp(s, S_i^j, k)$ of that string with all prefixes of length $j$ of all strings $S_1, S_2, \ldots, S_M$. That will require $O(2^L MNL)$ memory to store and can be done in $O(2^L MNL)$ in straightforward way.

Then iteratively build mismatch profiles $mp_j(i,i&#39;,k)$ for each pair of $j$-prefixes of $S_1, S_2, \ldots, S_M$ for $j=L,L+1,\ldots,N$, so $mp_N(i,i&#39;,k)$ will be your desired answer. Let's denote by $end(S)$ the suffix of $S$ of the length $L$ (i.e. $S[(length(S)-L+1) \ldots length(S)]$). Notice that $$
\begin{align*}
mp_j(i,i&#39;,k) = &amp;mp(S_i^{j-1},S_{i&#39;}^{j-1},k) + mp(end(S_i^j), S_{i&#39;}^{j-1}, k) + \\&amp;mp(S_i^{j-1}, end(S_{i&#39;}^j),  k) + mp(end(S_i^j), end(S_{i&#39;}^j),k)
\end{align*}
$$ which is indeed
$$
\begin{align*}
&amp;mp_{j-1}(i,i&#39;,k) + mp&#39;(end(S_i^j), i&#39;, j-1, k) + \\ &amp;mp&#39;(end(S_{i&#39;}^j), i, j-1, k) + mp(end(S_i^j), end(S_{i&#39;}^j),k)
\end{align*}

$$ 

The first 3 terms of that sum are already computed and the last one can be computed in amortized $O(1)$ time (it is $O(L)$ but you need to compute it only once for all values of $k$ with fixed $j,i,i'$). Thus you can compute $mp_j$ using $mp_{j-1}$ and $mp&#39;$ in $O(M^2L)$ time, which leads to $O(M^2NL)$ term in the total complexity.

Notice that you need values of $mp&#39;$ only for a fixed prefix length on each iteration. Thus you can compute $mp&#39;$ not all of a piece at the beginning but rather iteratively for $j=L,L+1, \ldots, N$ in between of $mp_j$ computations. That can be easily done in $O(2^LML)$ time per iteration (so total complexity does not change) but requires only $O(2^LML)$ additional memory.

The main issue of this solution is exponential in $L$ time.

P.S. If $L$ is too small ($2^L &lt; N$) then the naive method can be improved to $O(M^2 4^L)$ time by calculating the number of occurrences of each string $s$ of length $L$ in $S_i$. This allows you to process all different substrings of $S$ of length $L$ in $O(2^L)$ time instead of $O(N)$ (you will need to precompute pairwise differences between all such substrings first).