<p>A <strong>naive approach</strong> is as follows. This approach can be used when no better solution is available:</p>

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

<p>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 &lt;&lt; L, it is possible to prune the tree in such a way that it takes much less space.</p>

<p>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 <code>1</code> child, and takes the <code>0</code> and <code>.</code> children. This is continued until we find a match, a mismatch, or when the number of <code>.</code>'s along the path becomes greater than K (assuming the tree is not pruned already).</p>

<p>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 <code>data</code>, mark it as having no child.</p>

<p>Note that since $\binom{15}{7} = 6435$, in the extreme case, up to 6435 patterns in <code>data</code> 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).</p>

CC BY-SA 2.5
2011-04-03T06:17:31.100Z
Thanks Sadeq for your answer. I hoped there exists a more efficient solution.
mghandi
CC BY-SA 2.5
2011-04-03T06:47:24.743Z
@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!
Sadeq Dousti
CC BY-SA 2.5
2011-04-02T19:57:23.117Z
2011-04-02T19:57:23.117Z
Sadeq Dousti
<p>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? </p>

<p>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..}$</p>

<p>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) </p>

<p>This question was originally asked at math.stackexchange: <a href="https://math.stackexchange.com/questions/30454/a-data-structure-for-partial-sequences">link</a></p>

<p>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. </p>

CC BY-SA 2.5
2011-04-02T12:14:22.453Z
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
CC BY-SA 2.5
2011-04-03T11:03:08.603Z
Secret multiposting: http://math.stackexchange.com/questions/30454/a-data-structure-for-partial-sequences
Tsuyoshi Ito
CC BY-SA 2.5
2011-04-03T17:13:34.030Z
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
CC BY-SA 2.5
2011-04-03T18:40:46.117Z
It was no secret, sorry.
Tsuyoshi Ito
CC BY-SA 2.5
2011-04-04T01:06:30.567Z
@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
CC BY-SA 2.5
2011-04-04T15:05:04.203Z
@Jukka: the given L and K are examples. I was looking to see if there exists a famous data structure for such data, and I expressed the question in terms of bits (instead of nucleotides), for simplicity. Anyways, I think still your suggestion is useful, as we can pre-cumpute all answers for the 7 MSBs and 7 LSBs and use it to speedup Sadeq's proposed BT
mghandi
<co.combinatorics><ds.data-structures><bioinformatics>
a data structure for partial sequences
mghandi
# a data structure for partial sequences

(Asked by: username_0 on 2011-04-02)

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](https://math.stackexchange.com/questions/30454/a-data-structure-for-partial-sequences)

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.

**Tags:** co.combinatorics, ds.data-structures, bioinformatics

> **Comments:**
> **username_1**: 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.  
> **username_1**: Secret multiposting: http://math.stackexchange.com/questions/30454/a-data-structure-for-partial-sequences  
> **username_2**: 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.)  
> **username_1**: It was no secret, sorry.  
> **username_0**: @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$.  
> **username_0**: @Jukka: the given L and K are examples. I was looking to see if there exists a famous data structure for such data, and I expressed the question in terms of bits (instead of nucleotides), for simplicity. Anyways, I think still your suggestion is useful, as we can pre-cumpute all answers for the 7 MSBs and 7 LSBs and use it to speedup Sadeq's proposed BT  

---

## 1 answers

### Answer by username_3 on 2011-04-02. Score: 3 | Accepted 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).

> **Comments:**
> **username_0**: Thanks Sadeq for your answer. I hoped there exists a more efficient solution.  
> **username_3**: @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!  

---

