Gramáticas para el análisis de Secuencias Biológicas



Monografias.com
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. Þ Esta suposición se rompe dramáticamente para el RNA!
Monografias.com
La estructura secundaria del RNA pone constrains sobre la secuencia del RNA.
Monografias.com
tRNA en acción!
Monografias.com
Se deben adoptar nuevos modelos que consideren las correlaciones a larga distancia entre pares de residuos
Monografias.com
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
Monografias.com
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
Monografias.com
Árbol de parsing para UAG
Monografias.com
Gramáticas probabilísticas
Monografias.com
Jerarquía de Chomsky
Monografias.com
Gramáticas regulares u®Xv u®X Gramáticas libres de contexto u®b Gramáticas sensitivas al contexto a1 u a2 ® a1 b a2 Gramáticas irrestrictas a1 u a2 ® g donde u y v son no terminales, X es un terminal, a y g son cualquier secuencia de terminales / no terminales, excluyendo el string nulo, y b es cualquier secuencia de terminales / no terminales
Monografias.com
Gramaticas y parsers (Gp:) Máquina de Turing (Gp:) Gramática irrestricta (Gp:) Automata linealmente acotado (Gp:) Gramática sensitiva al contexto (Gp:) Automata de pila (Gp:) Gramática libre de contexto (Gp:) Automata de estados finitos (Gp:) Gramática Regular (Gp:) Automata de parsing (Gp:) Gramática
Monografias.com
De las gramáticas regulares a las gramáticas libres de contexto
Monografias.com
RNA: palindromos complementarios
Monografias.com
Lo que necesitamos modelar para nuestro problema del RNA es la simetría, como un palíndromo
Monografias.com
Extensión Para cubrir estas interacciones a larga distancia necesitamos hacer una extensión a nuestras reglas de escritura: Gramáticas regulares {NoTerminal} ® {Terminal}{NoTerminal} | {Terminal} Gramáticas libres de contexto {NoTerminal} ® string de simbolos
Monografias.com
Principal ventaja 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 | .. (Context Free) Versus: S ® aS | bS | b | a (Regular)