Gramática probabilística libre de contexto

La teoría gramatical 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 (PCFGs) se han aplicado en modelado probabilístico de estructuras de ARN casi 40 años después de su introducción en la lingüística computacional.

Los PCFG amplían las gramáticas independientes del contexto de forma similar a como los modelos ocultos de Markov amplían las gramáticas normales. A cada producción se le asigna una probabilidad. La probabilidad de una derivación (parse) 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 tienen aplicación en áreas tan diversas como el procesamiento del lenguaje natural para 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 tiene que 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 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 con una secuencia.

Un ejemplo de un analizador 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 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.

Definición formal

Al igual que un CFG, una gramática libre de contexto probabilística G se puede definir mediante un quíntuple:

G=()M,T,R,S,P){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 reglas de producción

Relación con modelos ocultos de Markov

Los modelos PCFG amplían las gramáticas independientes del contexto de la misma manera que los modelos ocultos de Markov amplían las gramáticas normales.

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 base a algún PCFG. Esto es equivalente a la probabilidad de que el PCFG genere la secuencia, y es intuitivamente una medida de qué tan 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 a partir 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 idiomas naturales. Las reglas son absolutas y tienen una representación de sintaxis típica conocida como la forma Backus-Naur. Las reglas de producción consisten en terminal {}a,b}{displaystyle left{a,bright} y no S símbolos y un blanco ε ε {displaystyle epsilon } también se puede utilizar como punto final. En las reglas de producción de CFG y PCFG el lado izquierdo tiene sólo un no-terminal, mientras que el lado derecho puede ser cualquier cadena de terminales o no-terminales. En los nulls PCFG están excluidos. Un ejemplo de gramática:

S→ → aS,S→ → bS,S→ → ε ε {displaystyle Sto aS,Sto bS,Sto epsilon }

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

S→ → aSSilenciobSSilencioε ε {displaystyle Sto aS habitbS habitepsilon }

Los terminales en una gramática son palabras y a través de las reglas de gramática un símbolo no-terminal se transforma en una cadena de terminales y/o no-terminales. La gramática anterior se lee como "comienzo 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 SRightarrow aSRightarrow abSRightarrow abbSRightarrow abb}

La gramática ambigua puede resultar en 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. Juegos de palabras como el titular del periódico "Cabeza iraquí busca armas" son un ejemplo de análisis ambiguos.

Una estrategia para lidiar con los análisis sintácticos ambiguos (que se originaron con los gramáticos desde Pāṇini) es agregar aún más reglas o priorizarlas para que una regla prevalezca sobre las demás. Esto, sin embargo, 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 ponderaciones de frecuencia, lo que da como resultado un "más probable" interpretación (el ganador se lo lleva todo). Como los patrones de uso se modifican en 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 genera un PCFG. Estas probabilidades se informan mediante 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 en las que las probabilidades se estiman a partir de datos normalmente superan 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 una relación secuencia-estructura, carecen de las métricas de puntuación que revelan un potencial estructural de secuencia.

Gramática ponderada 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 (o la suma) de todos los pesos de las reglas del árbol. El peso de cada 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 el "más ligero" Derivación (de menor peso) de una cadena dado algún WCFG.

When the tree weight is the product of the rule weights, WAGs and PCFGs can express the same set of probability distributions.

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 parte de los PCFG se puntúa de forma 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 en lugar de por experimentos. determinación como es el caso de los métodos de minimización de energía.

Los tipos de diversas estructuras que se pueden modelar mediante un PCFG incluyen interacciones de largo alcance, estructuras 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 máxima probabilidad de la gramática implica una estructura de máxima probabilidad. Dado que los ARN conservan sus estructuras sobre su secuencia primaria; La predicción de la estructura del ARN puede guiarse mediante la combinación de 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 la búsqueda de homólogos estructurales que utilizan reglas PCFG se puntúan de acuerdo con las probabilidades de derivación de PCFG. Por lo tanto, la construcción de la 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 de secuencias múltiples estructurales de los ARN relacionados.

S→ → aSaSilenciobSbSilencioaaSilenciobb{displaystyle Sto aSa tuberculosis

La gramática anterior genera una cadena de forma externa, que es el punto base en los extremos más lejanos de la terminal se deriva primero. Así que una cuerda como aabaabaa{displaystyle aabaa} se deriva por primera generación del distal a's en ambos lados antes de moverse hacia adentro:

S⇒ ⇒ aSa⇒ ⇒ aaSaa⇒ ⇒ aabSbaa⇒ ⇒ aabaabaa{displaystyle SRightarrow aSaRightarrow aaSaaRightarrow aabSbaaRightarrow 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 PCFG y la complejidad de la memoria y es deseable que un modelo basado en PCFG sea lo más simple posible.

Cada cadena posible x una gramática genera se asigna un peso de probabilidad P()xSilencioSilencio Silencio ){displaystyle P(x habittheta)} dado el modelo PCFG Silencio Silencio {displaystyle theta }. Se sigue que la suma de todas las probabilidades a todas las producciones gramáticas posibles es .. xP()xSilencioSilencio Silencio )=1{displaystyle sum _{text{x}P(x sometidatheta)=1}. Las puntuaciones para cada residuo emparejado y no pintado explican la probabilidad de formar estructuras secundarias. Las reglas de producción también permiten la puntuación de longitudes de lazo así como el orden de apilación de pares base por lo tanto es posible explorar la gama de todas las generaciones posibles, incluyendo estructuras suboptimales de la gramática y aceptar o rechazar estructuras basadas en umbrales de puntuación.

Implementaciones

Las implementaciones de estructuras secundarias de ARN basadas en enfoques PCFG se pueden utilizar en:

• Encontrar la estructura de consenso mediante la optimización de las probabilidades de estructura conjunta sobre el MSA.
• Modeling base-pair covariation to detecting homology in database searches.
• doble plegado y alineación simultánea.

Existen diferentes implementaciones de estos enfoques. Por ejemplo, Pfold se usa en la predicción de estructuras secundarias de un grupo de secuencias de ARN relacionadas, los modelos de covarianza se usan para buscar bases de datos de secuencias homólogas y la anotación y clasificación de ARN, RNApromo, CMFinder y TEISER se usan para encontrar motivos estructurales estables en los 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 estructura útil basado en PCFG tiene que mantener la simplicidad sin comprometer demasiado 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 la gramática debe ser capaz de:

• Encuentra la alineación óptima entre una secuencia y el PCFG.
• Marcar la probabilidad de las estructuras para la secuencia y subsecuencias.
• Parámetro del modelo adiestrando secuencias/estructuras.
• Encontrar el árbol de pares de gramática óptima (algoritmo de CYK).
• Comprobar la gramática ambigua (algoritmo interior convencional).

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 sólo una correspondencia entre el árbol de análisis 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 la 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 múltiples árboles de análisis por secuencia. Tal 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. En el caso de ambigüedad estructural, varios árboles de análisis sintáctico 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 y la estructura no es única. La ambigüedad gramatical puede verificarse mediante el algoritmo condicional interno.

Construyendo un modelo PCFG

Una gramática libre de contexto probabilístico 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.

A starting non-terminal S{displaystyle mathbf {Mathit {S} produce bucles. El resto de la gramática procede con parámetro L{displaystyle mathbf {Mathit {L} que decide si un bucle es un comienzo de un tallo o una sola región varada s y parámetro F{displaystyle mathbf {Mathit {F} que produce bases emparejadas.

El formalismo de este simple PCFG parece:

S→ → LSSilencioL{displaystyle {Mathit {Sto LS habitL}}

L→ → sSilenciodFd{displaystyle {Mathit {Lto s habitdFd}}

F→ → dFdSilencioLS{displaystyle {Mathit {Fto dFd habitLS}}

La aplicación de 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 consideren la historia evolutiva del ARN o busquen secuencias homólogas en bases de datos. En un contexto de historia evolutiva, la inclusión de distribuciones previas de estructuras de ARN de una alineación estructural en las reglas de producción del PCFG facilita una buena precisión de predicción.

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

• Genera reglas de producción para las secuencias.
• Comprueba la ambigüedad.
• Generar árboles pares de las estructuras posibles utilizando la gramática.
• Arranque y marque los árboles parse para la secuencia más plausible.

Algoritmos

Existen varios algoritmos que se ocupan de los 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, en base a algún PCFG. La parte interior puntúa los subárboles de un árbol de análisis y, por lo tanto, subsecuencia las probabilidades dado un PCFG. La parte exterior puntúa la probabilidad del árbol de análisis completo para una secuencia completa. CYK modifica la puntuación interior-exterior. 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 usando un PCFG. Extiende el algoritmo CYK real utilizado en los CFG no probabilísticos.

El algoritmo interior calcula α α ()i,j,v){displaystyle alpha (i,j,v)} probabilidades para todos i,j,v{displaystyle i,j,v} de un subárbol de parse Wv{displaystyle W_{v} para subsequence xi,...,xj{displaystyle x_{i},...,x_{j}. El algoritmo exterior calcula β β ()i,j,v){displaystyle beta (i,j,v)} probabilidades de un árbol parse completo para secuencia x de raíz excluyendo el cálculo xi,...,xj{displaystyle x_{i},...,x_{j}. Las variables α y β refinar la estimación de parámetros de probabilidad de un PCFG. Es posible reestimar el algoritmo PCFG encontrando el número esperado de veces que un estado se utiliza en una derivación a través de sumar todos los productos de α y β dividida por la probabilidad de una secuencia x dado el modelo P()xSilencioSilencio Silencio ){displaystyle P(x habittheta)}. También es posible encontrar el número esperado de veces que una regla de producción es utilizada por una expectativa-maximización que utiliza los valores de α y β. El algoritmo CYK calcula γ γ ()i,j,v){displaystyle gamma (i,j,v)} encontrar el árbol de parse más probable π π ^ ^ {fnMicrosoft {fnMicrosoft {fnMicrosoft {fnMicrosoft {fnMicrosoft {f {fnMicrosoft {fnMicrosoft {fnMicrosoft {fnMicrosoft {fnMicrosoft {fnMicrosoft {fnMicrosoft {fnMicrosoft {f}f}f}f {f}f}f {fnMicrosoft {fnMicrosoft {f}f}f}f}f}f}f}fnfnfnfnf}fn\fnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfn\\\fn\fnfn\fnfn } y rendimientos log⁡ ⁡ P()x,π π ^ ^ SilencioSilencio Silencio ){displaystyle log P(x,{hat {pi }.

La memoria y la complejidad del tiempo para algoritmos PCFG generales en las predicciones de la estructura RNA son O()L2M){displaystyle O(L^{2}M)} y O()L3M3){displaystyle O(L^{3}M^{3}} respectivamente. Restricting a PCFG may alter this requirement as is the case with database searches methods.

PCFG en 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 los CM es posible construir perfiles de ARN basados en PCFG donde los ARN relacionados pueden representarse mediante una estructura secundaria de consenso. El paquete de análisis de ARN Infernal utiliza dichos perfiles en la inferencia de alineaciones de ARN. La base de datos Rfam también utiliza CM para clasificar los ARN en familias según su estructura e información de secuencia.

Los CM están diseñados 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:

P→ → aWb{displaystyle Pto aWb}

probabilidades de interacciones pares entre 16 posibles pares

L→ → aW{displaystyle Lto aW}

probabilidades de generar 4 posibles bases individuales en la izquierda

R→ → Wa{displaystyle Rto Wa!

probabilidades de generar 4 posibles bases individuales en la derecha

B→ → SS{displaystyle Bto SS!

bifurcación con probabilidad de 1

S→ → W{displaystyle Sto W}

empezar con una probabilidad de 1

E→ → ε ε {displaystyle Eto epsilon }

final 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 entre sí.

Con el fin de marcar un modelo CM se utilizan los algoritmos externos. Los CM utilizan una implementación ligeramente diferente de CYK. Marcas de emisión de log-odds para el árbol de pares óptimo - log⁡ ⁡ e^ ^ {displaystyle log {hat {e}} - se calculan a partir de los estados emisores P,L,R{displaystyle P,~L,~R.. Puesto que estas puntuaciones son una función de longitud de secuencia una medida más discriminatoria para recuperar una puntuación óptima de probabilidad de árbol de parse- log⁡ ⁡ P()x,π π ^ ^ SilencioSilencio Silencio ){displaystyle log {text{P}(x,{hat {pi }tuvotheta)} - se alcanza limitando la longitud máxima de la secuencia a alinearse y calculando los log-odds relativos a un null. 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 O()MaD+MbD2){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 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 alineamiento 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 emparejadas y no emparejadas

En una alineación estructural las probabilidades de las columnas de bases no pintadas y las columnas de bases paradas son independientes de otras columnas. Contando bases en posiciones de base únicas y posiciones emparejadas se obtienen las frecuencias de las bases en bucles y tallos. Para básico X y Y una ocurrencia de XY{displaystyle XY. también se cuenta como una ocurrencia de YX{displaystyle Sí.. Pautas base idénticas como XX{displaystyle XX} son contados dos veces.

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

Al emparejar secuencias de todas las formas posibles, se estiman las tasas de mutación generales. Para recuperar mutaciones plausibles, debe usarse un umbral de identidad de secuencia para que la comparación sea entre secuencias similares. Este enfoque utiliza un umbral de identidad del 85 % entre las secuencias de emparejamiento. Las diferencias de posiciones de la primera base única -excepto las columnas separadas- entre los pares de secuencias se cuentan de tal manera que si la misma posición en dos secuencias tuviera bases diferentes X, Y el recuento de la diferencia se incrementa para cada secuencia.

mientras     X ل ل  Y   {displaystyle Xneq Sí.       C  XY   + 1   {displaystyle C_{text{XY}+1}  primer par de secuencia      C  YX   + 1   {displaystyle C_{text{YX}+1}  segundo par de secuencia

Calcule las tasas de mutación. Vamos      r  XY   =   {displaystyle ¿Qué?  mutación de la base X a la base Y     =    K   C  XY      P  x    P  s        {displaystyle ={frac {K~C_{XY}} {P_{x}}} {f}} {f}}} {f}}}}}} {f}}}}} {f}}}}}}} {f}}}}}}}}}}}}}}}}}}}}}}} {f}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {  Vamos      r  XX   =   {displaystyle ¿Qué?  el negativo de la tasa de mutación X a otras bases     = − −  ..   r  XY     {displaystyle =-sum r_{XY}}       P  s   =   {displaystyle P_{s}=  la probabilidad de que la base no esté emparejada.

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:

PXrXY=PYrYX{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 de adentro hacia afuera y la estructura más probable se encuentra mediante el algoritmo CYK.

Estimar probabilidades de alineación

Después de calcular las probabilidades anteriores de la columna, la probabilidad de alineación se calcula resumiendo sobre todas las estructuras secundarias posibles. Cualquier columna C en una estructura secundaria σ σ {displaystyle sigma } para una secuencia D de longitud l tales que D=()C1,C2,...Cl){displaystyle D=(C_{1},~C_{2},...C_{l} se puede anotar con respecto al árbol de alineación T y el modelo mutacional M. La distribución previa dada por el PCFG P()σ σ SilencioM){displaystyle P(sigma Silencio)}. El árbol filogenético, T se puede calcular desde el modelo por estimación máxima de probabilidad. Tenga en cuenta que las brechas se tratan como bases desconocidas y la suma se puede hacer mediante la programación dinámica.

P()DSilencioT,M){displaystyle P(D habitT,M)}

=.. P()D,σ σ SilencioT,M){displaystyle =sum P(D,sigma tenciónT,M)}

=.. P()DSilencioσ σ ,T,M)P()σ σ SilencioT,M){displaystyle =sum P(D habitsigmaT,M)P(sigma TENT,M)}

