a data structure for partial sequences

Question

We have a set of bit sequences of length $L$ with only $K$ known bits and $L-K$ gaps. We want to store them in a data structure in a way that given a new bit sequence $x$ of length $L$, with $L$ known bits, we can efficiently search and retrieve the elements in the data structure that are sub-strings of $x$. What data structure and search method do you recommend?

for example, $L=5$, $K=3$, and data=${1.10., 11..0, 10..1, 01.1., 101..}$ given $x=10101$, following elements are returned: ${1.10., 10..1, 101..}$

In a more realistic example, we expect L=15, K=7, |data|=100,000, our priority is search time, however, the data structure (/index) size should be reasonable too (lets say smaller than 1GB)

This question was originally asked at math.stackexchange: link

EDIT: We are also interested in the more general case where data elements re nucleotide sequences (using alphabet {${A,C,G,T}$} instead of binary sequences). The main difference in that case is that number of all sequences of length L, will be $4^{L}$ instead of $2^{L}$ for binary.

Answer 1

A naive approach is as follows. This approach can be used when no better solution is available:

Keep a ternary search tree: Each node (except leaves) has three children: a 0, a 1, and a .. The height of tree is L. Each leaf stores 1 bit: whether the pattern denoted by the path from the root to that leaf exists in your sequence.

A full ternary search tree takes a space of $3^L$. Since L is rather small (L=15), the space will be $3^{15} \approx 14 \ MB$. Since |data|=100,000, and since K << L, it is possible to prune the tree in such a way that it takes much less space.

Now, a backtracking algorithm can search this data structure: Given input x, it starts at the root of the tree, and checks the MSB of x. This bit is either 0 or 1. Assume wlog that the bit is 0. Then, the algorithm omits the 1 child, and takes the 0 and . children. This is continued until we find a match, a mismatch, or when the number of .'s along the path becomes greater than K (assuming the tree is not pruned already).

The above algorithm may take a long time, unless you have pruned the tree properly. That is, if a node does not have a child in the data, mark it as having no child.

Note that since $\binom{15}{7} = 6435$, in the extreme case, up to 6435 patterns in data might match x (which is 6% of |data|; so even the best algorithm has to search this fraction of the database in the worst case).