title: An approximate matching algorithm for finding (sub-)optimal sequences in S-attributed grammars.
abstract: BACKGROUND
  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 application. 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, given a grammar G and a sequence omega, computes the optimal attribute for all (approximate) strings omega(') in L(G) such that d(omega, omega(')) < or = M, and 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.
authors.affiliation: Ecole Polytechnique, Palaiseau, France. waldispu@lix.polytechnique.fr
authors.forename: J
authors.initials: J
authors.lastname: Waldispühl
authors.forename: B
authors.initials: B
authors.lastname: Behzadi
authors.forename: J-M
authors.initials: JM
authors.lastname: Steyaert
mesh_terms: D000465:Algorithms; D009323:Natural Language Processing; D010363:Pattern Recognition, Automated / Q000379:methods*; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid