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
| Página siguiente |