Entropía de Shannon
9.1 Introducción
Chomsky inicialmente formalizó gramáticas libres de contexto (CFGs) como un intento de modelar lenguajes. Desde entonces, se han utilizado ampliamente en una variedad de aplicaciones de ciencias de la computación. Los CFG tienen una naturaleza recursiva y se componen de conjuntos de reglas que pueden conducir cadenas de alfabetos, también conocidas como palabras. El conjunto de palabras generadas por una gramática se conoce como el lenguaje de esa gramática. Se dice que una gramática es inequívoca si hay una correspondencia uno a uno entre las palabras y sus derivaciones descriptivas. Los CFG estocásticos (SCFG) asignan probabilidades a cada regla, que a su vez asigna un valor de probabilidad a cada palabra multiplicando las probabilidades de las reglas utilizadas para derivar esa palabra . Grenander, Kuich, Hutchins, Soule y otros han investigado propiedades importantes de CFGs y SCFGs, como la convergencia de la longitud media de las derivaciones, la capacidad o la entropía de Shannon (entropía de Shannon) como se define en , utilizando técnicas de funciones generadoras. El esquemático de estructura secundaria del ARN también tiene una naturaleza libre de contexto, lo que le permite ser descrito por tales gramáticas. La estructura secundaria del ARN fue descrita formalmente por primera vez por Smith y Waterman . Las características combinatorias de las estructuras secundarias de ARN fueron exploradas por Stein y Waterman y posteriormente estudiadas por Viennot y Vauchaussade de Chaumont, Hofacker et al. , Nebel, Liao and Wang, Doslic et al. y otros que utilizan funciones generadoras y funciones generadoras de probabilidad.
Los SCFG han tenido un gran impacto en los estudios de estructura secundaria de ARN . El modelado de estructuras secundarias de ARN nos ayuda a hacer predicciones sobre la estructura del ARN y su función biológica posterior, ya que las funciones de muchos ARN, como varias clases de ARN no codificadores de proteínas (ncRNA), están relacionadas con sus estructuras. Típicamente, la predicción de la estructura secundaria de ARN se realiza minimizando la energía de plegado de la secuencia bajo un modelo de plegado termodinámico como el conjunto de Boltzmann . Los SCFG, por otro lado, son modelos de covarianza que pueden imitar el plegamiento del ARN con más flexibilidad. En el caso de un modelo de plegado basado en SCFG, los valores de probabilidad se asignan a todos los escenarios de plegado posibles de una secuencia de ARN. Luego, la estructura con valor de máxima verosimilitud (ML) se predice como la estructura secundaria de la secuencia de ARN. La predicción de ML de modelos basados en SCFG se puede hacer mediante el algoritmo Cocke-Younger-Kasami (CYK). Similar a la minimización de energía, el algoritmo CYK se implementa a través de programación dinámica. El objetivo del diseño del modelo es obtener estimaciones de ML que sean lo más similares posibles a las estructuras secundarias de ARN conocidas, haciendo así que la asignación de probabilidades a las reglas sea una tarea crítica y desafiante. Rivas ofrece una visión más profunda de varios aspectos del modelado de estructuras secundarias de ARN.
Los enfoques de entrenamiento del modelo de maximización de expectativas actuales (EM) generalmente consisten en los siguientes dos pasos: Primero, el algoritmo CYK se utiliza para la predicción de la estructura de cada secuencia de ARN del conjunto de entrenamiento (paso de maximización). En segundo lugar, las probabilidades de regla del SCFG se vuelven a estimar en función de los recuentos o frecuencias de sus ocurrencias en las predicciones (paso de estimación). Estas estimaciones se pueden calcular utilizando el enfoque previo de Laplace explicado en Durbin et al. o implementar enfoques basados en frecuencias similares. El procedimiento EM iterativo puede continuar hasta que las probabilidades de regla resultantes den la precisión deseada. Las técnicas de entrenamiento de modelos pueden variar, ya sea en la definición del criterio de ML (conjunto vs .condicional) o en las técnicas de estimación de regla-probabilidad. Un modelo de plegado de ARN basado en SCFG puede consistir en un SCFG ligero con solo unas pocas reglas gramaticales o puede ser una gramática pesada que consiste en muchas reglas, como super gramáticas descritas en Rivas et al. .
En este trabajo, la entropía de Shannon del SCFG, denotada aquí como entropía de espacio gramatical (GS), se calcula analíticamente e introduce como una característica gramatical crítica en el modelado de estructuras secundarias de ARN. Las formulaciones presentadas son consistentes con la forma general de entropía gramatical conocida como entropía derivacional, y se pueden encontrar en Grenander y Soule . En la sección 9.2, se presenta una formulación para calcular la entropía de Shannon del espacio probabilístico infinitamente grande de grammars1 de modelado de ARN estructuralmente inequívoco que es consistente con las formulaciones de entropía derivacional presentadas en Grenander . Los valores de entropía GS de varios modelos de plegado de ARN bien establecidos se calculan con diferentes conjuntos de parámetros en la sección 9.3. En la Sección 9.4, se propone un criterio para el entrenamiento del modelo de estructura secundaria de ARN basado en SCFG basado en la entropía GS. Por último, la sección 9.5 contiene un análisis y conclusiones.