motivos y dominios - tamps.cinvestav.mxertello/bioinfo/sesion09.pdf · usando modelos estadísticos...

Motivos y Dominios

Jesús Fernández C.

Cinvestav-Zacatenco

19 de Junio del 2013

Jesús Fernández C. (Cinvestav) Motivos y Dominios 19 de Junio del 2013 1 / 58

1 Motivos y DominiosIntroducciónIdenti�cación de motivos y dominios en alineamiento múltiple desecuenciasUsando expresiones regulares en las bases de datosUsando modelos estadísticos en las bases de datosDescubrimiento de motivos en secuencias no alineadasMotivos reguladores en secuencias de ADNPro�lesEl problema de hallar motivos.Motif Finding Problem.Median String Problem.Search TreesMotif ProblemMedian String Problem


Motivos y Dominios Introducción




Introducción

Un aspecto importante de la caracterización de secuencias biológicasson los motivos y los dominios, ya que sirven para caracterizarfunciones de proteínas desconocidas.

Secuencias conservadas son secuencias biológicas similares o idénticasque pueden encontrarse en ácidos nucléicos, proteínas.

Un motivo es un elemento conservado en la secuencia de aminoácidoso nucleótidos, que habitualmente se asocia con una función concreta.Los motivos se generan a partir de alineamientos múltiples desecuencias con elementos funcionales o estructurales conocidos, por loque son útiles para predecir la existencia de esos mismos elementos enotras proteínas de función y estructura desconocida.



Introducción

Un dominio es un término más genérico que designa una región de unaproteína con interés biológico funcional o estructural. También sellama dominio a una región de la estructura tridimensional de unaproteína con una función concreta, que incluye regiones nonecesariamente contiguas en la secuencia de aminoácidos.


Motivos y DominiosIdenti�cación de motivos y dominios en alineamiento

múltiple de secuencias



Motivos y DominiosIdenti�cación de motivos y dominios en alineamiento


Identi�cación de motivos y dominios en alineamiento


Los motivos y dominios son construidos a partir de un AMdS(Alineamiento múltiple de Secuencias) en las cuales, las secuenciasestá relacionadas entre sí.

Esto sirve para hallar las regiones conservadas.

Una vez halladas las regiones que se consideran motivos y dominios seprosigue a almacenar la información de consenso en una base de datospara que así sirvan como base en la identi�cación de las funciones deuna proteína desconocida que presente los mismos patrones.

Esto puede ser almacenado de dos formas:Expresiones regulares oMediante un modelo estadístico.


Motivos y Dominios Usando expresiones regulares en las bases de datos




Usando expresiones regulares en las bases de datos

Una expresión regular es una manera concisa de representar unafamilia de secuencias por un string.

Cuando los dominios y los motivos son escritos en expresionesregulares se deben seguir las siguientes reglas.

Un aminoácido es conservado se debe escribir su código de letra.

Cuando una posición tiene varias alternativas de aminoácidos se

encierra entre corchetes todas las posibilidades.

Si no está especi�cado se escribe por una X.

Cada posición está ligada por un guión.

Finalmente si se repite un patrón se escribe entre paréntesis cuántas

veces se repite.




Ejemplo E − X (2)− [FHM]− X (4)− {P} − L.

Existen dos mecanismos para coincidir dos expresiones regulares: ExactMatching y Fuzzy Matching.




En el Exact Matching como su nombre lo indica no permite algunavariación en la secuencia del query, ésta manera de buscar tiene unaalta probabilidad de perder motivos relevantes que pueden tenerpequeñas variaciones.

En el Fuzzy matches, también llamado approximate matches, lascoincidencias son más �exibles entre residuos de propiedadesbioquímicas semejantes, éste método es capaz de incluir una mayorvariedad de formas de un motivo con una función conservada, sinembargo ésto incrementa el ruido y los falsos positivos.

Ejemplos: PROSITE y Emotif .


Motivos y Dominios Usando modelos estadísticos en las bases de datos




Usando modelos estadísticos en las bases de datos

La mayor limitación de las expresiones regulares es que estos métodosno toman en cuenta la información de la probabilidad. Una expresiónregular tiene menos poder predictivo porque muchas secuencias con elmismo tipo de motivo no son representadas.



Usando modelos estadísticos en las bases de datos

Al contrario de las expresiones regulares, se utilizan PSSMs (Positionspeci�c scoring matrices), per�les y HMMs (Hidden Makarov models)y preservan la información de la secuencia de un AMdS y lo expresancon modelos probabilísticos. Además, éstos modelos estadísticos tienenun mayor poder de predicción que los modelos basados en expresionesregulares, incluso aunque han sido obtenidos de un número reducidode secuencias. Ésta capacidad puede incrementar la sensibilidad deldescubrimiento de motivos y detectar secuencias divergentes pero queestén relacionadas.


