Jérôme Waldispühl, Behshad Behzadi and Jean-Marc
Steyaert
An Approximate Matching Algorithm for Finding (Sub-)Optimal
Sequences in S-attributed Grammars
Motivation: S-attributed grammars (a generalization of
classical Context-Free grammars) provide a versatile formalism for
sequence analysis which allows to express long range constraints: the
RNA folding problem is a typical example of their
applications. Efficient algorithms have been developed to solve
problems expressed with these tools, which generally compute the
optimal attribute of the sequence w.r.t. the grammar. However, it is
often more meaningful and/or interesting from the biological point of
view to consider almost optimal attributes as well as approximate
sequences; we thus need more flexible and powerful algorithms able to
perform these generalized analyses.
Results: In this paper we present a basic algorithm which
computes the optimal attribute for all (approximate) strings W' in
L(G) such that d(W ,W') <= M, whose complexity is O(n^(r+1)) in
time and O(n^2) in space (r is the maximal length of the
right-hand side of any production of G). We will also give
some extensions and possible improvements of this algorithm.
Keywords: S-Attributed Grammar, Approximate matching, Dynamic
Algorithm.
Home