title: Improved algorithms for parsing ESLTAGs: a grammatical model suitable for RNA pseudoknots.
abstract: Formal grammars have been employed in biology to solve various important problems. In particular, grammars have been used to model and predict RNA structures. Two such grammars are Simple Linear Tree Adjoining Grammars (SLTAGs) and Extended SLTAGs (ESLTAGs). Performances of techniques that employ grammatical formalisms critically depend on the efficiency of the underlying parsing algorithms. In this paper, we present efficient algorithms for parsing SLTAGs and ESLTAGs. Our algorithm for SLTAGs parsing takes O(min{m,n⁴}) time and O(min{m,n⁴}) space, where m is the number of entries that will ever be made in the matrix M (that is normally used by TAG parsing algorithms). Our algorithm for ESLTAGs parsing takes O(min{m,n⁴}) time and O(min{m,n⁴}) space. We show that these algorithms perform better, in practice, than the algorithms of Uemura et al.
authors.affiliation: Computer Science and Engineering Department, University of Connecticut, 371 Fairfield Rd., Unit 2155, Storrs, CT 06269-2155, USA. rajasek@engr.uconn.edu
authors.forename: Sanguthevar
authors.initials: S
authors.lastname: Rajasekaran
authors.forename: Sahar
authors.initials: S
authors.lastname: Al Seesi
authors.forename: Reda A
authors.initials: RA
authors.lastname: Ammar
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D008958:Models, Molecular; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D012984:Software
chemical_list: D012313:RNA