Motivos y Dominios Descubrimiento de motivos en secuencias no alineadas




Descubrimiento de motivos en secuencias no alineadas

Para un conjunto de secuencias que estén estrechamente relacionadas,se pueden encontrar motivos mediante el uso de AMdS, pero nosucede ésto cuando son distantes pero están relacionadas.

Para detectar estos motivos se necesitan algoritmos más especializadoscomo: Expectation maximation y Gibbs Motif sampling.




Puede ser usado para encontrar motivos ocultos. El método primerohace un alineamiento aleatorio de secuencias para generar un PSSMde prueba. Luego la prueba es usada para comparar cada secuenciaindividualmente. Se irán modi�cando las puntuaciones de la PSSM encada iteración para maximizar el alineamiento de la matriz a cadasecuencia.

Durante cada iteración la secuencia de patrones de los motivosconservados se irá reuniendo en el PSSM.

El problema radica en la convergencia prematura al alcanzar unóptimo local.




Éste método es muy similar al EM. Primero se hace un alineamientosobre todas las secuencias excepto una. Luego un se genera un PSSMde prueba, luego la matriz se alinea con la secuencia que se dejó fuera.La matriz de puntuaciones se ajusta para obtener el mejoralineamiento. Éste se procesó se repite hasta que ya no quede nadaque mejorar.

Éste método es menos susceptible a los mínimos locales.


Motivos y Dominios Motivos reguladores en secuencias de ADN




Motivos reguladores en secuencias de ADN

Las moscas de fruta son susceptibles a infecciones de bacterias y otrospatógenos.Pero no tienen el sistema inmune tan so�sticado comonosotros. Ellos tienen un conjunto de genes inmunes que generalmentese encuentran dormidos en el genoma de la mosca los cuáles de algunamanera se despiertan y producen proteínas que destruyen el patógenoy generalmente curan la infección.




Si realizamos un experimento en el cual se contagian las moscas ymedimos cuales genes se despiertan como una respuesta inmune. Deeste conjunto de genes nos gustaría determinar que activa ese proceso.Éste proceso nos va a mostrar que los residuos TCGGGGATTTCC sonlos culpables de ésta activación. Éstas cadenas cortas llamadas NF-kBbinding sites, son importantes ejemplos de los motivos reguladores.Proteínas tales como los factores de transcripción están ligados a estosmotivos, Haciendo que el ARN polimerasa transcriba los genespreviamente dichos. Uno de los problemas es descubrir tales motivossin un conocimiento de como podrían verse.




Tomando en cuenta el experimento anterior va a devolver un conjuntode regiones de los genes en el genoma, cada región contiene al menosun NF-kB binding sites. Supongamos que no sabemos cual es elpatrón de NF-kB y tampoco sabes en que parte se encuentralocalizado en la muestra.

Por lo cual necesitamos un algoritmo que dado un conjunto desecuencias de un genoma, pueda encontrar subcadenas cortas queparezcan ocurrir seguido.

A pesar de que el DNA es complicado de descifrar, éste método esusado popularmente para encontrar motivos bajo la idea de quepalabras mas frecuentes o mas rara corresponden a los motivosreguladores en el ADN.




Figura: Texto encriptado




Figura: Texto parcialmente desencriptado


Motivos y Dominios Pro�les




Pro�les

Supongamos que se presentan 7 nucleótidos de tamaño 32 generadosaleatoriamente. También se da otro conjunto pero con el patrónsecreto p = ATGCAATCT y de tamaño l = 8 implantado en unaposición aleatoria. Supongamos que tampoco conocemos el patrón Po donde la secuencia es implantada. La tarea es hallar P analizando lasecuencia de ADN.

Una de las maneras de hacer esto es buscar todas las cadenas delongitud l que aparezcan en el conjunto, seria muy raro hallar ese tipode cadenas dado el azar(7 veces o mas) por lo cual podemos concluirque es el patrón p que estamos buscando.



Pro�les

Figura: Ejemplos de secuencias



Pro�les

Para hacer mas difícil el problema podemos hacer que ADN mute encierto nucleótidos, como por ejemplo tomando los NF-kB binding sitesTCGGGGATTTCC , y se da un conjunto donde cada cadena cambiamuy poco.

Esto se complica ya que la búsqueda de la cadena de tamaño 8 norevela ninguna patrón y la cadena ATGCAACT no aparece ni una solavez.

