Speeding up parsing of biological context-free grammars

Fredouille, D; Bryant, CH

Abstract

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.

• Online Publication Date: Jun 22, 2005
• Publication Date: Jun 22, 2005
• Deposit Date: Feb 16, 2009
• Publicly Available Date: Feb 16, 2009
• Publisher: Springer
• Pages: 241-256
• Series Title: Lecture notes in computer science
• Series Number: 3537
• Book Title: Proceedings of the 16th Annual Symposium on Combinatorial pattern matching
• ISBN: 9783540262015
• DOI: https://doi.org/10.1007/11496656_21
• Publisher URL: http://dx.doi.org/10.1007/11496656_21
• Additional Information: Paper originally presented at the 16th Annual Symposium, CPM 2005, Jeju Island, Korea, June 19-22 2005