Paper Info
Title
An approximate matching algorithm for finding (sub-)optimal sequences in S-attributed grammars.
Abstract
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 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(')is an element of L(G) such that d(omega, omega('))less than or equal to 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.
Year
DOI
Venue
2002
10.1093/bioinformatics/18.suppl_2.S250
BIOINFORMATICS
Keywords
Field
DocType
S-Attribute Grammar,Approximate matching,Dynamic Algorithm
Stochastic context-free grammar,Rule-based machine translation,Optimal matching,Grammar-based code,Computer science,Theoretical computer science,Approximate matching
Conference
Volume
Issue
ISSN
18
SUPnan
1367-4803
Citations 
PageRank 
References 
9
0.69
8
Authors
3
Name
Order
Citations
PageRank
Jérôme Waldispühl111116.24
Behshad Behzadi2937.29
Jean-Marc Steyaert321149.38