---
res:
bibo_abstract:
- 'We investigate a problem which arises in computational biology: Given a constant-size
alphabet [Mathematical script A] with a weight function µ : [Mathematical script
A] --> [Double-struck N], find an efficient data structure and query algorithm
solving the following problem: For a string [sigma] over [Mathematical script
A] and a weight [Mathematical italic M] [element of] [Double-struck N], decide
whether [sigma] contains a substring with weight [Mathematical italic 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 [less-than or equal to] j such that the substring beginning at
position i and ending at position j has weight [Mathematical italic M]. We allow
preprocessing of the string and measure efficiency in two parameters: storage
space required for the preprocessed data and running time of the query algorithm
for given [Mathematical italic 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 [sigma]. Among others, we present
two non-trivial efficient algorithms: Lookup 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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Mark
foaf_name: Cieliebak, Mark
foaf_surname: Cieliebak
- foaf_Person:
foaf_givenName: Thomas
foaf_name: Erlebach, Thomas
foaf_surname: Erlebach
- foaf_Person:
foaf_givenName: Zsuzsanna
foaf_name: Lipták, Zsuzsanna
foaf_surname: Lipták
- foaf_Person:
foaf_givenName: Jens
foaf_name: Stoye, Jens
foaf_surname: Stoye
foaf_workInfoHomepage: http://www.librecat.org/personId=65864
orcid: 0000-0002-4656-7155
orcid_put_code_url: https://api.orcid.org/v2.0/0000-0002-4656-7155/work/35435006
- foaf_Person:
foaf_givenName: Emo
foaf_name: Welzl, Emo
foaf_surname: Welzl
bibo_doi: 10.1016/S0166-218X(03)00187-2
bibo_issue: '1'
bibo_volume: 137
dct_date: 2004^xs_gYear
dct_identifier:
- UT:000188188900003
dct_isPartOf:
- http://id.crossref.org/issn/0166-218X
dct_language: eng
dct_subject:
- Computational biology
- Weighted strings
- Protein identification
dct_title: 'Algorithmic complexity of protein identification: combinatorics of weighted
strings@'
...