Gramática probabilística libre de contexto

En lingüística teórica y lingüística computacional , las gramáticas probabilísticas libres de contexto ( 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 sintáctico) 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á restringida por el contexto de su conjunto de datos de entrenamiento.

Los PCFG se originaron a partir de la teoría gramatical y 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 sopesar 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.

Definiciones

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. ^[1] Otro ejemplo de un analizador sintáctico PCFG es el Analizador estadístico de Stanford que se ha entrenado utilizando Treebank . ^[2]

Definición formal

De manera similar a una CFG , una gramática probabilística libre de contexto G se puede definir mediante un quíntuple:

${\displaystyle G=(M,T,R,S,P)}$

dónde

• M es el conjunto de símbolos no terminales
• T es el conjunto de símbolos terminales
• R es el conjunto de reglas de producción
• S es el símbolo de inicio
• P es el conjunto de probabilidades de las reglas de producción.

Relación con los modelos ocultos de Markov

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.

Construcción gramatical

Las gramáticas libres de contexto se representan como un conjunto de reglas inspiradas en los intentos de modelar lenguajes naturales. ^{[3] [4] [5]} 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. ^[1] Un ejemplo de gramática: ${\displaystyle \left\{a,b\right\}}$ ${\displaystyle \epsilon }$

${\displaystyle S\to aS,S\to bS,S\to \epsilon }$

Esta gramática se puede acortar utilizando el carácter '|' ('o') en:

${\displaystyle S\to aS|bS|\epsilon }$

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: ${\displaystyle \epsilon }$

${\displaystyle S\Rightarrow aS\Rightarrow abS\Rightarrow abbS\Rightarrow abb}$

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 ^[6].

Gramática ponderada e independiente del contexto

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 ^[7] (o suma ^[8] ) 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 ^{[9] [10]} ) 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 . ^[7]

Aplicaciones

Predicción de la estructura del ARN

Desde la década de 1990, la PCFG se ha aplicado para modelar estructuras de ARN . ^{[11] [12] [13] [14] [15]}

La minimización de energía ^{[16] [17]} y la PCFG proporcionan formas de predecir la estructura secundaria del ARN con un rendimiento comparable. ^{[11] [12] [1]} 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 ^[6] 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 diversas estructuras 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. ^{[11] [12] [1]} Los PCFG extienden CFG al asignar 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. ^[1]

${\displaystyle S\to aSa|bSb|aa|bb}$

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: ${\displaystyle aabaabaa}$

