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.