=.. P()DSilencioσ σ ,T,M)P()σ σ SilencioM){displaystyle =sum P(D habitsigmaT,M)P(sigma Silencio)}

Asigne 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 diseñadas 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 se escriben entre paréntesis en el formalismo gramatical y cada regla tendrá un total de 100%. Por ejemplo:

S→ → LS()80% % )SilencioL()20% % ){displaystyle Sto LS(80%)

L→ → s()70% % )SilenciodFd()30% % ){displaystyle Lto s(70%)

F→ → dFd()60,4% % )SilencioLS()39.6% % ){displaystyle Fto dFd(60.4%)

Predecir la probabilidad de la estructura

Dada las frecuencias de alineación previas de los datos, la estructura más probable del conjunto predicho por la gramática se puede calcular maximizando P()σ σ SilencioD,T,M){displaystyle P(sigma tenciónD,T,M)} a través del algoritmo CYK. La estructura con el mayor número previsto de predicciones correctas se informa como la estructura de consenso.

σ σ MAP=arg⁡ ⁡ maxσ σ P()DSilencioσ σ ,TML,M)P()σ σ SilencioM){displaystyle sigma _{}=rg {compset {sigma } {max }P(D habitsigmaT^{M}L,M)P(sigma ¦

Mejoras de pfold en el algoritmo KH-99

Se desea que los enfoques basados en PCFG sean escalables y lo suficientemente generales. Comprometer la velocidad por la precisión debe ser lo más mínimo posible. Pfold aborda las limitaciones del algoritmo KH-99 con respecto a la escalabilidad, las brechas, la velocidad y la precisión.

• En Pfold las brechas se tratan como desconocidas. En este sentido, la probabilidad de una columna apostada equivale a la de una columna sin explotar.
• En Pfold el árbol T se calcula antes de la predicción de la estructura a través de la unión vecina y no por la probabilidad máxima a través de la gramática PCFG. Sólo las longitudes de la rama se ajustan a estimaciones de probabilidad máxima.
• Una suposición de Pfold es que todas las secuencias tienen la misma estructura. umbral de identidad secuencial y permitiendo una probabilidad del 1% de que cualquier nucleótido se convierte en otro límite del deterioro del rendimiento debido a errores de alineación.

Análisis de secuencias de proteínas

Mientras que los PCFG han demostrado ser herramientas poderosas para predecir la estructura secundaria del ARN, el 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 comúnmente muestran dependencias de orden superior, incluidas 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 brinda la capacidad de modelar una gama más amplia de patrones de proteínas.