SEEK: Salford Environment for Expertise and Knowledge

Published Conference Proceedings - Paper
June 2005

Speeding up Parsing of Biological Context-Free Grammars

Fredouille, D & Bryant, C 2005, Speeding up Parsing of Biological Context-Free Grammars, in: Apostolico, A & Crochemore, M & Park, K (eds.), 'Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching', Springer-Verlag, Berlin, Germany, pp.241-256.


Grammars have been shown to be a very useful way to model biological sequences families. As both the quantity of biological sequences and the complexity of the biological grammars increase, generic and efficient methods for parsing are needed.  We consider two parsers for context-free grammars: depth-first top-down parser and chart parser; we analyse and compare them, both theoretically and empirically, with respect to biological data.  The theoretical comparison is based on a common feature of biological grammars: the gap - a gap is an element of the grammars designed to match any subsequence of the parsed string. The empirical comparison is based on grammars and sequences used by the bioinformatics community.  Our conclusions are that: (1) the chart parsing algorithm is significantly faster than the depth-first top-down a lgorithm, (2) designing special treatments in the algorithms for managing gaps is useful, and (3) the way the grammar encodes gaps has to be carefully chosen, when using parsers not optimised for managing gaps, to prevent important increases in running times.


Lecture Notes in Computer Science, No. 3537


SEEK Members

External Authors

D. Fredouille


Non-SEEK Editors

M. Crochemore

K. Park

A. Apostolico

Publication Details

Conference Proceedings
Fredouille, & Bryant, C eds. 2005, Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching, Springer-Verlag, Berlin, Germany, pp.241-256.