Fabrice Lefebvre

A Grammar-Based Unification of Several Alignment and Folding Algorithms

We show in this paper taht many popular models of folding and/or alignments may be described by a new formalism: multi-tape S-attribute grammars (MTSAG's). This formalism relieves the designer of biological models of implementation details which may hinder his inventiveness. To complete this formalism, we designed and implemented a tool which, given a MTSAG, will output an efficient parser for this grammar. We also show that MTSAG's offer a new, efficient and useful way to handle stochastic context-free grammars and tools that generate them.