${\displaystyle S\Rightarrow aSa\Rightarrow aaSaa\Rightarrow aabSbaa\Rightarrow aabaabaa}$

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. ^[6] 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. ^{[6] [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. ^{[1] [6]} ${\displaystyle P(x|\theta )}$ ${\displaystyle \theta }$ ${\displaystyle \sum _{\text{x}}P(x|\theta )=1}$

Implementaciones

Las implementaciones de estructura secundaria de ARN basadas en enfoques PCFG se pueden utilizar en:

• Encontrar la estructura de consenso mediante la optimización de las probabilidades conjuntas de la estructura sobre MSA. ^{[20] [21]}
• Modelado de la covariación de pares de bases para detectar homología en búsquedas en bases de datos. ^[11]
• plegado y alineación simultáneos por pares. ^{[22] [23]}

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, ^{[11] [24]} RNApromo, CMFinder y TEISER se utilizan para encontrar motivos estructurales estables en ARN. ^{[25] [26] [27]}

Consideraciones de diseño

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. ^[1] Un modelo basado en gramática debería poder:

• Encuentre la alineación óptima entre una secuencia y el PCFG.
• Califica la probabilidad de las estructuras para la secuencia y subsecuencias.
• Parametrizar el modelo mediante entrenamiento en secuencias/estructuras.
• Encuentre el árbol de análisis gramatical óptimo (algoritmo CYK).
• Comprueba si hay gramática ambigua (algoritmo condicional interno).

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. ^[6] 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. ^{[1] [6]}

Construyendo un modelo PCFG

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. ${\displaystyle \mathbf {\mathit {S}} }$ ${\displaystyle \mathbf {\mathit {L}} }$ ${\displaystyle \mathbf {\mathit {F}} }$

El formalismo de este PCFG simple se ve así:

${\displaystyle {\mathit {S\to LS|L}}}$

${\displaystyle {\mathit {L\to s|dFd}}}$

${\displaystyle {\mathit {F\to dFd|LS}}}$

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 anteriores 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:

• Generar reglas de producción para las secuencias.
• Comprobar ambigüedad.
• Genere de forma recursiva árboles de análisis de las posibles estructuras utilizando la gramática.
• Clasifique y puntúe los árboles de análisis para obtener la secuencia más plausible. ^[1]

Algoritmos

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 y, por lo tanto, las probabilidades de las subsecuencias dadas un PCFG. La parte externa puntúa la probabilidad del árbol de análisis 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 óptimo para una secuencia utilizando un PCFG. Extiende el algoritmo CYK real utilizado en CFG no probabilísticos. ^[1]

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 . ^[1] ${\displaystyle \alpha (i,j,v)}$ ${\displaystyle i,j,v}$ ${\displaystyle W_{v}}$ ${\displaystyle x_{i},...,x_{j}}$ ${\displaystyle \beta (i,j,v)}$ ${\displaystyle x_{i},...,x_{j}}$ ${\displaystyle P(x|\theta )}$ ${\displaystyle \gamma (i,j,v)}$ ${\displaystyle {\hat {\pi }}}$ ${\displaystyle \log P(x,{\hat {\pi }}|\theta )}$

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. ${\displaystyle O(L^{2}M)}$ ${\displaystyle O(L^{3}M^{3})}$

PCFG en la búsqueda de homología

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. ^{[11] [12]} 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. ^[1] Las gramáticas en un CM son las siguientes:

${\displaystyle P\to aWb}$

Probabilidades de interacciones por pares entre 16 pares posibles

${\displaystyle L\to aW}$

Probabilidades de generar 4 posibles bases individuales a la izquierda.

${\displaystyle R\to Wa}$

Probabilidades de generar 4 posibles bases individuales a la derecha

${\displaystyle B\to SS}$

bifurcación con una probabilidad de 1

${\displaystyle S\to W}$

comienza con una probabilidad de 1

${\displaystyle E\to \epsilon }$

termina con una probabilidad de 1

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í. ^[1]

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 valor 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 . ^[1] ${\displaystyle \log {\hat {e}}}$ ${\displaystyle P,~L,~R}$ ${\displaystyle \log {\text{P}}(x,{\hat {\pi }}|\theta )}$ ${\displaystyle O(M_{a}D+M_{b}D^{2})}$

Ejemplo: Uso de información evolutiva para orientar la predicción de estructuras

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.

Estimar probabilidades de columna para bases pareadas y no pareadas

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. ${\displaystyle XY}$ ${\displaystyle YX}$ ${\displaystyle XX}$

Calcular tasas de mutación para bases apareadas y no apareadas

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 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  ${\displaystyle X\neq Y}$ el primer par de secuencias es el segundo par de secuencias ${\displaystyle C_{\text{XY}}+1}$  ${\displaystyle C_{\text{YX}}+1}$

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  ${\displaystyle r_{\text{XY}}=}$ ${\displaystyle ={\frac {K~C_{\text{XY}}}{P_{x}P_{s}}}}$ sea el negativo de la tasa de mutación de X a otras bases  ${\displaystyle r_{\text{XX}}=}$ ${\displaystyle =-\sum r_{\text{XY}}}$ . ${\displaystyle P_{s}=}$

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]

${\displaystyle PX^{r}XY=PY^{r}YX}$

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]

Estimar probabilidades de alineación

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] ${\displaystyle \sigma }$ ${\displaystyle D=(C_{1},~C_{2},...C_{l})}$ ${\displaystyle P(\sigma |M)}$

${\displaystyle P(D|T,M)}$

${\displaystyle =\sum P(D,\sigma |T,M)}$

${\displaystyle =\sum P(D|\sigma ,T,M)P(\sigma |T,M)}$

${\displaystyle =\sum P(D|\sigma ,T,M)P(\sigma |M)}$

Asignar probabilidades de producción a cada regla en la gramática

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:

${\displaystyle S\to LS(80\%)|L(20\%)}$

${\displaystyle L\to s(70\%)|dFd(30\%)}$

${\displaystyle F\to dFd(60.4\%)|LS(39.6\%)}$

Predecir la probabilidad de la estructura

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] ${\displaystyle P(\sigma |D,T,M)}$

