  Context-free and context-sensitive formal grammars are often regarded as more
appropriate to model proteins than regular level models such as finite state
automata and Hidden Markov Models. In theory, the claim is well founded in the
fact that many biologically relevant interactions between residues of protein
sequences have a character of nested or crossed dependencies. In practice,
there is hardly any evidence that grammars of higher expressiveness have an
edge over old good HMMs in typical applications including recognition and
classification of protein sequences. This is in contrast to RNA modeling, where
CFG power some of the most successful tools. There have been proposed several
explanations of this phenomenon. On the biology side, one difficulty is that
interactions in proteins are often less specific and more "collective" in
comparison to RNA. On the modeling side, a difficulty is the larger alphabet
which combined with high complexity of CF and CS grammars imposes considerable
trade-offs consisting on information reduction or learning sub-optimal
solutions. Indeed, some studies hinted that CF level of expressiveness brought
an added value in protein modeling when CF and regular grammars where
implemented in the same framework. However, there have been no systematic study
of explanatory power provided by various grammatical models. The first step to
this goal is define objective criteria of such evaluation. Intuitively, a
decent explanatory grammar should generate topology, or the parse tree,
consistent with topology of the protein, or its secondary and/or tertiary
structure. In this piece of research we build on this intuition and propose a
set of measures to compare topology of the parse tree of a grammar with
topology of the protein structure.
