A Grammar-Based Unification of Several Alignment and Folding Algorithms

Fabrice Lefebvre

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.