${\displaystyle \sigma _{MAP}=\arg {\underset {\sigma }{\max }}P(D|\sigma ,T^{M}L,M)P(\sigma |M)}$

Mejoras de Pfold en el algoritmo KH-99

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]

• En Pfold, los huecos se consideran desconocidos. En este sentido, la probabilidad de una columna con huecos es igual a la de una columna sin huecos.
• En Pfold, el árbol T se calcula antes de la predicción de la estructura mediante la unión de vecinos y no por máxima verosimilitud mediante la gramática PCFG. Solo las longitudes de las ramas se ajustan a las estimaciones de máxima verosimilitud.
• Una de las premisas de Pfold es que todas las secuencias tienen la misma estructura. El umbral de identidad de secuencia y la posibilidad de que haya una probabilidad del 1 % de que cualquier nucleótido se convierta en otro limitan el deterioro del rendimiento debido a errores de alineación.

Análisis de secuencia de proteínas

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.

Véase también

• Análisis estadístico
• Gramática estocástica
• Sistema L

Referencias

1. R. Durbin; S. Eddy; A. Krogh; G. Mitchinson (1998). Análisis de secuencias biológicas: modelos probabilísticos de proteínas y ácidos nucleicos. Cambridge University Press. ISBN 978-0-521-62971-3.
2. Klein, Daniel; Manning, Christopher (2003). "Análisis sintáctico preciso y no lexicalizado" (PDF) . Actas de la 41.ª reunión de la Asociación de Lingüística Computacional : 423–430.
3. Chomsky, Noam (1956). "Tres modelos para la descripción del lenguaje". IRE Transactions on Information Theory . 2 (3): 113–124. doi :10.1109/TIT.1956.1056813. S2CID  19519474.
4. Chomsky, Noam (junio de 1959). "Sobre ciertas propiedades formales de las gramáticas". Información y control . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .
5. Noam Chomsky, ed. (1957). Estructuras sintácticas . Mouton & Co. Publishers, La Haya, Países Bajos.
6. Dowell R. y Eddy S. (2004). "Evaluación de varias gramáticas estocásticas ligeras e independientes del contexto para la predicción de la estructura secundaria del ARN". BMC Bioinformatics . 5 (71): 71. doi : 10.1186/1471-2105-5-71 . PMC 442121 . PMID  15180907. 
7. Smith, Noah A.; Johnson, Mark (2007). "Las gramáticas libres de contexto ponderadas y probabilísticas son igualmente expresivas" (PDF) . Computational Linguistics . 33 (4): 477. doi :10.1162/coli.2007.33.4.477. S2CID  1405777.
8. Katsirelos, George; Narodytska, Nina; Walsh, Toby (2008). "La restricción ponderada CFG". Integración de técnicas de IA y OR en programación de restricciones para problemas de optimización combinatoria . Apuntes de clase en informática. Vol. 5015. págs. 323–327. CiteSeerX 10.1.1.150.1187 . doi :10.1007/978-3-540-68155-7_31. ISBN .  978-3-540-68154-0.S2CID 9375313  .
9. Johnson, Mark (2005). "Modelos log-lineales o de Gibbs" (PDF) .
10. Chi, Zhiyi (marzo de 1999). "Propiedades estadísticas de gramáticas probabilísticas libres de contexto" (PDF) . Computational Linguistics . 25 (1): 131–160. Archivado desde el original (PDF) el 21 de agosto de 2010.
11. Eddy SR y Durbin R. (1994). "Análisis de secuencias de ARN utilizando modelos de covarianza". Nucleic Acids Research . 22 (11): 2079–2088. doi :10.1093/nar/22.11.2079. PMC 308124 . PMID  8029015. 
12. Sakakibara Y.; Brown M.; Hughey R.; Mian IS; et al. (1994). "Gramáticas estocásticas libres de contexto para el modelado de ARNt". Nucleic Acids Research . 22 (23): 5112–5120. doi :10.1093/nar/22.23.5112. PMC 523785 . PMID  7800507. 
13. Grat, L. (1995). "Determinación automática de la estructura secundaria del ARN con gramáticas estocásticas libres de contexto" (PDF) . En Rawlings, C., Clark, D., Altman, R., Hunter, L., Lengauer, T y Wodak, S. Actas de la Tercera Conferencia Internacional sobre Sistemas Inteligentes para Biología Molecular, AAAI Press : 136–144. Archivado desde el original (PDF) el 2015-12-04 . Consultado el 2017-08-03 .
14. Lefebvre, F (1995). "Un algoritmo de análisis optimizado muy adecuado para el plegamiento del ARN". En Rawlings, C.; Clark, D.; Altman, R.; Hunter, L.; Lengauer, T.; Wodak, S. (eds.). Actas de la Tercera Conferencia Internacional sobre Sistemas Inteligentes para Biología Molecular (PDF) . AAAI Press. págs. 222–230.
15. Lefebvre, F. (1996). "Una unificación basada en gramática de varios algoritmos de alineamiento y plegado". En Estados Unidos, DJ; Agarwal, P.; Gaasterlan, T.; Hunter, L.; Smith RF (eds.). Actas de la Cuarta Conferencia Internacional sobre Sistemas Inteligentes para Biología Molecular (PDF) . AAAI Press. págs. 143–153.
16. McCaskill JS (1990). "La función de partición de equilibrio y las probabilidades de unión de pares de bases para la estructura secundaria del ARN". Biopolímeros . 29 (6–7): 1105–19. doi :10.1002/bip.360290621. hdl : 11858/00-001M-0000-0013-0DE3-9 . PMID  1695107. S2CID  12629688.
17. Juan V.; Wilson C. (1999). "Predicción de la estructura secundaria del ARN basada en energía libre y análisis filogenético". J. Mol. Biol . 289 (4): 935–947. doi :10.1006/jmbi.1999.2801. PMID  10369773.
18. Zuker M (2000). "Cálculo de la estructura secundaria de los ácidos nucleicos". Curr. Opin. Struct. Biol . 10 (3): 303–310. doi :10.1016/S0959-440X(00)00088-9. PMID  10851192.
19. Mathews DH; Sabina J.; Zuker M.; Turner DH (1999). "La dependencia de la secuencia expandida de los parámetros termodinámicos mejora la predicción de la estructura secundaria del ARN". J. Mol. Biol . 288 (5): 911–940. doi : 10.1006/jmbi.1999.2700 . PMID  10329189. S2CID  19989405.
20. B. Knudsen y J. Hein. (2003). "Pfold: predicción de la estructura secundaria del ARN utilizando gramáticas estocásticas libres de contexto". Investigación de ácidos nucleicos . 31 (13): 3423–3428. doi :10.1093/nar/gkg614. PMC 169020. PMID  12824339 . 
21. Knudsen B.; Hein J. (1999). "Predicción de la estructura secundaria del ARN utilizando gramáticas estocásticas libres de contexto e historia evolutiva". Bioinformática . 15 (6): 446–454. doi : 10.1093/bioinformatics/15.6.446 . PMID  10383470.
22. Rivas E.; Eddy SR (2001). "Detección de genes de ARN no codificante mediante análisis comparativo de secuencias". BMC Bioinformatics . 2 (1): 8. doi : 10.1186/1471-2105-2-8 . PMC 64605 . PMID  11801179. 
23. Holmes I.; Rubin GM (2002). Comparación de la estructura del ARN por pares con gramáticas estocásticas libres de contexto . pp. 163–174. doi :10.1142/9789812799623_0016. ISBN 978-981-02-4777-5. Número de identificación personal  11928472. {{cite book}}: |journal=ignorado ( ayuda )
24. PP Gardner; J. Daub; J. Tate; BL Moore; IH Osuch; S. Griffiths-Jones; RD Finn; EP Nawrocki; DL Kolbe; SR Eddy; A. Bateman. (2011). "Rfam: Wikipedia, clanes y la publicación "decimal"". Nucleic Acids Research . 39 (Supl 1): D141–D145. doi :10.1093/nar/gkq1129. PMC 3013711 . PMID  21062808. 
25. Yao Z.; Weinberg Z.; Ruzzo WL (2006). "CMfinder: un algoritmo de búsqueda de motivos de ARN basado en un modelo de covarianza". Bioinformática . 22 (4): 445–452. doi : 10.1093/bioinformatics/btk008 . PMID  16357030.
26. Rabani M.; Kertesz M.; Segal E. (2008). "Predicción computacional de motivos estructurales de ARN implicados en procesos de regulación postranscripcional". Proc. Natl. Sci. USA . 105 (39): 14885–14890. Bibcode :2008PNAS..10514885R. doi : 10.1073/pnas.0803169105 . PMC 2567462 . PMID  18815376. 
27. Goodarzi H.; Najafabadi HS; Oikonomou P.; Greco TM; Fish L.; Salavati R.; Cristea IM; Tavazoie S. (2012). "Descubrimiento sistemático de elementos estructurales que rigen la estabilidad de los ARN mensajeros de mamíferos". Nature . 485 (7397): 264–268. Bibcode :2012Natur.485..264G. doi :10.1038/nature11013. PMC 3350620 . PMID  22495308. 
28. Sipser M. (1996). Introducción a la teoría de la computación . Brooks Cole Pub Co.
29. Michael A. Harrison (1978). Introducción a la teoría del lenguaje formal . Addison-Wesley.
30. Hopcroft JE; Ullman JD (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley.
31. Giegerich R. (2000). "Explicación y control de la ambigüedad en la programación dinámica". Coincidencia de patrones combinatorios . Apuntes de clase en informática. Vol. 1848. En Actas del 11.º simposio anual sobre coincidencia de patrones combinatorios 1848. Editado por: Giancarlo R., Sankoff D. Montreal, Canadá: Springer-Verlag, Berlín. págs. 46–59. doi :10.1007/3-540-45123-4_6. ISBN. 978-3-540-67633-1.S2CID17088251  .​
32. Lari K.; Young SJ (1990). "La estimación de gramáticas estocásticas libres de contexto utilizando el algoritmo dentro-fuera". Lenguaje y habla por computadora . 4 : 35–56. doi :10.1016/0885-2308(90)90022-X.
33. Lari K.; Young SJ (1991). "Aplicaciones de gramáticas estocásticas libres de contexto utilizando el algoritmo dentro-fuera". Lenguaje y habla por computadora . 5 (3): 237–257. doi :10.1016/0885-2308(91)90009-F.
34. Nawrocki EP, Eddy SR (2013). "Infernal 1.1: búsquedas de homología de ARN 100 veces más rápidas". Bioinformática . 29 (22): 2933–2935. doi :10.1093/bioinformatics/btt509. PMC 3810854 . PMID  24008419. 
35. Tavaré S. (1986). "Algunos problemas probabilísticos y estadísticos en el análisis de secuencias de ADN". Lecciones de matemáticas en las ciencias de la vida. American Mathematical Society . 17 : 57–86.
36. Muse SV (1995). "Análisis evolutivo de secuencias de ADN sujetas a restricciones de estructura secundaria". Genética . 139 (3): 1429–1439. doi :10.1093/genetics/139.3.1429. PMC 1206468 . PMID  7768450. 
37. Schöniger M.; von Haeseler A. (1994). "Un modelo estocástico para la evolución de secuencias de ADN autocorrelacionadas". Mol. Phylogenet. Evol . 3 (3): 240–7. Bibcode :1994MolPE...3..240S. doi :10.1006/mpev.1994.1026. PMID  7529616.
38. Baker, JK (1979). "Gramáticas entrenables para el reconocimiento de voz". Revista de la Sociedad Acústica de América . 65 (S1): S132. Código Bibliográfico :1979ASAJ...65Q.132B. doi : 10.1121/1.2017061 .
39. Searls, D (2013). "Revisión: Una introducción a la lingüística macromolecular". Biopolímeros . 99 (3): 203–217. doi :10.1002/bip.22101. PMID  23034580. S2CID  12676925.
40. Krogh, A; Brown, M; Mian, I; Sjolander, K; Haussler, D (1994). "Modelos ocultos de Markov en biología computacional: aplicaciones al modelado de proteínas". J Mol Biol . 235 (5): 1501–1531. doi :10.1006/jmbi.1994.1104. PMID  8107089. S2CID  2160404.
41. Sigrist, C; Cerutti, L; Hulo, N; Gattiker, A; Falquet, L; Pagni, M; Bairoch, A; Bucher, P (2002). "PROSITE: una base de datos documentada que utiliza patrones y perfiles como descriptores de motivos". Brief Bioinform . 3 (3): 265–274. doi : 10.1093/bib/3.3.265 . PMID  12230035.

Enlaces externos

• Base de datos de RFAM
• Infernal
• El analizador Stanford: un analizador estadístico
• Analizador de PyStat