Finding Patterns in Intervals

Sequences of genes and proteins are usually stored in a full-text index (such as suffix trees) that allow fast searches for patterns. Often, due to preliminary knowledge of the location of a gene or protein, the search can be limited to a specified interval in the sequence. Recent advances have shown how to answer these kind of "position restricted matching queries" by using an additional data structure called "range next value query" (RNV).

The first task of this thesis is to implement one such variant. When this is done, you will have a good basis for tuning your algorithm at various points. You can try around with different parameters and data structures to get a fast and space conscious data structure.

Good knowledge of Java or C/C++ and an interest in algorithmic engineering is required.

This thesis will be supervised by the Huson lab (Uni Tuebingen). Please contact Johannes Fischer for further information.