Gramáticas para el análisis de Secuencias Biológicas (página 2)

Partes: 1, 2

CFG y RNA
Aca vemos una gramatica context free que puede generar un stem de 3 bases, y un loop de GAAA o GCAA

De las gramáticas libres de contexto a las 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
Sub No se conocen algoritmos generales en tiempo polinomial para
parsear gramaticas sensitivas al contexto

Tres problemas basicos
Scoring: Cuan probable es una secuencia dado un SCFG parametrizado?
Algoritmo Inside
Training: Dada un conjunto de secuencias, como estimamos los parametros de un SCFG?
Algoritmo Inside Outside
Alineamiento: Cual es el parsing mas probable de una secuencia a un SCFG parametrizado?
Algoritmo CYK

a (i,j,v): la probabilidad suma de todos los subtrees de parsing de raiz v para la subsecuencia de i a j
Determinando la probabilidad de una secuencia: El Algoritmo Inside

El algoritmo Inside

El algoritmo Inside
Inicializacion: ?(i,i,v) = ev (xi )

Iteracion

Terminacion: Pr(x) = ?(1,L,1)

El algoritmo Outside: b(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 g (i,j,V).
Empezamos con g (i,i,V) = log P(V®Xi)
Para todo j > i, buscamos todas las producciones V®YZ y nos quedamos con la de maxima probabilidad.

Algoritmo CYK
g (i,i,V) = log P(V®Xi), " no terminal V, " 1£i£N
for i=1 to N-1
for j=i+1 to N
" no terminal V
g (i,j,V) = maxx maxy maxi£k£j [log P(V®XY)+ g (i,k,X)+ g (k+1,j,Y)];
endfor
endfor
return g (1,N,S)

Sub Recordamos las elecciones hechas en CYK en cada paso para reconstruir el parser optimo!

Veamos una aplicación de la gramatica a la estructura secundaria del RNA
Sub .

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 programacion dinamica que llena una matriz de L x L, con la informacion del maximo apareamiento de las bases.
Hacemos la funcion ? (xi, xj) = 1, si xi y xj se aparearian entre si, y ? (xi, xj) = 0, en caso contrario.

Algoritmo Nussinov
Inicializacion:
? (i, i-1) = 0, i= 2…L
? (i, i) = 0, i= 1…L
Recursion: for i=1…L-1, j=i+1…L

Terminacion: maxima cantidad de apareamientos de bases: ? (1, L)

Nussinov traceback
Inicializacion: Push (1,L) en el stack
Recursion: Repetir hasta que el stack este vacio
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

Version SCFG de Nussinov

S ® GSC: 3 ½ CSG: 3 ½ ASU: 2½USA: 2 ½GSU: 1 ½ USG: 1
S ® SS: 0 ½ e: 0
S ® AS: 0 ½ CS: 0 ½ GS: 0 ½ US: 0
S ® SA: 0 ½ SC: 0 ½ SG: 0 ½ SU: 0