Por lo cual es necesario que queremos por �motivo� . Ya que permitirque un solo string represente un motivo generalmente falla alrepresentar las variaciones de los patrones en la vida real sin embargouna representación de un motivo puede ser hecho por una matriz deper�les.



Pro�les

Figura: Nucleótidos mutados y la obtención del Patrón



Pro�les

Figura: Secuencia con mutaciones



Pro�les

Lo que se realiza es lo siguiente, consideremos que un conjunto de tsecuencias de ADN, cada una tiene n nucleótidos. Selecciona unaposición de esas t secuencias,y así formar un array s = (s1, s2, ..., st ,con 1 <= si <= n − l + 1. Éstas cadenas de tamaño l pueden seragrupadas en una matriz, la cual será la matriz de per�les y despuésde un consenso se halla que el string de consenso es ATGCAACT quees el patrón P.



Pro�les

Figura: Selección del consenso


Motivos y Dominios El problema de hallar motivos.




El problema de hallar motivos.

Si P(s) denota la matriz de per�les correspondiente a las posicionesde inicio s, entonces podemos usar Mps(j) para denotar como elmayor número en la columna j de P(s).

Mientras que la puntuación de consenso está dada por la suma detodos los Mps(j), éste score puede se usado como una medida de quetan fuerte es un per�l correspondiendo las posiciones de inicio de s.

Un consenso de la puntuación lt corresponde al mejor alineamientoposible, en el cual cada �la de una columna tiene la misma letra. Sinembargo un consenso de lt/4 corresponde al peor alineamiento posible.



El problema de hallar motivos.

En la forma más sencilla el problema de hallar el motivo se formulacomo la selección de las posiciones iniciales de s.


Motivos y Dominios Motif Finding Problem.




Motif Finding Problem.

Dado un conjunto de secuencias encontrar el conjunto de l-mers. unopor cada secuencia, que maxímice las puntuaciones.Input: Una matriz t × n de ADN.Output: Un arreglo de t que contienen posiciones inicialess = (s1, s2, ..., st) que maxímize Score(s,DNA).



Motif Finding Problem.

Otra forma de ver el problema es en formular el problema como sifuera un problema de hallar un String mediano. Dado dos l-mers v yw , podemos computar la distancia de Hamming entre ellos, como elnúmero de posiciones que di�eren en los dos string.

Forzando la notación podemos calcular la distancia de hamming totalentre v y s, dH(v , s), para hallar la distancia mínima de hammingentre un string v y cualquier set es un problema sencillo.

Primero uno tiene que encontrar la mejor coincidencia para v en laprimer secuencia de ADN, luego la segunda y así sucesivamente.


Motivos y Dominios Median String Problem.



Motivos y Dominios Median String Problem.

Median String Problem.

Dado un conjunto desecuencias de ADN, encontrar el string mediano.Input: Una matriz At × n de ADN, y l la longitud del patrón.Output: Un string v de l nucleótidos que minimize la distancia totalentre v ,ADN, sobre todos los strings de esa longitud.

Una vez calculado el string medio del ADN puede ser usado paragenerar un pro�le que resuelva el problema de busqueda de motivos.


Motivos y Dominios Search Trees




Search Trees

Como hemos visto hasta ahora para resolver los problemas de hallar elmotivo y encontrar la cadena mediana, es necesario manejar una grancantidad de información ((n − l + 1)ty k l )

En general puede ser visto como un todos los kL L-mers, la siguientesubrutina NextLeaf muestra como saltar de un L-mer a otro através deuna progresión.



Search Trees

Figura: Espacio de busqueda para hallar los mejores s



Search Trees

Figura: Espacio de busqueda para hallar la cadena mediana



Search Trees

NEXTLEAF(a, L, k)1 for i ← L to 12 if ai < k

3 ai ← ai + 14 return a

5 ai ← 16 return a



Search Trees

Utilizando este algoritmo podemos producir todas las hojas de un L-mercon el algoritmo a continuación.ALL LEAVES(L, k)

1 a← (1, ..., 1)2 while forever3 output a4 a←NEXTLEAF(a, L, k)5 if a = (1, 1, ..., 1)6 return



Search Trees

Estas hojas pueden ser utilizadas para construir un árbol como el siguiente.

Figura: Arbol con k = 2 y l = 4



Search Trees

PREORDER(v)1 output v2 if v has children3 PREORDER ( left child of v )4 PREORDER ( rigth child of v )



Search Trees

Una manera iterativa de hacer esto es la siguiente.NEXTVERTEX(a, i , L, k)

1 if i < L

2 ai+1 ← 13 return (a, i + 1)4 else5 for j ← L to 16 if aj < k

7 aj ← aj + 18 return (a, j)

9 return (a, 0)

Cuando i > L, nos movemos hacia abajo en el árbol. Si i = L y j < k nosmovemos a los lados del árbol, pero k = j nos movemos hacia atrás, elproceso acaba cuando todo el árbol es explorado.


Motivos y Dominios Motif Problem




Motif Problem

El algoritmo de fuerza bruta quedaría como el siguiente.BRUTEFORCEMOTIFSEARCH(ADN, t, n, l)

1 bestScore ← 02 for each (s1, ..., st) from (1, ..., 1) to (n − l + 1, ..., n − l + 1)3 if Score(s,ADN) > bestScore

4 bestScore ← Score(s,ADN)

5 bestMotif ← (s1, s2, ..., st)6 return bestMotif



Motif Problem

Para encontrar un mejor método podemos utilizar el método de selecciónpara encontrar todos los posiblesL-mer.BRUTEFORCEMOTIFSEARCHAGAIN(ADN, t, n, l)

1 s ← (1, 1, ..., 1)2 bestScore ← Score(s,ADN)

3 while forever4 s ← NEXTLEAF(s, t, n − l + 1)5 if Score(s,ADN) > bestScore


7 bestMotif ← (s1, s2, ..., st)8 if s = (1, 1, ..., 1)9 return bestMotif



Motif Problem

O en su defecto podemos utilizar el algoritmo de NextVertex para generarun árbol.SIMPLEMOTIFSEARCH(ADN, t, n, l)

1 s ← (1, 1, ..., 1)2 bestScore ← 03 i ← 04 while i > 05 if i < t

6 (s, i)←NEXTVERTEX(s, i , t, n − l + 1)7 else8 if Score(s,ADN) > bestScore

9 bestScore ← Score(s,ADN)10 bestMotif ← (s1, s2, ..., st)11 (s, i)←NEXTVERTEX(s, i , t, n − l + 1)12 return bestMotif



Motif Problem

Podemos observar de los resultados para hallar la mejor puntuacion. Porejemplo si al primeras i posiciones de inicio t son un per�l débil, puede queno sea necesario seguir analizando esa rama, ya que lo más probable es quelos per�les que se puedan generar no sean mejores que los per�les quegeneren las otras ramas.BRANCHANDBOUNDMOTIFSEARCH(ADN, t, n, l)

1 s ← (1, 1, ..., 1)2 bestScore ← 03 i ← 04 while i > 05 if i < t

6 optimisticScore ← Score(s, i ,ADN) + (t − i)l

7 if optimisticScore < bestScore

8 (s, i)← BYPASS(s, i , t, n − l + 1)



Motif Problem

1 else2 (s, i)←NEXTVERTEX(s, i , t, n − l + 1)3 else4 if Score(s,ADN) > bestScore


6 bestMotif ← (s1, s2, ..., st)7 (s, i)←NEXTVERTEX(s, i , t, n − l + 1)8 return bestMotif

Con esto el algoritmo es mejorado para algunas instancias, pero no todas,el peor caso sigue siendo exponencial.


Motivos y Dominios Median String Problem




Median String Problem

Se pueden aplicar los mismo metodos que se aplicaron para mejorar elproblema de motivos, pero ahora con respecto a la mediana, el algoritmooptimizado sería el siguiente.BRANCHANDBOUNDMEDIANSEARCH(ADN, t, n, l)

1 s ← (1, 1, ..., 1)2 bestScore ←∞3 i ← 04 while i > 05 if i < l

6 pre�x ←nucleotide string corresponding to (s1, s2, ..., si)7 optimisticDistance ← TOTALDISTANCE(pre�x ,ADN)

8 if optimisticDistance > bestDistance

9 (s, i)← BYPASS(s, i , t, 4)



Median String Problem

1 else2 (s, i)←NEXTVERTEX(s, i , t, 4)3 else4 word ←nucleotide string corresponding to (s1, s2, ...sl)5 if TOTALDISTANCE(word ,ADN) < bestDistance

6 bestDistance ← TOTALDISTANCE (word ,ADN)

7 bestWord ← word

8 (s, i)←NEXTVERTEX(s, i , t, n − l + 1)9 return bestWord

Como en el caso anterior, el algoritmo no provee una mejora en el peor delos casos, pero hace un incremento en general a la aceleración.


motivos y dominios - tamps.cinvestav.mxertello/bioinfo/sesion09.pdf · usando modelos estadísticos...

Documents