Lets define:
$U=\left \{ u_j\right \} , 1 \leq j\leq N= b^{L},$ the set of all different sequences of length $L$ where each element of the sequence can be an integer in $\left \{ 0, 1, .., b-1 \right \}$.
$V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}b^{k},$ the set of all different gaped sequences with $k$ known elements and $L-k$ gaps.
$A_{M*N}=[a_{i,j}]$ is a binary matrix defined as following:
$a_{i,j} = \left\{\begin{matrix} 1 & \text{if } v_i \text{ matches } u_j \\ 0 & \text{otherwise } \end{matrix}\right.$
now, the questions are:
i) What is the rank of the matrix $S_{M*M}=AA^{T}$?
ii) What are the eigenvectors and eigenvalues of $AA^{T}$?
Here is an example for $L=2, k=1, b=2$:
$U = \left \{ 00,01,10,11\right \} $ $V = \left \{ 0.,1.,.0,.1\right \} ^*$
$ A = \begin{bmatrix} 1 & 1 & 0 &0 \\ 0 & 0 & 1 &1 \\ 1 & 0 & 1 &0 \\ 0 & 1 & 0 &1 \end{bmatrix}$
$ S = \begin{bmatrix} 2 & 0 & 1 &1 \\ 0 & 2 & 1 &1 \\ 1 & 1 & 2 &0 \\ 1 & 1 & 0 &2 \end{bmatrix}$
For the special case $k=1$, it has been previously solved by joriki and the solution can be found here. For the special case of binary sequences $(b=2)$, the rank is given here by joriki, and a solution for the eigen vectors is given here by Siva.
$^{*}$ here dots denote gaps. a gap can take any value, and each gaped sequence with $k$ known elements and $(L−K)$ gaps in $V$, exactly matches to $b^{L−k}$ sequences in U, hence the sum of elements in each row of $A$ is $b^{L−k}$.
EDIT:
my guess is that $\text{rank}(AA^T)=\text{rank}(A)=\sum_{m=0}^k\left({L\atop m}\right)(b-1)^m\;\;$. and it has $\left({L\atop m}\right)(b-1)^m$ eigenvalues of $\binom{L-m}{k-m}* b^{L-k}$, and the corresponding eigenvectors can be constructed in a similar way as Siva showed for b=2.
EDIT2:
using Gram-Schmidt process I obtained the following orthogonal set from Siva's proposed set of eigenvectors. but I wonder if there is a simpler solution too. $\Delta_{m}^{L,k}=\left[\begin{array}{c|c|cccc} & \mathrm{first\, bit\, Not\, picked} & & \mathrm{first\, bit\, picked}\\ & & a_{1}=1 & a_{1}=2 & \cdots & a_{1}=(b-1)\\ \hline 0\ldots & \Delta_{m}^{L-1,k-1} & \Delta_{m-1}^{L-1,k-1} & \frac{1}{2}\Delta_{m-1}^{L-1,k-1} & \cdots & \frac{1}{b-1}\Delta_{m-1}^{L-1,k-1}\\ \hline 1\ldots & \Delta_{m}^{L-1,k-1} & -\Delta_{m-1}^{L-1,k-1} & \frac{1}{2}\Delta_{m-1}^{L-1,k-1} & \cdots & \frac{1}{b-1}\Delta_{m-1}^{L-1,k-1}\\ 2\ldots & \Delta_{m}^{L-1,k-1} & 0 & -\Delta_{m-1}^{L-1,k-1} & \cdots & \frac{1}{b-1}\Delta_{m-1}^{L-1,k-1}\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ (b-1)\ldots & \Delta_{m}^{L-1,k-1} & 0 & 0 & \cdots & -\Delta_{m-1}^{L-1,k-1}\\ \hline g\ldots & \Delta_{m}^{L-1,k} & 0 & 0 & \cdots & 0\end{array}\right]$ $\Delta_{m}^{L,k}$ is the matrix containing orthogonal eigenvectors for L,k and m.