Gramática probabilística libre de contexto - Probabilistic context-free grammar

La teoría de la gramática para modelar cadenas de símbolos se originó a partir del trabajo en lingüística computacional con el objetivo de comprender la estructura de los lenguajes naturales . 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 su introducción en la lingüística computacional .

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 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á limitada por el contexto de su conjunto de datos de entrenamiento.

Los PCFG tienen aplicación en áreas tan diversas como el procesamiento del lenguaje natural para el estudio de la estructura de 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 varios requisitos de tiempo y memoria.

Definiciones

Derivación: El proceso de generación recursiva de cadenas 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 con una secuencia.

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

Definicion formal

Similar a un CFG , una gramática $G$ probabilística libre de contexto se puede definir por un quíntuplo:

{\ 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 modelos ocultos de Markov

Los modelos PCFG amplían las gramáticas libres de contexto de la misma forma que los modelos ocultos de Markov amplían 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, basándose en algún PCFG. Esto es equivalente a la probabilidad de que el PCFG genere la secuencia e intuitivamente es una medida de cuán consistente es la secuencia con la gramática dada. El algoritmo Inside-Outside se utiliza en la parametrización del modelo para estimar las frecuencias previas observadas de 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 por el 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. Las reglas son absolutas y tienen una representación de sintaxis 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. Un ejemplo de gramática: ${\ Displaystyle \ left \ {a, b \ right \}}$ ${\ Displaystyle \ epsilon}$

{\ Displaystyle S \ a aS, S \ a bS, S \ a \ epsilon}

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

{\ 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 ya sea $una$ o $b$ o ". Su derivación es: ${\ Displaystyle \ epsilon}$

{\ Displaystyle S \ Rightarrow aS \ Rightarrow abS \ Rightarrow abbS \ Rightarrow abb}

La gramática ambigua puede resultar en un análisis ambiguo si se aplica en homógrafos, ya que la misma secuencia de palabras puede tener más de una interpretación. Las frases de juego de palabras como el titular del periódico "El jefe iraquí busca armas" son un ejemplo de análisis ambiguo.

Una estrategia para lidiar con análisis ambiguos (que se originaron con gramáticos ya en Pāṇini ) es agregar aún más reglas, o priorizarlas para que una regla tenga prioridad sobre otras. Sin embargo, esto tiene el inconveniente de que las reglas proliferan, a menudo hasta el punto en que se vuelven difíciles de administrar. Otra dificultad es la sobregeneración, donde también se generan estructuras sin licencia.

Las gramáticas probabilísticas eluden estos problemas al clasificar varias producciones en pesos de frecuencia, lo que da como resultado una interpretación "más probable" (el ganador se lo lleva todo). A medida que los patrones de uso se alteran en los cambios diacrónicos , estas reglas probabilísticas se pueden volver a aprender, actualizando así la gramática.

Asignar probabilidad a las reglas de producción hace un PCFG. Estas probabilidades se informan observando 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 hechas a mano. Los CFG, cuando se contrastan 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 secuencia.

Gramática ponderada sin 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 (o la suma) de todos los pesos de las reglas del árbol. Cada peso de regla se incluye con la frecuencia con la que se usa la regla en el árbol. Un caso especial de WCFG son los PCFG, donde los pesos son ( logaritmos de) probabilidades .

Se puede usar una versión extendida del algoritmo CYK para encontrar la derivación "más liviana" (de menor peso) de una cadena dada alguna 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 .

Aplicaciones

Predicción de la estructura del ARN

La minimización de energía y PCFG proporcionan formas de predecir la estructura secundaria del ARN con un rendimiento comparable. Sin embargo, la predicción de la estructura por los PCFG se puntúa de forma probabilística en lugar de mediante el cálculo de energía libre mínima. Los parámetros del modelo PCFG se derivan directamente de frecuencias de diferentes características observadas en bases de datos de estructuras de ARN en lugar de por determinación experimental como es el caso de los métodos de minimización de energía.

Los tipos de varias 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 se pueden modelar. Los PCFG amplían el 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 sobre su secuencia primaria; La predicción de la estructura del ARN se puede guiar combinando información evolutiva del análisis de secuencia comparativa con conocimiento biofísico sobre la plausibilidad de una estructura basada en tales probabilidades. Además, los resultados de la búsqueda de homólogos estructurales que utilizan reglas de PCFG se puntúan de acuerdo con las probabilidades de derivación de PCFG. Por lo tanto, la construcción de gramática para modelar el comportamiento de los pares de bases y las regiones monocatenarias comienza con la exploración de las características de la alineación estructural de secuencias múltiples de ARN relacionados.

{\ 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 lejanos de la terminal se deriva primero. Así que una cadena como se deriva por primera generación de la distal $un$ 's en ambos lados antes de pasar hacia el interior: ${\ displaystyle aabaabaa}$

{\ Displaystyle S \ Rightarrow aSa \ Rightarrow aaSaa \ Rightarrow aabSbaa \ Rightarrow aabaabaa}

La extensibilidad de un modelo PCFG permite restringir la predicción de estructuras al incorporar expectativas sobre diferentes características de un ARN. Tal expectativa puede reflejar, por ejemplo, la propensión a asumir una determinada estructura por parte de un ARN. Sin embargo, la incorporación de demasiada información puede aumentar el espacio de PCFG y la complejidad de la memoria y es deseable que un modelo basado en PCFG sea lo más simple posible.

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 gramaticales es . Las puntuaciones para cada residuo emparejado y no emparejado 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 basadas en los umbrales de puntuación. ${\ 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 optimizando las probabilidades conjuntas de la estructura sobre MSA.
Modelado de la covariación de pares de bases para detectar homología en búsquedas en bases de datos.
plegado y alineación simultáneos por parejas.

Existen diferentes implementaciones de estos enfoques. Por ejemplo, Pfold se usa en la predicción de estructuras secundarias a partir de un grupo de secuencias de ARN relacionadas, los modelos de covarianza se usan en la búsqueda de bases de datos para secuencias homólogas y anotación y clasificación de ARN, RNApromo, CMFinder y TEISER se usan para encontrar motivos estructurales estables en ARN.

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 estructuras útil basado en PCFG debe mantener la simplicidad sin comprometer mucho la precisión de la predicción. Un modelo demasiado complejo de excelente rendimiento en una sola secuencia puede no escalar. Un modelo basado en gramática debería poder:

Encuentre la alineación óptima entre una secuencia y el PCFG.
Califique la probabilidad de las estructuras para la secuencia y subsecuencias.
Parametrice el modelo entrenando en secuencias / estructuras.
Encuentre el árbol de análisis gramatical óptimo (algoritmo CYK).
Compruebe la gramática ambigua (algoritmo Conditional Inside).

El resultado de varios árboles de análisis por gramática denota ambigüedad gramatical. Esto puede resultar ú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 hay una y solo una correspondencia entre el árbol de análisis sintáctico y la estructura secundaria.

Se pueden distinguir dos tipos de ambigüedades. Analizar la ambigüedad del árbol y la ambigüedad estructural. La ambigüedad estructural no afecta los enfoques termodinámicos ya que la selección de estructura óptima siempre se basa en las puntuaciones de energía libre más bajas. La ambigüedad del árbol de análisis se refiere a la existencia de varios á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 sintáctico posibles y luego encontrando el óptimo. En el caso de ambigüedad estructural, varios árboles de análisis describen la misma estructura secundaria. Esto oscurece la decisión del algoritmo CYK de encontrar una estructura óptima, ya que la correspondencia entre el árbol de análisis sintáctico y la estructura no es única. La ambigüedad gramatical se puede verificar mediante el algoritmo de interior condicional.

Construyendo un modelo PCFG

Una gramática libre de contexto probabilística 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 de forma recursiva hasta que solo quedan residuos terminales.

Un no terminal inicial produce bucles. El resto de la gramática procede con el parámetro que decidir si un bucle es un comienzo de un tallo o una región monocatenaria $s$ y el parámetro que produce bases apareadas. ${\ Displaystyle \ mathbf {\ mathit {S}}}$ ${\ Displaystyle \ mathbf {\ mathit {L}}}$ ${\ Displaystyle \ mathbf {\ mathit {F}}}$

El formalismo de este simple PCFG se ve así:

{\ Displaystyle {\ mathit {S \ a LS | L}}}

{\ Displaystyle {\ mathit {L \ to s | dFd}}}

{\ Displaystyle {\ mathit {F \ to dFd | LS}}}

La aplicación de PCFG en la predicción de estructuras es un proceso de varios pasos. Además, el propio PCFG se puede incorporar en modelos probabilísticos que consideran la historia evolutiva del ARN o 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.

Un resumen de los pasos generales para utilizar PCFG en varios escenarios:

Genere reglas de producción para las secuencias.
Compruebe la ambigüedad.
Genere de forma recursiva árboles de análisis de las posibles estructuras utilizando la gramática.
Clasifique y califique los árboles de análisis sintáctico según la secuencia más plausible.

Algoritmos

Existen varios algoritmos que tratan aspectos de los modelos probabilísticos basados en PCFG en la predicción de la estructura del ARN. Por ejemplo, el algoritmo de adentro hacia afuera y el algoritmo CYK. El algoritmo de adentro hacia afuera 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, basándose en algún PCFG. La parte interior puntúa los subárboles de un árbol de análisis y, por lo tanto, las probabilidades de subsecuencias dadas una PCFG. La parte exterior puntúa la probabilidad del árbol de análisis completo para una secuencia completa. CYK modifica la puntuación de adentro hacia afuera. Tenga en cuenta que el término 'algoritmo CYK' describe la variante CYK del algoritmo interno que encuentra un árbol de análisis óptimo para una secuencia que utiliza un PCFG. Amplía el algoritmo CYK real utilizado en CFG no probabilísticos.

El algoritmo interno calcula las probabilidades de todo un subárbol de análisis con raíz en 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 volver a estimar el algoritmo PCFG encontrando el número esperado de veces que se usa un estado en una derivación sumando todos los productos de $α$ y $β$ divididos por la probabilidad de 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 maximización de expectativas que utiliza los valores de $α$ y $β$ . El algoritmo CYK calcula para encontrar el árbol de análisis y los rendimientos más probables . ${\ 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 la memoria y el tiempo para los algoritmos PCFG generales en las predicciones de la estructura del ARN son y respectivamente. La restricción de un PCFG puede alterar este requisito, como es el caso de los métodos de búsqueda de 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, anotaciones y clasificación de ARN. A través de CM es posible construir perfiles de ARN basados en PCFG donde los ARN relacionados se pueden representar mediante una estructura secundaria de consenso. El paquete de análisis de ARN Infernal utiliza tales perfiles en inferencia de alineaciones de ARN. La base de datos Rfam también utiliza CM para clasificar los ARN en familias en función de su estructura y la información de secuencia.

Los CM se diseñan a partir de una estructura de ARN de consenso. Un CM permite indeles de longitud ilimitada en la alineación. Los terminales constituyen estados en el CM y las probabilidades de transición entre los estados es 1 si no se consideran indeles. 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 simples a la izquierda
${\ Displaystyle R \ to Wa}$: probabilidades de generar 4 posibles bases únicas a la derecha
${\ Displaystyle B \ to SS}$: bifurcación con una probabilidad de 1
${\ Displaystyle S \ a W}$: comenzar con una probabilidad de 1
${\ 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 los nodos actuales se conectan a todos los estados de inserción y los estados de los nodos subsiguientes se conectan a los 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í.

Para puntuar un modelo CM se utilizan los algoritmos de adentro hacia afuera. Los CM utilizan una implementación ligeramente diferente de CYK. Los puntajes de emisión de log-odds para el árbol de análisis óptimo - - se calculan a partir de los estados emisores . Dado que estos puntajes son una función de la longitud de la secuencia, se alcanza una medida más discriminativa para recuperar un puntaje de probabilidad de árbol de análisis sintáctico óptimo limitando la longitud máxima de la secuencia a alinear y calculando las probabilidades de registro relativas a 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 . ${\ 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 guiar la predicción de estructuras

El algoritmo KH-99 de Knudsen y Hein sienta las bases del enfoque de Pfold para predecir la estructura secundaria del ARN. En este enfoque, la parametrización requiere información de la historia evolutiva derivada de un árbol de alineación, además de las 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 apareadas y no apareadas

En una alineación estructural, las probabilidades de las columnas de bases no apareadas y las columnas de bases pareadas son independientes de otras columnas. Contando bases en posiciones de base única y posiciones pareadas, se obtienen las frecuencias de bases en bucles y tallos. Para el par de bases $X$ e $Y,$ una aparición de también se cuenta como una aparición de . Los pares de bases idénticos como, por ejemplo, se cuentan dos veces. ${\ Displaystyle XY}$ ${\ Displaystyle YX}$ ${\ displaystyle XX}$

Calcule las tasas de mutación para bases emparejadas y no emparejadas

Mediante el apareamiento de secuencias de todas las formas posibles se estiman las tasas de mutación globales. Para recuperar mutaciones plausibles, debe usarse un umbral de identidad de secuencia de modo que la comparación sea entre secuencias similares. Este enfoque utiliza un umbral de identidad del 85% entre secuencias de emparejamiento. Las diferencias de las primeras posiciones de una sola base -excepto por las columnas con huecos- entre los pares de secuencias se cuentan de tal manera que si la misma posición en dos secuencias tiene diferentes bases $X, Y,$ el recuento de la diferencia se incrementa para cada secuencia.

while  $X\neq Y$ 
                $C_{\text{XY}}+1$  first sequence  pair
                $C_{\text{YX}}+1$  second sequence pair

Calculate mutation rates.
               Let   $r_{\text{XY}}=$  mutation of base X to base Y  $={\frac {K~C_{\text{XY}}}{P_{x}P_{s}}}$ 
               Let   $r_{\text{XX}}=$  the negative of the rate of X mutation to other bases  $=-\sum r_{\text{XY}}$ 
                $P_{s}=$  the probability that the base is not paired.

Para bases no apareadas, se usa una matriz de tasa de mutación de 4 X 4 que satisface que el flujo de mutación de X a Y sea reversible:

{\ Displaystyle PX ^ {r} XY = PY ^ {r} YX}

Para los pares de bases, se genera de manera similar una matriz de distribución de tasas de 16 X 16. El PCFG se utiliza para predecir la distribución de probabilidad previa de la estructura, mientras que las probabilidades posteriores se estiman mediante el algoritmo interior-exterior y la estructura más probable se encuentra mediante el algoritmo CYK.

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 posibles estructuras secundarias. Cualquier columna $C$ en una estructura secundaria para una secuencia $D$ de longitud $l$ de tal manera que puede ser anotó 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 la estimación de máxima verosimilitud. Tenga en cuenta que los huecos se tratan como bases desconocidas y la suma se puede realizar mediante programación dinámica . ${\ 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 creadas a partir de las estructuras del conjunto de datos de entrenamiento. Estas probabilidades previas dan peso a la precisión de las predicciones. La cantidad de veces que se usa cada regla depende de las observaciones del conjunto de datos de entrenamiento para esa característica gramatical en particular. Estas probabilidades están escritas entre paréntesis en el formalismo gramatical y cada regla tendrá un total del 100%. Por ejemplo:

{\ Displaystyle S \ a LS (80 \%) | L (20 \%)}

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

{\ Displaystyle F \ a dFd (60,4 \%) | LS (39,6 \%)}

Predecir la probabilidad de la estructura

Dadas las frecuencias de alineación anteriores de los datos, la estructura más probable del conjunto predicho por la gramática se puede calcular maximizando a través del algoritmo CYK. La estructura con el mayor número previsto de predicciones correctas se informa como estructura de consenso. ${\ Displaystyle P (\ sigma | D, T, M)}$

{\ 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 desea que los enfoques basados en PCFG sean escalables y lo suficientemente generales. Comprometer la velocidad para la precisión debe ser lo más mínimo posible. Pfold aborda las limitaciones del algoritmo KH-99 con respecto a escalabilidad, brechas, velocidad y precisión.

En Pfold, los huecos se tratan como desconocidos. En este sentido, la probabilidad de una columna con espacios es igual a la de una sin espacios.
En Pfold, el árbol $T$ se calcula antes de la predicción de la estructura a través de la unión de vecinos y no por 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.
Una suposición de Pfold es que todas las secuencias tienen la misma estructura. El umbral de identidad de secuencia y permite una probabilidad del 1% de que cualquier nucleótido se convierta en otro límite del deterioro del rendimiento debido a errores de alineación.

Análisis de la secuencia de proteínas

Mientras que 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. 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. Dado que las estructuras de proteínas suelen mostrar dependencias de orden superior, incluidas las relaciones anidadas y cruzadas, superan claramente las capacidades de cualquier CFG. Aún así, el desarrollo de PCFG permite expresar algunas de esas dependencias y proporcionar la capacidad de modelar una gama más amplia de patrones de proteínas.

Uno de los principales obstáculos para inferir una gramática de proteínas es el tamaño del alfabeto que debería codificar los 20 aminoácidos diferentes . Se ha propuesto abordar esto mediante el uso de propiedades físico-químicas de los aminoácidos para reducir significativamente el número de posibles combinaciones de símbolos del lado derecho en las reglas de producción: se utilizan 3 niveles de una propiedad cuantitativa en lugar de los 20 tipos de aminoácidos , por ejemplo, pequeños , volumen de van der Waals mediano o grande . Sobre la base de tal esquema, se han producido PCFG para generar descriptores de sitio de unión y de sitio de contacto hélice-hélice. Una característica importante de esas gramáticas es que el análisis de sus reglas y árboles de análisis puede proporcionar información biológicamente significativa.

Languages

In other projects