Related Experiment Videos
A grammar-based unification of several alignment and folding algorithms
1Ecole Polytechnique, Palaiseau, France. lefebvre@lix.polytechnique.fr
Proceedings. International Conference on Intelligent Systems for Molecular Biology
|January 1, 1996
Summary
This paper introduces multi-tape S-attribute grammars (MT-SAGs) for modeling biological structures, simplifying design and enabling efficient parser generation. MT-SAGs also provide a novel approach for handling stochastic context-free grammars.
Area of Science:
- Computational Biology
- Formal Language Theory
- Bioinformatics
Background:
- Existing models for biological folding and alignment can be complex.
- Implementation details often limit the creativity of biological model designers.
Purpose of the Study:
- To introduce a new formalism, multi-tape S-attribute grammars (MT-SAGs), for describing biological models.
- To develop a tool for generating efficient parsers from MT-SAGs.
- To demonstrate the utility of MT-SAGs for handling stochastic context-free grammars.
Main Methods:
- Development of the multi-tape S-attribute grammar (MT-SAG) formalism.
- Implementation of a parser generation tool for MT-SAGs.
- Application of MT-SAGs to stochastic context-free grammars.
Main Results:
- MT-SAGs provide a unified formalism for various folding and alignment models.
- The developed tool efficiently generates parsers for MT-SAGs.
- MT-SAGs offer an effective method for managing stochastic context-free grammars.
Conclusions:
- MT-SAGs simplify the design of biological models by abstracting implementation details.
- The parser generation tool enhances the practical application of MT-SAGs.
- MT-SAGs present a valuable advancement for computational biology and formal language applications.