Discriminative Estimation using Probabilistic Context Free Grammars for Protein Characterization

Abstract

[EN] Bioinformatics is an active research area in which the objective is to develop intelligent systems for the analysis of molecular biology. Throughout the last decade, there has been a significant increase in the use of the formal language theory in the field of bioinformatics. Many methods based on formal language theory, statistical theory and learning theory have been developed for the analysis and characterization of sequences such as DNA, RNA and proteins. However, in the field of proteomics, the main problems resides in the size of the alphabet and the high complexity of the relations between amino acids. This parameters have deeply influenced the application of grammatical inference methods to the production of grammars in which the expressive power is not higher than stochastic regular grammars. Nevertheless, these stochastic regular grammars are unable to cover and detect any high-order dependencies such as nested and crossing relationships that are common in secondary and tertiary protein structures. For this reason, we propose a discriminative estimation model for the analysis and detection of protein binding sites that is capable of producing human readable descriptors for this sequences of interest.

[ES] La bioinformática es un campo de investigación activo cuyo objetivo principal es el desarrollo de sistemas inteligentes para el análisis en biología molecular. A lo largo de la última decada, se ha producido un incremento significativo en el uso de la teoría del lenguaje formal en este campo, dando lugar a diversos métodos para el análisis y caracterización de moleculas de ADN, ARN y proteínas. Aun así, en el campo de la proteómica, el tamaño del alfabeto y la complejidad de las relaciones entre amino ácidos han limitado la aplicación de métodos de inferecia gramatical a la producción de gramáticas que no tienen un poder expresivo mayor que una gramática estocástica regular. Sin embargo, estas gramáticas regulares son incapaces de cubrir y detectar las dependencias que aparecen en las estructuras secundarias y terciarias de las proteínas. Es por este motivo que proponemos un método de estimación discriminativo usando gramáticas incontextuales para el análisis y detección de lugares de unión en proteínas capaz de producir descripciones para las secuencias de interés.

[CA] La bioinformàtica és un camp de recerca actiu, l’objectiu principal de la qual és el desenvolupament de sistemes intel·ligents per a l’anàlisi en biologia molecular. Al llarg de l’última década s’ha produït un increment significatiu en l’ús de la teoría del llenguatge formal en aquest camp, donant lloc a diversos mètodes per a l’anàlisi i caracterització de molècules d’ADN, ARN i proteïnes. Encara així, en el camp de la proteòmica, la grandària de l’alfabet i la complexitat de les relacions entre aminoàcids han limitat l’aplicació de mètodes d’inferència gramatical a la producció de gramàtiques que no tenen un poder expressiu major que una gramática estocástica regular. No obstant això, aquestes gramàtiques regulars són incapaces de cobrir i detectar les dependències que apareixen en les estructures secundàries i terciàries de les proteïnes. És per aquest motiu que proposem un mètode d’estimació discriminatiu usant gramàtiques incontextuals per a l’anàlisi i detecció de llocs d’unió en proteïnes capaç de produir descripcions per a les seqüències d’interès.