Algorithmic Complexity of Protein Identification

Mark Cieliebak¹, Thomas Erlebach², Zsuzsanna Lipták¹, Jens Stoye³, and Emo Welzl<sup>1

1</sup> Institute for Theoretical Computer Science, ETH Zürich
² Computer Engineering and Networks Laboratory (TIK), ETH Zürich
³ Max Planck Institute for Molecular Genetics, Berlin

We investigate a combinatorial problem that originates from computational biology: Given a string $\sigma$ of length n over a weighted alphabet, find a data structure and a query algorithm which, for a given weight M, decides whether $\sigma$ has a (contiguous) substring of weight M. Here, the weight of a string is the sum of the weights of its letters. There are two simple algorithms that solve the problem: one runs in time linear in n, the other has running time $O(\log n)$, but requires an additional data structure of size O(n²). We present an algorithm that uses preprocessing on $\sigma$ to construct a data structure of linear size that allows to perform queries in sublinear time, namely time $O(\frac{n}{\log n})$.