Hispanopedia Wiki
Articulo de referencia

Gramática probabilística libre de contexto

En lingüística teórica y computacional , las gramáticas libres de contexto probabilísticas ( GLPCP ) extienden las gramáticas libres de contexto , de forma similar a como los mo...

Hispanopedia WikiContenido en espanolLectura gratuita

En lingüística teórica y computacional , las gramáticas libres de contexto probabilísticas ( GLPCP ) extienden las gramáticas libres de contexto , de forma similar a como 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 dicha derivación. Estas probabilidades pueden considerarse parámetros del modelo, y para problemas de gran tamaño resulta conveniente aprenderlos mediante aprendizaje automático . La validez de una gramática probabilística está limitada por el contexto de su conjunto de datos de entrenamiento.

Las gramáticas funcionales con contexto (PCFG) se originaron en 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 requiere considerar factores como la escalabilidad y la generalidad. Es necesario resolver problemas como la ambigüedad gramatical. El diseño de la gramática afecta la precisión de los resultados. Los algoritmos de análisis sintáctico de gramáticas 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 sintáctico : Encontrar una derivación válida utilizando un autómata.

Árbol de análisis sintáctico: La alineación de la gramática con una secuencia.

Un ejemplo de analizador sintáctico para gramáticas PCFG es el autómata de pila . El algoritmo analiza los no terminales de la gramática de izquierda a derecha de forma apilada . Este enfoque de fuerza bruta no es muy eficiente. En la predicción de la estructura secundaria del ARN, las variantes del algoritmo de Cocke-Younger-Kasami (CYK) proporcionan alternativas más eficientes para el análisis sintáctico de gramáticas que los autómatas de pila. [ 1 ] Otro ejemplo de analizador sintáctico PCFG es el analizador estadístico de Stanford, que ha sido entrenado con Treebank . [ 2 ]

Definición formal

De forma similar a una CFG , una gramática libre de contexto probabilística G puede definirse mediante una quíntupla:

GRAMO=(METRO,T,R,S,PAG){\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 análogo al algoritmo Forward-Backward . Calcula la probabilidad total de todas las derivaciones que son consistentes con una secuencia dada, basándose en una gramática libre de contexto (PCFG). Esto equivale a la probabilidad de que la PCFG genere la secuencia y, de forma intuitiva, es una medida de la consistencia de la secuencia con la gramática dada. El algoritmo Inside-Outside se utiliza en la parametrización de modelos para estimar las frecuencias previas observadas en las secuencias de entrenamiento en el caso de los 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 mediante el PCFG dado.

Construcción gramatical

Las gramáticas libres de contexto se representan como un conjunto de reglas inspiradas en intentos de modelar lenguajes naturales. [ 3 ] [ 4 ] [ 5 ] Las reglas son absolutas y tienen una representación sintáctica típica conocida como forma de Backus-Naur . Las reglas de producción consisten en terminales{a,b}{\displaystyle \left\{a,b\right\}}y símbolos S no terminales y un espacio en blancoϵ{\displaystyle \epsilon }También puede usarse 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, los caracteres nulos están excluidos. [ 1 ] Un ejemplo de gramática:

S→aS,S→bS,S→ϵ{\displaystyle S\to aS,S\to bS,S\to \epsilon }

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

S→aS|bS|ϵ{\displaystyle S\to aS|bS|\epsilon }

Los terminales en 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 un no terminal S la emisión puede generar a o b oϵ{\displaystyle \epsilon }". Su derivación es:

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

La gramática ambigua puede dar lugar a un análisis sintáctico ambiguo si se aplica a homógrafos , ya que una misma secuencia de palabras puede tener más de una interpretación. Los juegos de palabras como el titular del periódico "Iraqi Head Seeks Arms" son un ejemplo de análisis sintáctico ambiguo.

Una estrategia para abordar los análisis sintácticos ambiguos (que se remonta a gramáticos como Pāṇini ) consiste en añadir más reglas o priorizarlas de forma que una tenga precedencia sobre las demás. Sin embargo, esto tiene el inconveniente de multiplicar las reglas, a menudo hasta el punto de que resultan difíciles de gestionar. Otra dificultad es la sobregeneración, donde también se generan estructuras no permitidas.

Las gramáticas probabilísticas sortean estos problemas clasificando las distintas producciones según su frecuencia, lo que da como resultado una interpretación de "la más probable" (donde el ganador se lo lleva todo). A medida que los patrones de uso se modifican con los cambios diacrónicos , estas reglas probabilísticas pueden reaprenderse, actualizando así la gramática.

Asignar probabilidad a las reglas de producción crea una PCFG. Estas probabilidades se basan en la observación de 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, donde las probabilidades se estiman a partir de datos, suelen superar a las gramáticas diseñadas manualmente. Las CFG, en comparación con las 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 el potencial estructural de una secuencia [ 6 ].

Gramática libre de contexto ponderada

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 una WCFG es el producto [ 7 ] (o suma [ 8 ] ) de todos los pesos de las reglas en el árbol. Cada peso de regla se incluye tantas veces como se usa la regla en el árbol. Un caso especial de WCFG son las 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 ligera" (de menor peso) de una cadena dada una 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, PCFG se ha aplicado para modelar estructuras de ARN . [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ]

La minimización de energía [ 16 ] [ 17 ] y PCFG proporcionan métodos para predecir la estructura secundaria del ARN con un rendimiento comparable. [ 11 ] [ 12 ] [ 1 ] Sin embargo, la predicción de la estructura mediante PCFG se puntúa probabilísticamente 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 determinación experimental, como ocurre con los métodos de minimización de energía . [ 18 ] [ 19 ]

Los tipos de estructuras que pueden ser modeladas por una PCFG incluyen interacciones de largo alcance, estructuras de pares y otras estructuras anidadas. Sin embargo, los pseudonudos no pueden ser modelados. [ 11 ] [ 12 ] [ 1 ] Las PCFG extienden las CFG asignando probabilidades a cada regla de producción. Un árbol de análisis de probabilidad máxima de la gramática implica una estructura de probabilidad máxima. Dado que los ARN conservan 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 dichas probabilidades. Además, los resultados de búsqueda de homólogos estructurales utilizando reglas PCFG se puntúan según 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 alineación de secuencias múltiples estructurales de ARN relacionados. [ 1 ]

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

La gramática anterior genera una cadena de afuera hacia adentro, es decir, el par de bases en los extremos más alejados del terminal se deriva primero. Por lo tanto, una cadena comoaabaabaa{\displaystyle aabaabaa}se obtiene generando primero las ' s' distales en ambos lados antes de moverse hacia adentro:

S⇒aSa⇒aaSaa⇒aabSbaa⇒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 al incorporar expectativas sobre diferentes características de un ARN. Dicha expectativa puede reflejar, por ejemplo, la propensión de un ARN a adoptar una estructura determinada. [ 6 ] Sin embargo, la incorporación de demasiada información puede aumentar el espacio y la complejidad de memoria del PCFG, por lo que 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.PAG(incógnita|θ){\displaystyle P(x|\theta )}dado el modelo PCFGθ{\displaystyle \theta }De ello se deduce que la suma de todas las probabilidades de todas las posibles producciones gramaticales es ∑incógnitaPAG(incógnita|θ)=1{\displaystyle \sum _{\text{x}}P(x|\theta )=1}Las puntuaciones para cada residuo emparejado y no emparejado explican la probabilidad de formación de estructuras secundarias. 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 tanto, 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 umbrales de puntuación. [ 1 ] [ 6 ]

Implementaciones

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

  • Encontrar la estructura de consenso optimizando 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 en 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 influye en la precisión de la predicción de la estructura secundaria. Cualquier modelo probabilístico de predicción de 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 ser escalable. [ 1 ] Un modelo basado en gramática debería ser capaz de:

  • Encuentra la alineación óptima entre una secuencia y el PCFG.
  • Calcula la probabilidad de las estructuras para la secuencia y las subsecuencias.
  • Parametrizar el modelo entrenándolo con secuencias/estructuras.
  • Encontrar el árbol de análisis gramatical óptimo (algoritmo CYK).
  • Comprobación de gramática ambigua (algoritmo Condicional Interno).

La presencia de múltiples árboles de análisis sintáctico por gramática indica ambigüedad gramatical. Esto puede ser útil para revelar todas las posibles estructuras de pares de bases de una gramática. Sin embargo, una estructura óptima es aquella en la que existe una única correspondencia entre el árbol de análisis sintáctico y la estructura secundaria.

Se pueden distinguir dos tipos de ambigüedades: ambigüedad del árbol de análisis y 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. Dicha ambigüedad puede revelar todas las posibles estructuras de pares de bases para la secuencia al generar todos los árboles de análisis posibles y luego encontrar 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 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 recursivamente hasta que solo quedan residuos terminales.

Un no terminal de inicioS{\displaystyle \mathbf {\mathit {S}} }produce bucles. El resto de la gramática procede con el parámetroL{\displaystyle \mathbf {\mathit {L}} }que deciden si un bucle es el inicio de un tallo o una región de cadena simple y parámetroF{\displaystyle \mathbf {\mathit {F}} }que produce bases emparejadas.

El formalismo de este sencillo PCFG se ve así:

S→LS|L{\displaystyle {\mathit {S\to LS|L}}}
L→s|dFd{\displaystyle {\mathit {L\to s|dFd}}}
F→dFd|LS{\displaystyle {\mathit {F\to dFd|LS}}}

La aplicación de los PCFG en la predicción de estructuras es un proceso de varios pasos. Además, el propio PCFG puede incorporarse a modelos probabilísticos que consideran la historia evolutiva del ARN o que buscan 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 del PCFG facilita una buena precisión de predicción. [ 21 ]

Resumen de los pasos generales para utilizar los PCFG en diversos escenarios:

  • Generar reglas de producción para las secuencias.
  • Verificar la ambigüedad.
  • Generar recursivamente árboles de análisis sintáctico de las posibles estructuras utilizando la gramática.
  • Clasifique y puntúe los árboles de análisis para 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 inside-outside y el algoritmo CYK. El algoritmo inside-outside es un algoritmo de puntuación de programación dinámica recursiva que puede seguir paradigmas de expectativa-maximización . Calcula la probabilidad total de todas las derivaciones que son consistentes con una secuencia dada, basándose en algún PCFG. La parte inside puntúa los subárboles de un árbol de análisis y, por lo tanto, las probabilidades de las subsecuencias dada un PCFG. La parte outside puntúa la probabilidad del árbol de análisis completo para una secuencia completa. [ 32 ] [ 33 ] CYK modifica la puntuación inside-outside. Nótese que el término "algoritmo CYK" describe la variante CYK del algoritmo inside 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α(i,j,v){\displaystyle \alpha (i,j,v)}probabilidades para todosi,j,v{\displaystyle i,j,v} de un subárbol de análisis sintáctico enraizado enWv{\displaystyle W_{v}}para subsecuenciaincógnitai,...,incógnitaj{\displaystyle x_{i},...,x_{j}}. El algoritmo externo calculaβ(i,j,v){\displaystyle \beta (i,j,v)}probabilidades de un árbol de análisis completo para la secuencia x desde la raíz excluyendo el cálculo deincógnitai,...,incógnitaj{\displaystyle x_{i},...,x_{j}}Las variables α y β refinan la estimación de los parámetros de probabilidad de un PCFG. Es posible reestimar el algoritmo PCFG hallando el número esperado de veces que se utiliza un estado en una derivación mediante la suma de todos los productos de α y β divididos por la probabilidad de una secuencia x dado el modelo.PAG(incógnita|θ){\displaystyle P(x|\theta )}También es posible hallar el número esperado de veces que se utiliza una regla de producción mediante una maximización de la expectativa que utiliza los valores de α y β . [ 32 ] [ 33 ] El algoritmo CYK calculaγ(i,j,v){\displaystyle \gamma (i,j,v)}para encontrar el árbol de análisis sintáctico más probableπ^{\displaystyle {\hat {\pi }}}y rendimientosregistro⁡PAG(incógnita,π^|θ){\displaystyle \log P(x,{\hat {\pi }}|\theta )}. [ 1 ]

La complejidad temporal y de memoria para los algoritmos PCFG generales en predicciones de estructura de ARN son:O(L2METRO){\displaystyle O(L^{2}M)}yO(L3METRO3){\displaystyle O(L^{3}M^{3})}respectivamente. Restringir un PCFG puede alterar este requisito, como ocurre 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 homólogos en bases de datos, anotación y clasificación de ARN. Mediante los CM es posible construir perfiles de ARN basados ​​en PCFG donde los ARN relacionados pueden representarse mediante una estructura secundaria consensuada. [ 11 ] [ 12 ] El paquete de análisis de ARN Infernal utiliza dichos perfiles en la inferencia de alineamientos de ARN. [ 34 ] La base de datos Rfam también utiliza CM para clasificar los 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 consensuada. Un CM permite inserciones/deleciones de longitud ilimitada en el alineamiento. Los terminales constituyen estados en el CM y la probabilidad de transición entre los estados es 1 si no se consideran inserciones/deleciones. [ 1 ] Las gramáticas en un CM son las siguientes:

PAG→aWb{\displaystyle P\to aWb}
Probabilidades de interacciones por pares entre 16 pares posibles
L→aW{\displaystyle L\to aW}
probabilidades de generar 4 posibles bases simples en el lado izquierdo
R→Wa{\displaystyle R\to Wa}
Probabilidades de generar 4 posibles bases simples a la derecha
B→SS{\displaystyle B\to SS}
bifurcación con una probabilidad de 1
S→W{\displaystyle S\to W}
comenzar con una probabilidad de 1
mi→ϵ{\displaystyle E\to \epsilon }
terminar 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 que no son de inserción. Para permitir la inserción de más de una base, los estados de inserción se conectan a sí mismos. [ 1 ]

Para puntuar un modelo CM se utilizan los algoritmos de dentro-fuera. Los CM utilizan una implementación ligeramente diferente de CYK. Puntuaciones de emisión de log-odds para el árbol de análisis óptimo -registro⁡mi^{\displaystyle \log {\sombrero {e}}}- se calculan a partir de los estados emisoresPAG, L, R{\displaystyle P,~L,~R}. Dado que estas puntuaciones son función de la longitud de la secuencia, una medida más discriminatoria para recuperar una puntuación de probabilidad de árbol de análisis óptimo-registro⁡PAG(incógnita,π^|θ){\displaystyle \log {\text{P}}(x,{\hat {\pi }}|\theta )}- se alcanza limitando la longitud máxima de la secuencia a alinear y calculando las probabilidades logarítmicas relativas a 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 deO(METROaD+METRObD2){\displaystyle O(M_{a}D+M_{b}D^{2})}. [ 1 ]

Ejemplo: Utilizar información evolutiva para guiar la predicción de estructuras.

El algoritmo KH-99 de Knudsen y Hein sienta las bases del enfoque Pfold para predecir la estructura secundaria del ARN. [ 20 ] En este enfoque, la parametrización requiere información de la historia evolutiva derivada de un árbol de alineación, además de probabilidades de columnas y mutaciones. Las probabilidades gramaticales se observan a partir de un conjunto de datos de entrenamiento.

Estimar las probabilidades de columna para bases emparejadas y no emparejadas.

En una alineación estructural, las probabilidades de las columnas de bases no apareadas y las columnas de bases apareadas son independientes de otras columnas. Al contar las bases en posiciones de base simple y posiciones apareadas, se obtienen las frecuencias de bases en bucles y tallos. Para el par de bases X e Y, una ocurrencia deincógnitaY{\displaystyle XY}también se cuenta como una ocurrencia deYincógnita{\displaystyle YX}. Pares de bases idénticos comoincógnitaincógnita{\displaystyle XX}se cuentan dos veces.

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

Al emparejar secuencias de todas las maneras posibles, se estiman las tasas de mutación generales. Para recuperar mutaciones plausibles, se debe usar un umbral de identidad de secuencia para que la comparación se realice entre secuencias similares. Este enfoque utiliza un umbral de identidad del 85 % entre las secuencias emparejadas. Primero, se cuentan las diferencias de posiciones de una sola base (excepto en columnas con huecos) entre pares de secuencias, de modo que si la misma posición en dos secuencias tiene bases diferentes X, Y, el contador de la diferencia se incrementa para cada secuencia.

mientrasincógnita≠Y{\displaystyle X\neq Y}doXY+1{\displaystyle C_{\text{XY}}+1}primer par de secuenciasdoYX+1{\displaystyle C_{\text{YX}}+1}segundo par de secuencias
Calcular las tasas de mutación.rXY={\displaystyle r_{\text{XY}}=}mutación de la base X a la base Y=K doXYPAGincógnitaPAGs{\displaystyle ={\frac {K~C_{\text{XY}}}{P_{x}P_{s}}}}Dejar rXX={\displaystyle r_{\text{XX}}=}el negativo de la tasa de mutación de X a otras bases=−∑rXY{\displaystyle =-\sum r_{\text{XY}}}PAGs={\displaystyle P_{s}=}la probabilidad de que la base no esté emparejada.

Para bases no apareadas se utiliza una matriz de tasas de mutación de 4 x 4 que satisface que el flujo de mutación de X a Y es reversible: [ 35 ]

PAGincógnitarincógnitaY=PAGYrYincógnita{\displaystyle PX^{r}XY=PY^{r}YX}

Para pares de bases se genera de manera similar una matriz de distribución de tasas de 16 x 16. [ 36 ] [ 37 ] El PCFG se utiliza para predecir la distribución de probabilidad a priori de la estructura, mientras que las probabilidades a posteriori se estiman mediante el algoritmo inside-outside y la estructura más probable se encuentra mediante el algoritmo CYK. [ 20 ]

Estimar las probabilidades de alineación

Después de calcular las probabilidades previas de las columnas, la probabilidad de alineación se estima sumando sobre todas las posibles estructuras secundarias. Cualquier columna C en una estructura secundariaσ{\displaystyle \sigma }para una secuencia D de longitud l tal queD=(do1, do2,...dol){\displaystyle D=(C_{1},~C_{2},...C_{l})}se puede puntuar con respecto al árbol de alineación T y al modelo mutacional M. La distribución a priori dada por el PCFG esPAG(σ|METRO){\displaystyle P(\sigma |M)}El árbol filogenético , T, se puede calcular a partir del modelo mediante estimación de máxima verosimilitud . Cabe señalar que los huecos se tratan como bases desconocidas y la suma se puede realizar mediante programación dinámica . [ 38 ]

PAG(D|T,METRO){\displaystyle P(D|T,M)}
=∑PAG(D,σ|T,METRO){\displaystyle =\sum P(D,\sigma |T,M)}
=∑PAG(D|σ,T,METRO)PAG(σ|T,METRO){\displaystyle =\sum P(D|\sigma ,T,M)P(\sigma |T,M)}
=∑PAG(D|σ,T,METRO)PAG(σ|METRO){\displaystyle =\sum P(D|\sigma ,T,M)P(\sigma |M)}
Asigne probabilidades de producción a cada regla de la gramática.

A cada estructura de la gramática se le asignan probabilidades de producción derivadas de las estructuras del conjunto de datos de entrenamiento. Estas probabilidades previas ponderan la precisión de las predicciones. [ 21 ] [ 32 ] [ 33 ] El número de veces que se utiliza cada regla depende de las observaciones del conjunto de datos de entrenamiento para esa característica gramatical en particular. Estas probabilidades se escriben entre paréntesis en el formalismo gramatical y cada regla tendrá un total del 100 %. [ 20 ] Por ejemplo:

S→LS(80%)|L(20%){\displaystyle S\to LS(80\%)|L(20\%)}
L→s(70%)|dFd(30%){\displaystyle L\to s(70\%)|dFd(30\%)}
F→dFd(60.4%)|LS(39.6%){\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 maximizandoPAG(σ|D,T,METRO){\displaystyle P(\sigma |D,T,M)}mediante el algoritmo CYK. La estructura con el mayor número de predicciones correctas se reporta como la estructura de consenso. [ 20 ]

σMETROAPAG=arg⁡máximoσPAG(D|σ,TMETROL,METRO)PAG(σ|METRO){\displaystyle \sigma _{MAP}=\arg {\underset {\sigma }{\max }}P(D|\sigma ,T^{M}L,M)P(\sigma |M)}
Pfold mejoras en el algoritmo KH-99

Se busca que los enfoques basados ​​en PCFG sean escalables y suficientemente generales. El compromiso entre velocidad y precisión debe ser mínimo. 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 tratan como 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 el método de unión de vecinos , y no mediante máxima verosimilitud a través de la gramática PCFG. Solo las longitudes de las ramas se ajustan a las estimaciones de máxima verosimilitud.
  • Pfold parte de la premisa de que todas las secuencias tienen la misma estructura. El umbral de identidad de secuencia y la posibilidad de que un 1 % de probabilidad de que cualquier nucleótido se convierta en otro limitan el deterioro del rendimiento debido a errores de alineación.

Análisis de la secuencia de proteínas

Si bien las 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, incluidas relaciones anidadas y cruzadas, claramente superan las capacidades de cualquier CFG. [ 39 ] Aun así, el desarrollo de PCFG permite expresar algunas de esas dependencias y proporciona la capacidad de modelar una gama más amplia de patrones de proteínas.

Véase también

Referencias

  1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 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 sin lexicalizar" (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" . Information and 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. 1 2 3 4 5 6 7 Dowell R. y Eddy S. (2004). "Evaluación de varias gramáticas libres de contexto estocásticas ligeras 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. 1 2 Smith, Noah A.; Johnson, Mark (2007). "Las gramáticas libres de contexto ponderadas y probabilísticas son igualmente expresivas" (PDF) . Lingüística Computacional . 33 (4): 477. doi : 10.1162/coli.2007.33.4.477 . S2CID 1405777 . 
  8. ↑ Katsirelos, George; Narodytska, Nina; Walsh, Toby (2008). "The Weighted CFG Constraint" . Integración de técnicas de IA e investigación operativa en programación con restricciones para problemas de optimización combinatoria . Lecture Notes in Computer Science. Vol. 5015. pp. 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 las gramáticas probabilísticas libres de contexto" (PDF) . Lingüística Computacional . 25 (1): 131–160 . Archivado del original (PDF) el 21 de agosto de 2010.
  11. 1 2 3 4 5 6 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. 1 2 3 4 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 la Biología Molecular, AAAI Press : 136–144 . Archivado del original (PDF) el 4 de diciembre de 2015. Recuperado el 3 de agosto de 2017 .
  14. ↑ Lefebvre, F (1995). "Un algoritmo de análisis optimizado 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 la Biología Molecular (PDF) . AAAI Press. págs. 222–230 . 
  15. ↑ Lefebvre, F. (1996). «Una unificación basada en gramáticas de varios algoritmos de alineación y plegado». En States, DJ; Agarwal, P.; Gaasterlan, T.; Hunter, L.; Smith RF (eds.). Actas de la Cuarta Conferencia Internacional sobre Sistemas Inteligentes para la 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". Biopolymers . 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 la energía libre y el 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 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. 1 2 3 4 5 6 7 8 B. Knudsen y J. Hein. (2003). "Pfold: predicción de la estructura secundaria del ARN mediante gramáticas estocásticas libres de contexto" . Nucleic Acids Research . 31 (13): 3423– 3428. doi : 10.1093/nar/gkg614 . PMC 169020. PMID 12824339 .  
  21. 1 2 3 Knudsen B.; Hein J. (1999). "Predicción de la estructura secundaria del ARN mediante gramáticas estocásticas libres de contexto e historia evolutiva" . Bioinformatics . 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 . págs. 163–174 . doi : 10.1142/9789812799623_0016 . ISBN  978-981-02-4777-5. PMID 11928472 . {{cite book}}: |journal=ignorado ( ayuda )
  24. 1 2 P. P. 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 versió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" . Bioinformatics . 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 involucrados en procesos reguladores postranscripcionales" . Proc. Natl. Acad. 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". Combinatorial Pattern Matching . Lecture Notes in Computer Science. Vol. 1848. En Actas del 11.º Simposio Anual sobre Combinatorial Pattern Matching 1848. Editado por: Giancarlo R., Sankoff D. Montreal, Canadá: Springer-Verlag, Berlín. pp. 46–59 . doi : 10.1007/3-540-45123-4_6 . ISBN   978-3-540-67633-1. S2CID 17088251 . 
  32. 1 2 3 Lari K.; Young SJ (1990). "La estimación de gramáticas estocásticas libres de contexto utilizando el algoritmo interior-exterior". Computer Speech and Language . 4 : 35– 56. doi : 10.1016/0885-2308(90)90022-X .
  33. 1 2 3 Lari K.; Young SJ (1991). "Aplicaciones de gramáticas estocásticas libres de contexto utilizando el algoritmo interior-exterior". Computer Speech and Language . 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" . Bioinformatics . 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. Sociedad Matemática Americana . 17 : 57–86 .
  36. ↑ Muse SV (1995). " Análisis evolutivos de secuencias de ADN sujetas a restricciones de estructura secundaria" . Genetics . 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 del habla" . The Journal of the Acoustical Society of America . 65 (S1): S132. Bibcode : 1979ASAJ...65Q.132B . doi : 10.1121/1.2017061 .
  39. 1 2 Searls, D (2013). "Revisión: Una introducción a la lingüística macromolecular". Biopolymers . 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" . Breve Bioinformación . 3 (3): 265– 274. doi : 10.1093/bib/3.3.265 . PMID 12230035 . 
  • Base de datos Rfam
  • Infernal
  • El analizador sintáctico de Stanford: un analizador sintáctico estadístico
  • pyStatParser
  • QSMM: analizadores sintácticos adaptativos de arriba hacia abajo y de abajo hacia arriba para la inducción de PCFG mediante plantillas.