How to measure the topological quality of protein grammars?

Abstract : Motivation. Context-free (CF) and context-sensitive (CS) formal grammars are often regarded as more appropriate to model proteins than regular level models such as finite state automata and Hidden Markov Models (HMM). 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 (Dyrka, 2007; Dyrka et al., 2013). 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.
Type de document :
Communication dans un congrès
ICGI 2016 - 13th International Conference on Grammatical Inference, Oct 2016, Delft, Netherlands. 〈http://icgi2016.tudelft.nl/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01406331
Contributeur : François Coste <>
Soumis le : jeudi 1 décembre 2016 - 09:42:34
Dernière modification le : mercredi 16 mai 2018 - 11:23:35
Document(s) archivé(s) le : lundi 20 mars 2017 - 20:21:05

Fichier

icgi16_abs_rev.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01406331, version 1
  • ARXIV : 1611.10078

Collections

Citation

Witold Dyrka, François Coste, Olgierd Unold, Lukasz Culer, Agnieszka Kaczmarek. How to measure the topological quality of protein grammars?. ICGI 2016 - 13th International Conference on Grammatical Inference, Oct 2016, Delft, Netherlands. 〈http://icgi2016.tudelft.nl/〉. 〈hal-01406331〉

Partager

Métriques

Consultations de la notice

244

Téléchargements de fichiers

77