A grammar-based unification of several alignment and folding algorithms.
We show in this paper that many popular models of folding and/or alignment may be described by a new formalism: multi-tape S-attribute grammars (MT-SAG'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.
Lefebvre
F
F
Ecole Polytechnique, Palaiseau, France. lefebvre@lix.polytechnique.fr
D000465:Algorithms; D001483:Base Sequence; D008954:Models, Biological; D008957:Models, Genetic; D008969:Molecular Sequence Data; D016415:Sequence Alignment