gramaticas rna

Gramáticas para el análisis de secuencias biológicas

Ing. Informático Mitchell Blancas

Facultad de CC.FF. - Escuela de Informática 1

Secuencias y estructuras

• Los algoritmos de análisis de secuencias tratan al DNA, RNA y a las proteínas como strings de nucleótidos o aminoácidos

• La mayoría de estos algoritmos asume strings de elementos sin relación, donde el valor de un residuo en una posición no tiene efecto sobre el valor de otro residuo (La suposición anterior se rompe dramáticamente para el RNA).


• La estructura secundaria del RNA pone constrains sobre la secuencia del RNA.


RNA en acción


GRAMATICAS


Se deben adoptar nuevos modelos que consideren las correlaciones a larga distancia entre pares de residuos….

Gramáticas transformacionales

• Una gramática caracteriza un lenguaje

• Una gramática consiste de:– N: Un conjunto de símbolos no terminales– V: Un conjunto de símbolos terminales

(son los que realmente aparecen en el string)

– S: Un símbolo no terminal de start S– P: Un conjunto de producciones


Ejemplo: Una gramática para codones stop

• Lenguaje: UAA, UAG, UGA

• N: {s, c1, c2, c3, c4}

• S: s • V: {A, C, G, U}

• P: s c1 c1 Uc2 c2 Ac3 c3 A

c2 Gc4 c3 G

c4 A


Árbol de parsing para UAG


Gramáticas probabilísticas


Jerarquía de Chomsky


Gramaticas y parsers

Máquina de TuringGramática irrestricta

Automata linealmente acotadoGramática sensitiva al contexto

Automata de pilaGramática libre de contexto

Automata de estados finitosGramática Regular

Automata de parsingGramática


De gramáticas regulares a gramáticas libres de

contexto


RNA: palindromos complementarios


Lo que necesitamos modelar para nuestro problema del RNA es la simetría, como un palíndromo


Extensión

• Para cubrir estas interacciones a larga distancia necesitamos hacer una extensión a nuestras reglas de escritura:

• Gramáticas regulares (GR){NoTerminal} {Terminal}{NoTerminal} {Terminal}

• Gramáticas libres de contexto (GLC o CFG){NoTerminal} string de simbolos


Principal ventaja de una GLC

• Las gramaticas regulares generan strings de izquierda a derecha, las gramaticas libres de contexto pueden generar strings de afuera hacia adentro.

• Veamos: S aSa bSb bb aa .. (Libre de

contexto)

Versus: S aS bS b a (Regular)


CFG (GLC) y RNA• Aquí vemos una GLC que puede generar un stem

de 3 bases, y un loop de GAAA o GCAA


De gramáticas libres de contexto a gramáticas sensitivas al contexto


Pseudoknots

• Las gramaticas sensitivas al contexto permiten modelar lenguajes Copy, que son los que se presentan en los pseudoknots.


Problema

No se conocen algoritmos generales en tiempo polinomial para parsear gramáticas sensitivas al contexto.


Tres problemas basicos• Scoring: Cuan probable es una secuencia dado un

SCFG parametrizado? Algoritmo Inside

• Training: Dado un conjunto de secuencias, como estimamos los parámetros de un SCFG? Algoritmo Inside Outside

• Alineamiento: Cual es el parsing mas probable de una secuencia a un SCFG parametrizado? Algoritmo CYK

* SCFG = «Stochastic context-free grammar»


• α (i,j,v): la probabilidad suma de todos los subtrees de parsing de raíz v para la subsecuencia de i a j

Determinando la probabilidad de una secuencia: El Algoritmo Inside


El algoritmo Inside


El algoritmo Inside

• Inicialización: (i,i,v) = ev (xi )

• Iteración

• Terminación: Pr(x) = (1,L,1)


El algoritmo Outside: (i,j,v)


Algoritmo CYK

• Dada una secuencia X encontrar el parsing mas probable.

• A la probabilidad del parsing mas probable del substring Xi...Xj con raiz en V la llamamos (i,j,V).

• Empezamos con (i,i,V) = log P(VXi)• Para todo (j > i), buscamos todas las

producciones VYZ y nos quedamos con la de máxima probabilidad.


Algoritmo CYK

(i,i,V) = log P(VXi), no terminal V, 1iNfor i=1 to N-1 for j=i+1 to N no terminal V (i,j,V) = maxx maxy maxikj [log P(VXY)

+ (i,k,X) + (k+1,j,Y)];end

endforendforreturn (1,N,S)


Veamos una aplicación de las gramáticas a la estructura secundaria del RNA..


Algoritmo Nussinov

• Dada: Una secuencia RNA• Objetivo: Encontrar la estructura secundaria que maximice

el numero de apareamiento de bases• Algoritmo recursivo: Encuentra la mejor estructura para

los inputs i...j intentando una de las siguientes 4 posibilidades:– Agregar el par i, j sobre la mejor estructura i+1...j-1– Agregar i sin aparear a la mejor estructura i+1...j– Agregar j sin aparear a la mejor estructura i...j-1– Combinar las dos estructuras optimas i...k y k+1...j


Casos en Nussinov


Algoritmo Nussinov• La secuencia a analizar tiene longitud L.• Es un algoritmo de programación dinámica que llena

una matriz de L x L, con la información del máximo apareamiento de las bases.

• Hacemos la función (xi, xj) = 1, si xi y xj se aparearían entre si, y (xi, xj) = 0, en caso contrario.


Algoritmo Nussinov• Inicialización:

(i, i-1) = 0, i= 2...L

(i, i) = 0, i= 1...L• Recursión: for i=1...L-1, j=i+1...L

• Terminación: máxima cantidad de apareamientos de bases: (1, L)


Nussinov traceback

• Inicialización: Push (1,L) en el stack• Recursión: Repetir hasta que el stack este vacío

pop(i,j)

if i > j continuar

else if (i+1, j) = (i, j) push (i+1, j)

else if (i, j-1) = (i, j) push (i, j-1)

else if (i+1, j-1)+ij = (i, j):

registrar i, j como apareamiento

push (i+1, j-1)

else for k= i+1 to j-1: if (i,k)+ (k+1,j)= (i,j):

push (k+1,j)

push (i,k)

break


Ejemplo


Versión SCFG del ejemplo Nussinov

• S GSC: 3 CSG: 3 ASU: 2USA: 2 GSU: 1 USG: 1

• S SS: 0 : 0• S AS: 0 CS: 0 GS: 0 US: 0 • S SA: 0 SC: 0 SG: 0 SU: 0


Referencias

1. Biological sequence analysis (Capitulos 9 y 10). Durbin, R., Eddy,

S., Krogh, A., Mitchison, G., Cambridge University Press, 1998.

2. Bioinformatics, The Machine Learning Approach, 2da. Edicion

(Capitulo 11). Baldi, P. & Brunak, S., MIT press, 2001.

3. Bioinformatics: sequence and genome analysis (Capitulo 5). Mount,

D., Cold Spring Harbor Laboratory Press, 2001.

4. The language of RNA: a formal grammar that includes pseudoknots.

Rivas E., Eddy, S.R., Bioinformatics. 2000 Apr;16(4):334-40.1.


gramaticas rna

Documents