Entropie de Shannon

9.1 Introduction

Chomsky a initialement formalisé des grammaires sans contexte (CFG) comme tentative de modéliser des langages. Depuis lors, ils ont été largement utilisés dans une variété d’applications informatiques. Les CFG ont un caractère récursif et sont composés d’ensembles de règles pouvant entraîner des chaînes d’alphabets, également appelées mots. L’ensemble des mots générés par une grammaire est appelé la langue de cette grammaire. Une grammaire est dite sans ambiguïté s’il existe une correspondance un à un entre les mots et leurs dérivations descriptives. Les CFG stochastiques (SCFG) attribuent des probabilités à chaque règle, qui à son tour attribue une valeur de vraisemblance à chaque mot en multipliant les probabilités des règles utilisées pour dériver ce mot. Grenander, Kuich, Hutchins, Soule et d’autres ont étudié des propriétés importantes des CFG et des SCFG, telles que la convergence de la longueur moyenne des dérivations, la capacité ou l’entropie de Shannon (entropie de Shannon) telle que définie dans, en utilisant des techniques de fonctions génératrices. Le schéma de structure secondaire de l’ARN a également un caractère sans contexte, ce qui lui permet d’être décrit par de telles grammaires. La structure secondaire de l’ARN a été décrite pour la première fois formellement par Smith et Waterman. Les caractéristiques combinatoires des structures secondaires de l’ARN ont ensuite été explorées par Stein et Waterman, puis étudiées par Viennot et Vauchaussade de Chaumont, Hofacker et al. , Nebel, Liao et Wang, Doslic et al. et d’autres utilisant des fonctions génératrices et des fonctions génératrices de probabilités.

Les GSC ont eu un grand impact sur les études de structure secondaire de l’ARN. La modélisation de la structure secondaire de l’ARN nous aide à faire des prédictions sur la structure de l’ARN et sa fonction biologique ultérieure, car les fonctions de nombreux ARN tels que diverses classes d’ARN non codants pour les protéines (arNNC) sont liées à leurs structures. Typiquement, la prédiction de la structure secondaire de l’ARN se fait par minimisation de l’énergie de pliage de la séquence selon un modèle de pliage thermodynamique tel que l’ensemble de Boltzmann. Les SCFG, d’autre part, sont des modèles de covariance qui peuvent imiter le repliement de l’ARN avec plus de flexibilité. Dans le cas d’un modèle de repliement basé sur SCFG, des valeurs de vraisemblance sont attribuées à tous les scénarios de repliement possibles d’une séquence d’ARN. Ensuite, la structure ayant une valeur de maximum de vraisemblance (ML) est prédite comme structure secondaire de la séquence d’ARN. La prédiction ML des modèles basés sur SCFG peut être effectuée par l’algorithme Cocke-Younger-Kasami (CYK). Similaire à la minimisation de l’énergie, l’algorithme CYK est implémenté par programmation dynamique. L’objectif de la conception du modèle est d’obtenir des estimations de ML aussi similaires que possible aux structures secondaires d’ARN connues, ce qui rend l’attribution des probabilités aux règles une tâche critique et difficile. Rivas offre un aperçu plus approfondi de divers aspects de la modélisation de la structure secondaire de l’ARN.

Les approches d’apprentissage du modèle de maximisation des attentes actuelles (EM) consistent généralement en deux étapes : Premièrement, l’algorithme CYK est utilisé pour la prédiction de la structure de chaque séquence d’ARN de l’ensemble d’apprentissage (étape de maximisation). Deuxièmement, les probabilités de règle du SCFG sont réestimées en fonction des comptages ou des fréquences de leurs occurrences dans les prédictions (étape d’estimation). Ces estimations peuvent être calculées soit en utilisant l’approche antérieure de Laplace expliquée dans Durbin et al. ou en déployant des approches similaires basées sur les fréquences. La procédure d’EM itérative peut se poursuivre jusqu’à ce que les probabilités de règles résultantes donnent la précision souhaitée. Les techniques d’apprentissage du modèle peuvent varier, soit dans la définition du critère de ML (conjoint par rapport au conditionnel), soit dans les techniques d’estimation de la règle-probabilité. Un modèle de pliage d’ARN basé sur SCFG peut soit consister en un SCFG léger avec seulement quelques règles de grammaire, soit il peut s’agir d’une grammaire lourde composée de nombreuses règles telles que des super-grammaires décrites dans Rivas et al. .

Dans ce travail, l’entropie de Shannon du SCFG, désignée ici comme entropie de l’espace grammatical (GS), est calculée analytiquement et introduite comme caractéristique grammaticale critique dans la modélisation de la structure secondaire de l’ARN. Les formulations présentées sont cohérentes avec la forme générale de l’entropie grammaticale connue sous le nom d’entropie dérivationnelle, et peuvent être trouvées dans Grenander et Soule. Dans la section 9.2, une formulation est présentée pour calculer l’entropie de Shannon de l’espace probabiliste infiniment grand de grammaires structurellement non ambiguës de modélisation de l’ARN1 qui est compatible avec les formulations d’entropie dérivationnelle présentées dans Grenander. Les valeurs d’entropie GS de plusieurs modèles de repliement d’ARN bien établis sont ensuite calculées sous différents ensembles de paramètres dans la section 9.3. Dans la section 9.4, un critère d’apprentissage du modèle de structure secondaire d’ARN basé sur SCFG est proposé sur la base de l’entropie GS. Enfin, la section 9.5 comprend une discussion et des conclusions.