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='1010101' \\ S2='1011000' \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 & 10110 & (2) \\ 10101 & 01100 & (3) \\ 10101 & 11000 & (3) \\ 01010 & 10110 & (3) \\ 01010 & 01100 & (2) \\ 01010 & 11000 & (2) \\ 10101 & 10110 & (2) \\ 10101 & 01100 & (3) \\ 10101 & 11000 & (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 ?