a data structure for partial sequences

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)

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.

• I do not know the answer, but have you checked Algorithm on Strings, Trees, and Sequences: Computer Science and Computational Biology by Dan Gusfield? It is the definitive book to read for various kinds of algorithms and data structures related to string search. – Tsuyoshi Ito Apr 2 '11 at 12:14
• Secret multiposting: math.stackexchange.com/questions/30454/… – Tsuyoshi Ito Apr 3 '11 at 11:03
• There are only $2^{15} = 32768$ possible queries. You can simply pre-compute all answers and store them as an array; queries will be extremely fast and you won't use that much space, either. (And when you need to store a new element, you only need to update $2^8 = 256$ pre-computed answers – not too bad.) – Jukka Suomela Apr 3 '11 at 17:13
• It was no secret, sorry. – Tsuyoshi Ito Apr 3 '11 at 18:40
• @Jukka: the problem is that I am working with DNA sequences, which are not binary, and the number of total possible queries is $4^{15}$ for $L=15$. – mghandi Apr 4 '11 at 1:06

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).

• Thanks Sadeq for your answer. I hoped there exists a more efficient solution. – mghandi Apr 3 '11 at 6:17
• @Mahmoud: You're welcome. I think there are cleverer solutions that this naive one. Just keep an eye on this topic, and do more research. I hope that you find one! – M.S. Dousti Apr 3 '11 at 6:47