Algorithmic complexity of protein identi$cation: combinatorics of weighted strings
Mark Cieliebak, Thomas Erlebach, Jens Stoye, Emo Welzl · 2004
We investigate a problem which arises in computational biology: Given a constant-size alpha- bet A with a weight function � :A → N, $nd an e:cient data structure and query algorithm solving the following problem: For a stringover A and a weight M ∈ N, decide whether � contains a substring with weight M , where the weight of a string is the sum of the weights of its letters (ONE-STRING MASS FINDING PROBLEM). If the answer is yes, then we may in addition require a witness, i.e., indices i 6 j such that the substring beginning at position i and ending at position j has weight M. We allow preprocessing of the string and measure e:ciency in two parameters: storage space required for the preprocessed data and running time of the query al- gorithm for given M. We are interested in data structures and algorithms requiring subquadratic storage space and sublinear query time, where we measure the input size as the length n of the input string � . Among others, we present two non-trivial e:cient algorithms: L OOKUP solves the problem with O(n) storage space and O(n=log n) time; INTERVAL solves the problem for binary alphabets with O(n) storage space in O(log n) query time. We introduce other variants of the problem and sketch how our algorithms may be extended for these variants. Finally, we discuss combinatorial properties of weighted strings. ? 2003 Elsevier B.V. All rights reserved.