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)

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.

• 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. Apr 2, 2011 at 12:14
• Secret multiposting: math.stackexchange.com/questions/30454/… Apr 3, 2011 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.) Apr 3, 2011 at 17:13
• It was no secret, sorry. Apr 3, 2011 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$. Apr 4, 2011 at 1:06

1 Answer

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. Apr 3, 2011 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! Apr 3, 2011 at 6:47