A Grammar-Based Unification of Several Alignment and Folding Algorithms

Proceedings Of The Fourth International Conference On Intelligent Systems For Molecular Biology

Volume

Proceedings Of The Fourth International Conference On Intelligent Systems For Molecular Biology

Contents

I 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 (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. I also show that MTSAG’s offer a new, efficient and useful way to handle stochastic context-free grammars and tools that generate them.