Post on 12-Dec-2015
description
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).
Facultad de CC.FF. - Escuela de Informática 2
• La estructura secundaria del RNA pone constrains sobre la secuencia del RNA.
Facultad de CC.FF. - Escuela de Informática 3
RNA en acción
Facultad de CC.FF. - Escuela de Informática 4
GRAMATICAS
Facultad de CC.FF. - Escuela de Informática 5
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
Facultad de CC.FF. - Escuela de Informática 6
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
Facultad de CC.FF. - Escuela de Informática 7
Árbol de parsing para UAG
Facultad de CC.FF. - Escuela de Informática 8
Gramáticas probabilísticas
Facultad de CC.FF. - Escuela de Informática 9
Jerarquía de Chomsky
Facultad de CC.FF. - Escuela de Informática 10
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
Facultad de CC.FF. - Escuela de Informática 11
De gramáticas regulares a gramáticas libres de
contexto
Facultad de CC.FF. - Escuela de Informática 12
RNA: palindromos complementarios
Facultad de CC.FF. - Escuela de Informática 13
Lo que necesitamos modelar para nuestro problema del RNA es la simetría, como un palíndromo
Facultad de CC.FF. - Escuela de Informática 14
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
Facultad de CC.FF. - Escuela de Informática 15
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)
Facultad de CC.FF. - Escuela de Informática 16
CFG (GLC) y RNA• Aquí vemos una GLC que puede generar un stem
de 3 bases, y un loop de GAAA o GCAA
Facultad de CC.FF. - Escuela de Informática 17
De gramáticas libres de contexto a gramáticas sensitivas al contexto
Facultad de CC.FF. - Escuela de Informática 18
Pseudoknots
• Las gramaticas sensitivas al contexto permiten modelar lenguajes Copy, que son los que se presentan en los pseudoknots.
Facultad de CC.FF. - Escuela de Informática 19
Problema
No se conocen algoritmos generales en tiempo polinomial para parsear gramáticas sensitivas al contexto.
Facultad de CC.FF. - Escuela de Informática 20
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»
Facultad de CC.FF. - Escuela de Informática 21
• α (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
Facultad de CC.FF. - Escuela de Informática 22
El algoritmo Inside
Facultad de CC.FF. - Escuela de Informática 23
El algoritmo Inside
• Inicialización: (i,i,v) = ev (xi )
• Iteración
• Terminación: Pr(x) = (1,L,1)
Facultad de CC.FF. - Escuela de Informática 24
El algoritmo Outside: (i,j,v)
Facultad de CC.FF. - Escuela de Informática 25
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.
Facultad de CC.FF. - Escuela de Informática 26
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)
Facultad de CC.FF. - Escuela de Informática 27
Veamos una aplicación de las gramáticas a la estructura secundaria del RNA..
Facultad de CC.FF. - Escuela de Informática 28
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
Facultad de CC.FF. - Escuela de Informática 29
Casos en Nussinov
Facultad de CC.FF. - Escuela de Informática 30
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.
Facultad de CC.FF. - Escuela de Informática 31
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)
Facultad de CC.FF. - Escuela de Informática 32
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
Facultad de CC.FF. - Escuela de Informática 33
Ejemplo
Facultad de CC.FF. - Escuela de Informática 34
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
Facultad de CC.FF. - Escuela de Informática 35
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.
Facultad de CC.FF. - Escuela de Informática 36