La teoría gramatical para modelar cadenas de símbolos se originó a partir del trabajo en lingüística computacional que apuntaba a comprender la estructura de los lenguajes naturales . [1] [2] [3] Las gramáticas probabilísticas libres de contexto ( PCFG ) se han aplicado en el modelado probabilístico de estructuras de ARN casi 40 años después de que se introdujeran en la lingüística computacional . [4] [5] [6] [7] [8]
Los PCFG extienden las gramáticas libres de contexto de manera similar a cómo los modelos ocultos de Markov extienden las gramáticas regulares . A cada producción se le asigna una probabilidad. La probabilidad de una derivación (análisis) es el producto de las probabilidades de las producciones utilizadas en esa derivación. Estas probabilidades se pueden ver como parámetros del modelo y, para problemas grandes, es conveniente aprender estos parámetros a través del aprendizaje automático . La validez de una gramática probabilística está limitada por el contexto de su conjunto de datos de entrenamiento.
Los PCFG tienen aplicaciones en áreas tan diversas como el procesamiento del lenguaje natural, el estudio de la estructura de las moléculas de ARN y el diseño de lenguajes de programación . El diseño de PCFG eficientes debe tener en cuenta factores de escalabilidad y generalidad. Deben resolverse cuestiones como la ambigüedad gramatical. El diseño gramatical afecta la precisión de los resultados. Los algoritmos de análisis gramatical tienen diversos requisitos de tiempo y memoria.
Derivación: El proceso de generación recursiva de cadenas a partir de una gramática.
Análisis : encontrar una derivación válida utilizando un autómata.
Árbol de análisis: la alineación de la gramática a una secuencia.
Un ejemplo de un analizador sintáctico para gramáticas PCFG es el autómata pushdown . El algoritmo analiza los no terminales de la gramática de izquierda a derecha de manera similar a una pila . Este enfoque de fuerza bruta no es muy eficiente. En la predicción de la estructura secundaria del ARN, las variantes del algoritmo Cocke–Younger–Kasami (CYK) brindan alternativas más eficientes al análisis sintáctico de gramática que los autómatas pushdown. [9] Otro ejemplo de un analizador sintáctico PCFG es el Analizador estadístico de Stanford que se ha entrenado utilizando Treebank . [10]
De manera similar a una CFG , una gramática probabilística libre de contexto G se puede definir mediante un quíntuple:
dónde
Los modelos PCFG extienden las gramáticas libres de contexto de la misma manera que los modelos ocultos de Markov extienden las gramáticas regulares .
El algoritmo Inside-Outside es un análogo del algoritmo Forward-Backward . Calcula la probabilidad total de todas las derivaciones que son consistentes con una secuencia dada, en función de algún PCFG. Esto es equivalente a la probabilidad de que el PCFG genere la secuencia y es intuitivamente una medida de cuán consistente es la secuencia con la gramática dada. El algoritmo Inside-Outside se utiliza en la parametrización de modelos para estimar frecuencias previas observadas a partir de secuencias de entrenamiento en el caso de ARN.
Las variantes de programación dinámica del algoritmo CYK encuentran el análisis de Viterbi de una secuencia de ARN para un modelo PCFG. Este análisis es la derivación más probable de la secuencia por el modelo PCFG dado.
Las gramáticas libres de contexto se representan como un conjunto de reglas inspiradas en los intentos de modelar lenguajes naturales. [3] Las reglas son absolutas y tienen una representación sintáctica típica conocida como forma Backus–Naur . Las reglas de producción consisten en símbolos S terminales y no terminales y también se puede usar un espacio en blanco como punto final. En las reglas de producción de CFG y PCFG, el lado izquierdo tiene solo un no terminal, mientras que el lado derecho puede ser cualquier cadena de terminales o no terminales. En PCFG, se excluyen los nulos. [9] Un ejemplo de gramática:
Esta gramática se puede acortar utilizando el carácter '|' ('o') en:
Los terminales de una gramática son palabras y, a través de las reglas gramaticales, un símbolo no terminal se transforma en una cadena de terminales y/o no terminales. La gramática anterior se lee como "a partir de una S no terminal , la emisión puede generar a o b o ". Su derivación es:
La gramática ambigua puede dar lugar a un análisis ambiguo si se aplica a homógrafos, ya que la misma secuencia de palabras puede tener más de una interpretación. Las oraciones con juegos de palabras , como el titular del periódico "Cabeza iraquí busca armas", son un ejemplo de análisis ambiguo.
Una estrategia para lidiar con los análisis ambiguos (que se originó con gramáticos como Pāṇini ) es agregar aún más reglas o priorizarlas de modo que una regla prevalezca sobre las demás. Sin embargo, esto tiene el inconveniente de que proliferan las reglas, a menudo hasta el punto en que se vuelven difíciles de manejar. Otra dificultad es la sobregeneración, donde también se generan estructuras sin licencia.
Las gramáticas probabilísticas evitan estos problemas clasificando las distintas producciones según su peso de frecuencia, lo que da como resultado una interpretación "más probable" (el ganador se lleva todo). A medida que se alteran los patrones de uso en los cambios diacrónicos , estas reglas probabilísticas se pueden volver a aprender, actualizando así la gramática.
La asignación de probabilidad a las reglas de producción crea un PCFG. Estas probabilidades se obtienen al observar distribuciones en un conjunto de entrenamiento de composición similar al lenguaje que se va a modelar. En la mayoría de las muestras de lenguaje amplio, las gramáticas probabilísticas en las que las probabilidades se estiman a partir de datos suelen superar a las gramáticas elaboradas a mano. Los CFG, en contraste con los PCFG, no son aplicables a la predicción de la estructura del ARN porque, si bien incorporan la relación secuencia-estructura, carecen de las métricas de puntuación que revelan un potencial estructural de la secuencia [11].
Una gramática libre de contexto ponderada ( WCFG ) es una categoría más general de gramática libre de contexto , donde cada producción tiene un peso numérico asociado. El peso de un árbol de análisis específico en un WCFG es el producto [12] (o la suma [13] ) de todos los pesos de las reglas en el árbol. Cada peso de regla se incluye con la misma frecuencia con la que se utiliza la regla en el árbol. Un caso especial de WCFG son los PCFG, donde los pesos son ( logaritmos de [14] [15] ) probabilidades .
Se puede utilizar una versión extendida del algoritmo CYK para encontrar la derivación "más liviana" (de menor peso) de una cadena dado algún WCFG.
Cuando el peso del árbol es el producto de los pesos de las reglas, los WCFG y los PCFG pueden expresar el mismo conjunto de distribuciones de probabilidad . [12]
La minimización de energía [16] [17] y la PCFG proporcionan formas de predecir la estructura secundaria del ARN con un rendimiento comparable. [4] [5] [9] Sin embargo, la predicción de la estructura mediante PCFG se califica de manera probabilística en lugar de mediante el cálculo de la energía libre mínima. Los parámetros del modelo PCFG se derivan directamente de las frecuencias de diferentes características observadas en bases de datos de estructuras de ARN [11] en lugar de mediante una determinación experimental como es el caso de los métodos de minimización de energía. [18] [19]
Los tipos de estructuras diversas que pueden ser modeladas por un PCFG incluyen interacciones de largo alcance, estructura por pares y otras estructuras anidadas. Sin embargo, los pseudonudos no pueden ser modelados. [4] [5] [9] Los PCFG extienden CFG asignando probabilidades a cada regla de producción. Un árbol de análisis de máxima probabilidad de la gramática implica una estructura de máxima probabilidad. Dado que los ARN preservan sus estructuras a lo largo de su secuencia primaria, la predicción de la estructura del ARN puede guiarse combinando información evolutiva del análisis comparativo de secuencias con conocimiento biofísico sobre la plausibilidad de una estructura basada en tales probabilidades. Además, los resultados de búsqueda de homólogos estructurales utilizando reglas PCFG se califican de acuerdo con las probabilidades de derivación de PCFG. Por lo tanto, la construcción de una gramática para modelar el comportamiento de pares de bases y regiones monocatenarias comienza con la exploración de características de la alineación de secuencias múltiples estructurales de ARN relacionados. [9]
La gramática anterior genera una cadena de afuera hacia adentro, es decir, primero se deriva el par de bases en los extremos más alejados de la terminal. Por lo tanto, una cadena como la que se deriva se genera primero generando las a distales en ambos lados antes de moverse hacia adentro:
La extensibilidad de un modelo PCFG permite restringir la predicción de la estructura incorporando expectativas sobre diferentes características de un ARN. Dicha expectativa puede reflejar, por ejemplo, la propensión a suponer una determinada estructura por parte de un ARN. [11] Sin embargo, la incorporación de demasiada información puede aumentar la complejidad del espacio y la memoria del PCFG y es deseable que un modelo basado en PCFG sea lo más simple posible. [11] [20]
A cada cadena posible x que genera una gramática se le asigna un peso de probabilidad dado el modelo PCFG . De ello se deduce que la suma de todas las probabilidades de todas las posibles producciones de gramática es . Las puntuaciones para cada residuo apareado y no apareado explican la probabilidad de formaciones de estructura secundaria. Las reglas de producción también permiten puntuar las longitudes de los bucles, así como el orden de apilamiento de pares de bases, por lo que es posible explorar el rango de todas las generaciones posibles, incluidas las estructuras subóptimas de la gramática, y aceptar o rechazar estructuras en función de los umbrales de puntuación. [9] [11]
Las implementaciones de estructura secundaria de ARN basadas en enfoques PCFG se pueden utilizar en:
Existen diferentes implementaciones de estos enfoques. Por ejemplo, Pfold se utiliza en la predicción de la estructura secundaria a partir de un grupo de secuencias de ARN relacionadas, [20] los modelos de covarianza se utilizan en la búsqueda de bases de datos de secuencias homólogas y la anotación y clasificación de ARN, [4] [24] RNApromo, CMFinder y TEISER se utilizan para encontrar motivos estructurales estables en ARN. [25] [26] [27]
El diseño de PCFG afecta la precisión de la predicción de la estructura secundaria. Cualquier modelo probabilístico de predicción de la estructura útil basado en PCFG debe mantener la simplicidad sin comprometer demasiado la precisión de la predicción. Un modelo demasiado complejo con un rendimiento excelente en una sola secuencia puede no escalar. [9] Un modelo basado en gramática debería poder:
El resultado de múltiples árboles de análisis por gramática denota ambigüedad gramatical. Esto puede ser útil para revelar todas las posibles estructuras de pares de bases para una gramática. Sin embargo, una estructura óptima es aquella en la que existe una y solo una correspondencia entre el árbol de análisis y la estructura secundaria.
Se pueden distinguir dos tipos de ambigüedades: la ambigüedad del árbol de análisis y la ambigüedad estructural. La ambigüedad estructural no afecta a los enfoques termodinámicos, ya que la selección de la estructura óptima siempre se basa en las puntuaciones de energía libre más bajas. [11] La ambigüedad del árbol de análisis se refiere a la existencia de múltiples árboles de análisis por secuencia. Tal ambigüedad puede revelar todas las posibles estructuras de pares de bases para la secuencia generando todos los árboles de análisis posibles y luego encontrando el óptimo. [ 28] [29] [30] En el caso de la ambigüedad estructural, múltiples árboles de análisis describen la misma estructura secundaria. Esto oscurece la decisión del algoritmo CYK sobre la búsqueda de una estructura óptima, ya que la correspondencia entre el árbol de análisis y la estructura no es única. [31] La ambigüedad gramatical se puede verificar mediante el algoritmo condicional interno. [9] [11]
Una gramática probabilística libre de contexto consta de variables terminales y no terminales. Cada característica que se va a modelar tiene una regla de producción a la que se le asigna una probabilidad estimada a partir de un conjunto de entrenamiento de estructuras de ARN. Las reglas de producción se aplican de forma recursiva hasta que solo quedan residuos terminales.
Un no terminal inicial produce bucles. El resto de la gramática continúa con parámetros que deciden si un bucle es el comienzo de un tallo o una región monocatenaria y parámetros que producen bases pareadas.
El formalismo de este PCFG simple se ve así:
La aplicación de las PCFG para predecir estructuras es un proceso de varios pasos. Además, la propia PCFG puede incorporarse a modelos probabilísticos que consideren la historia evolutiva del ARN o busquen secuencias homólogas en bases de datos. En un contexto de historia evolutiva, la inclusión de distribuciones previas de estructuras de ARN de una alineación estructural en las reglas de producción de la PCFG facilita una buena precisión de predicción. [21]
Un resumen de los pasos generales para utilizar PCFG en diversos escenarios:
Existen varios algoritmos que abordan aspectos de los modelos probabilísticos basados en PCFG en la predicción de la estructura del ARN. Por ejemplo, el algoritmo interno-externo y el algoritmo CYK. El algoritmo interno-externo es un algoritmo de puntuación de programación dinámica recursiva que puede seguir paradigmas de maximización de expectativas . Calcula la probabilidad total de todas las derivaciones que son consistentes con una secuencia dada, en función de algún PCFG. La parte interna puntúa los subárboles de un árbol de análisis sintáctico y, por lo tanto, las probabilidades de las subsecuencias dadas un PCFG. La parte externa puntúa la probabilidad del árbol de análisis sintáctico completo para una secuencia completa. [32] [33] CYK modifica la puntuación interna-externa. Nótese que el término "algoritmo CYK" describe la variante CYK del algoritmo interno que encuentra un árbol de análisis sintáctico óptimo para una secuencia utilizando un PCFG. Extiende el algoritmo CYK real utilizado en CFG no probabilísticos. [9]
El algoritmo interno calcula las probabilidades para todo un subárbol de análisis con raíz en para la subsecuencia . El algoritmo externo calcula las probabilidades de un árbol de análisis completo para la secuencia x desde la raíz excluyendo el cálculo de . Las variables α y β refinan la estimación de los parámetros de probabilidad de un PCFG. Es posible reestimar el algoritmo PCFG al encontrar el número esperado de veces que se usa un estado en una derivación mediante la suma de todos los productos de α y β divididos por la probabilidad para una secuencia x dado el modelo . También es posible encontrar el número esperado de veces que se usa una regla de producción mediante una expectativa-maximización que utiliza los valores de α y β . [32] [33] El algoritmo CYK calcula para encontrar el árbol de análisis más probable y produce . [9]
La complejidad de memoria y tiempo para algoritmos PCFG generales en predicciones de estructura de ARN son y respectivamente. Restringir un PCFG puede alterar este requisito, como sucede con los métodos de búsqueda en bases de datos.
Los modelos de covarianza (CM) son un tipo especial de PCFG con aplicaciones en búsquedas de bases de datos para homólogos, anotación y clasificación de ARN. A través de los CM es posible construir perfiles de ARN basados en PCFG donde los ARN relacionados pueden representarse mediante una estructura secundaria de consenso. [4] [5] El paquete de análisis de ARN Infernal utiliza dichos perfiles en la inferencia de alineaciones de ARN. [34] La base de datos Rfam también utiliza CM para clasificar ARN en familias según su estructura e información de secuencia. [24]
Los CM se diseñan a partir de una estructura de ARN de consenso. Un CM permite indels de longitud ilimitada en la alineación. Las terminales constituyen estados en el CM y las probabilidades de transición entre los estados son 1 si no se consideran indels. [9] Las gramáticas en un CM son las siguientes:
El modelo tiene 6 estados posibles y cada gramática de estado incluye diferentes tipos de probabilidades de estructura secundaria de los no terminales. Los estados están conectados por transiciones. Idealmente, los estados de nodo actuales se conectan a todos los estados de inserción y los estados de nodo subsiguientes se conectan a estados de no inserción. Para permitir la inserción de más de una base, los estados de inserción se conectan entre sí. [9]
Para puntuar un modelo CM se utilizan los algoritmos de dentro-fuera. Los CM utilizan una implementación ligeramente diferente de CYK. Los puntajes de emisión de probabilidades logarítmicas para el árbol de análisis sintáctico óptimo - - se calculan a partir de los estados de emisión . Dado que estos puntajes son una función de la longitud de la secuencia, una medida más discriminativa para recuperar un puntaje de probabilidad de árbol de análisis sintáctico óptimo - - se alcanza limitando la longitud máxima de la secuencia que se alineará y calculando las probabilidades logarítmicas en relación con un nulo. El tiempo de cálculo de este paso es lineal al tamaño de la base de datos y el algoritmo tiene una complejidad de memoria de . [9]
El algoritmo KH-99 de Knudsen y Hein sienta las bases del método Pfold para predecir la estructura secundaria del ARN. [20] En este método, la parametrización requiere información del historial evolutivo derivada de un árbol de alineamiento, además de probabilidades de columnas y mutaciones. Las probabilidades gramaticales se observan a partir de un conjunto de datos de entrenamiento.
En una alineación estructural, las probabilidades de las columnas de bases no apareadas y las columnas de bases apareadas son independientes de las demás columnas. Al contar las bases en posiciones de base única y en posiciones apareadas, se obtienen las frecuencias de las bases en bucles y tallos. Para los pares de bases X e Y, una ocurrencia de también se cuenta como una ocurrencia de . Los pares de bases idénticos, como se cuentan dos veces.
Al emparejar secuencias de todas las formas posibles, se estiman las tasas de mutación generales. Para recuperar mutaciones plausibles, se debe utilizar un umbral de identidad de secuencia de modo que la comparación se realice entre secuencias similares. Este enfoque utiliza un umbral de identidad del 85 % entre secuencias emparejadas. Primero, se cuentan las diferencias en las posiciones de bases individuales (excepto en las columnas con espacios) entre pares de secuencias, de modo que si la misma posición en dos secuencias tenía bases X, Y diferentes , el recuento de la diferencia se incrementa para cada secuencia.
mientras que el primer par de secuencias es el segundo par de secuencias
Calcular tasas de mutación. Sea la mutación de la base X a la base Y la probabilidad de que la base no esté emparejada sea el negativo de la tasa de mutación de X a otras bases .
Para bases no apareadas se utiliza una matriz de tasa de mutación de 4 X 4 que satisface que el flujo de mutación de X a Y es reversible: [35]
Para los pares de bases, se genera de manera similar una matriz de distribución de tasa de 16 X 16. [36] [37] La PCFG se utiliza para predecir la distribución de probabilidad previa de la estructura, mientras que las probabilidades posteriores se estiman mediante el algoritmo interno-externo y la estructura más probable se encuentra mediante el algoritmo CYK. [20]
Después de calcular las probabilidades previas de la columna, la probabilidad de alineación se estima sumando todas las estructuras secundarias posibles. Cualquier columna C en una estructura secundaria para una secuencia D de longitud l tal que pueda ser puntuada con respecto al árbol de alineación T y el modelo mutacional M . La distribución previa dada por el PCFG es . El árbol filogenético, T se puede calcular a partir del modelo mediante estimación de máxima verosimilitud. Nótese que los huecos se tratan como bases desconocidas y la suma se puede hacer mediante programación dinámica . [38]
A cada estructura de la gramática se le asignan probabilidades de producción ideadas a partir de las estructuras del conjunto de datos de entrenamiento. Estas probabilidades previas otorgan peso a la precisión de las predicciones. [21] [32] [33] La cantidad de veces que se utiliza cada regla depende de las observaciones del conjunto de datos de entrenamiento para esa característica particular de la gramática. Estas probabilidades se escriben entre paréntesis en el formalismo de la gramática y cada regla tendrá un total de 100 %. [20] Por ejemplo:
Dadas las frecuencias de alineación previas de los datos, la estructura más probable del conjunto predicha por la gramática se puede calcular maximizando mediante el algoritmo CYK. La estructura con el mayor número predicho de predicciones correctas se informa como la estructura de consenso. [20]
Se desea que los enfoques basados en PCFG sean escalables y lo suficientemente generales. Es necesario reducir al mínimo la velocidad en beneficio de la precisión. Pfold aborda las limitaciones del algoritmo KH-99 con respecto a la escalabilidad, las brechas, la velocidad y la precisión. [20]
Si bien los PCFG han demostrado ser herramientas poderosas para predecir la estructura secundaria del ARN, su uso en el campo del análisis de secuencias de proteínas ha sido limitado. De hecho, el tamaño del alfabeto de aminoácidos y la variedad de interacciones observadas en las proteínas hacen que la inferencia gramatical sea mucho más desafiante. [39] Como consecuencia, la mayoría de las aplicaciones de la teoría del lenguaje formal al análisis de proteínas se han restringido principalmente a la producción de gramáticas de menor poder expresivo para modelar patrones funcionales simples basados en interacciones locales. [40] [41] Dado que las estructuras de proteínas comúnmente muestran dependencias de orden superior que incluyen relaciones anidadas y cruzadas, exceden claramente las capacidades de cualquier CFG. [39] Aún así, el desarrollo de PCFG permite expresar algunas de esas dependencias y brindar la capacidad de modelar una gama más amplia de patrones de proteínas.
{{cite book}}
: |journal=
ignorado ( ayuda )