Story Transcript
Alineamiento de pares de secuencias Dr. Eduardo A. R ODRÍGUEZ T ELLO C INVESTAV-Tamaulipas
30 de mayo del 2013
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
1 / 61
1
Alineamiento de pares de secuencias Introducción Evolución de secuencias Homología y similitud de secuencias Similitud e identidad de secuencias Métodos de alineamiento de secuencias Método de matriz de puntos Programación dinámica Tarea
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
2 / 61
Alineamiento de pares de secuencias
1
Introducción
Alineamiento de pares de secuencias Introducción Evolución de secuencias Homología y similitud de secuencias Similitud e identidad de secuencias Métodos de alineamiento de secuencias Método de matriz de puntos Programación dinámica Tarea
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
3 / 61
Alineamiento de pares de secuencias
Introducción
Introducción
La comparación de secuencias es una de las actividades fundamentales en el análisis bioinformático Es un primer paso hacia el análisis estructural y funcional de nuevas secuencias descubiertas A medida que nuevas secuencias están siendo generadas a tasas exponenciales, la importancia de la comparación de secuencias ha aumentando considerablemente
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
4 / 61
Alineamiento de pares de secuencias
Introducción
Introducción Esto se debe a que gracias a la comparación de secuencias es posible realizar inferencias sobre la evolución de una nueva proteína en base a proteínas existentes en las bases de datos (BD) El proceso fundamental detrás de este tipo de comparación es el alineamiento de secuencias En términos simples el alineamiento de secuencias es el proceso en el cual diferentes secuencias son comparadas mediante la búsqueda de patrones de caracteres comunes y el establecimiento de correspondencias residuo-residuo entre secuencias relacionadas
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
5 / 61
Alineamiento de pares de secuencias
Introducción
Introducción
El alineamiento de pares de secuencias es el proceso de alineamiento de dos secuencias y es la base de diversas herramientas de análisis de secuencias: Alineamiento múltiple de secuencias Desarrollo de modelos ocultos de Márkov (búsqueda de familias de proteínas) Predicción de la estructura 3D de proteínas Análisis filogenético Búsqueda de similitud en BD
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
6 / 61
Alineamiento de pares de secuencias
Introducción
Introducción
Alineamiento de secuencias producido con ClustalW entre dos secuencias de proteínas zinc finger disponibles en GenBank
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
7 / 61
Alineamiento de pares de secuencias
1
Evolución de secuencias
Alineamiento de pares de secuencias Introducción Evolución de secuencias Homología y similitud de secuencias Similitud e identidad de secuencias Métodos de alineamiento de secuencias Método de matriz de puntos Programación dinámica Tarea
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
8 / 61
Alineamiento de pares de secuencias
Evolución de secuencias
Evolución de secuencias
El ADN y las proteínas son producto de la evolución Recordemos que los componentes básicos de estas macromoléculas (bases y aminoácidos) forman secuencias lineales que determinan la estructura primaria de las moléculas Una característica importante de estas moléculas es que codifican la historia de millones de años de evolución
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
9 / 61
Alineamiento de pares de secuencias
Evolución de secuencias
Evolución de secuencias
Durante este largo período de evolución las secuencias moleculares han sufrido cambios aleatorios (mutaciones) que las hacen diferir Sin embargo, algunos rastros de la evolución pueden quedar en ciertas porciones de las secuencias, lo que permite identificar los ancestros comunes La presencia de estos rastros se debe a que los residuos que realizan papeles importantes (funcionales o estructurales) tienden a ser preservados por la selección natural
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
10 / 61
Alineamiento de pares de secuencias
Evolución de secuencias
Evolución de secuencias
Por otra parte los residuos que son menos cruciales tienden a mutar más frecuentemente Ejemplo: los sitios activos de los residuos de una familia de enzimas tienden a ser conservados porque son responsables de las funciones catalíticas Gracias a la comparación de secuencias mediante alineamiento es posible identificar la conservación y variación de patrones
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
11 / 61
Alineamiento de pares de secuencias
Evolución de secuencias
Evolución de secuencias
El grado de conservación en el alineamiento revela las relaciones evolutivas de secuencias diferentes Mientras que la variación entre secuencias refleja los cambios que han ocurrido durante la evolución (substituciones, inserciones y eliminaciones)
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
12 / 61
Alineamiento de pares de secuencias
Evolución de secuencias
Evolución de secuencias La identificación adecuada de las relaciones evolutivas entre secuencias permite caracterizar la función de secuencias desconocidas de la siguiente forma: Cuando un alineamiento de secuencias revela una similitud significativa entre un grupo de secuencias entonces se puede considerar que pertenecen a la misma familia (mismo origen evolucionario) Si un miembro de esa familia tiene una estructura o funciones conocidas, entonces esa información puede extrapolarse a aquellos que aún no se han caracterizado experimentalmente
Es así como el alineamiento de secuencias es usado como base para la predicción de la estructura y función de secuencias no caracterizadas
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
13 / 61
Alineamiento de pares de secuencias
Evolución de secuencias
Evolución de secuencias Extrapolación de información acerca de una secuencia utilizando las características conocidas de otra secuencia
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
14 / 61
Alineamiento de pares de secuencias
Evolución de secuencias
Evolución de secuencias Relaciones en la evolución de secuencias Misma secuencia
Mismo origen
Misma funci´on
Mismo plegado 3D
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
15 / 61
Alineamiento de pares de secuencias
1
Homología y similitud de secuencias
Alineamiento de pares de secuencias Introducción Evolución de secuencias Homología y similitud de secuencias Similitud e identidad de secuencias Métodos de alineamiento de secuencias Método de matriz de puntos Programación dinámica Tarea
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
16 / 61
Alineamiento de pares de secuencias
Homología y similitud de secuencias
Homología y similitud de secuencias
Un concepto importante en el análisis de secuencias es la homología de secuencias Cuando dos secuencias descienden de un origen evolucionario común, se dice que tienen una relación homóloga o que comparten una homología Por su parte la similitud de secuencias mide el porcentaje de residuos alineados que son similares en cuanto a propiedades fisicoquímicas tales como el tamaño, carga, e hidrofobicidad
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
17 / 61
Alineamiento de pares de secuencias
Homología y similitud de secuencias
Homología y similitud de secuencias Aun cuando los dos términos suelen confundirse, es importante distinguir sus diferencias La homología de secuencias es una conclusión (inferencia) acerca de una relación ancestral común hecha a base de comprobar que existe un grado de similitud suficientemente alto entre las secuencias comparadas La homología es una afirmación cualitativa (homólogas o no homólogas) Por otra parte, la similitud es un resultado directo de la observación de un alineamiento de secuencias y se cuantifica usando porcentajes (40 % similitud)
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
18 / 61
Alineamiento de pares de secuencias
Homología y similitud de secuencias
Homología y similitud de secuencias
En la práctica el decidir a que nivel de similitud puede uno inferir relaciones de homología no es siempre fácil La respuesta depende del tipo de secuencias examinadas y de sus longitudes Las secuencias de nucleótidos consisten solo de 4 caracteres, y por lo tanto, las secuencias no relacionadas tiene al menos 25 % de oportunidad de ser idénticas
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
19 / 61
Alineamiento de pares de secuencias
Homología y similitud de secuencias
Homología y similitud de secuencias
Para las secuencias de proteínas, hay 20 posibles residuos de aminoácidos, y por lo tanto dos secuencias no relacionadas pueden coincidir hasta en 5 % de los residuos por azar Además si se permiten huecos, el porcentaje puede incrementarse entre 10 y 20 % La longitud de las secuencias también es un factor muy importante
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
20 / 61
Alineamiento de pares de secuencias
Homología y similitud de secuencias
Homología y similitud de secuencias
Entre más corta es una secuencia más alta es la posibilidad de que algún alineamiento se deba al azar Entre más larga es una secuencia es menos probable que una coincidencia en el mismo nivel de similitud sea atribuible al azar
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
21 / 61
Alineamiento de pares de secuencias
Homología y similitud de secuencias
Homología y similitud de secuencias Tres zonas de los alineamientos de secuencias: homólogas, probablemente homólogas, no es posible determinar homología
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
22 / 61
Alineamiento de pares de secuencias
1
Similitud e identidad de secuencias
Alineamiento de pares de secuencias Introducción Evolución de secuencias Homología y similitud de secuencias Similitud e identidad de secuencias Métodos de alineamiento de secuencias Método de matriz de puntos Programación dinámica Tarea
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
23 / 61
Alineamiento de pares de secuencias
Similitud e identidad de secuencias
Similitud e identidad de secuencias
Otros dos conceptos relacionados con la comparación de secuencias son la similitud y la identidad de secuencias Cuando se trata de secuencias de nucleótidos estos dos términos son sinónimos Sin embargo, para secuencias de proteínas los dos conceptos son muy diferentes
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
24 / 61
Alineamiento de pares de secuencias
Similitud e identidad de secuencias
Similitud e identidad de secuencias
En el alineamiento de secuencias de proteínas, la identidad de secuencias se refiere al porcentaje de coincidencias de los mismos residuos de aminoácidos entre las dos secuencias alineadas Por su parte la similitud de secuencias se refiere al porcentaje de residuos alineados que tienen características fisicoquímicas similares y que pueden ser substituídos entre sí
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
25 / 61
Alineamiento de pares de secuencias
Similitud e identidad de secuencias
Similitud e identidad de secuencias
Para calcular el porcentaje de similitud de dos secuencias se emplea la siguiente fórmula que hace uso de la totalidad de las longitudes de ambas secuencias: S = [(Ls × 2)/(La + Lb )] × 100
(1)
donde S es el porcentaje de similitud de las secuencias, Ls es el número de residuos alineados con características similares, y La , Lb son las longitudes totales de cada secuencia
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
26 / 61
Alineamiento de pares de secuencias
Similitud e identidad de secuencias
Similitud e identidad de secuencias
La identidad (I) de las secuencias puede ser calculada de manera similar: I = [(Li × 2)/(La + Lb )] × 100 (2) donde Li es el número de residuos alineados idénticos
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
27 / 61
Alineamiento de pares de secuencias
1
Métodos de alineamiento de secuencias
Alineamiento de pares de secuencias Introducción Evolución de secuencias Homología y similitud de secuencias Similitud e identidad de secuencias Métodos de alineamiento de secuencias Método de matriz de puntos Programación dinámica Tarea
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
28 / 61
Alineamiento de pares de secuencias
Métodos de alineamiento de secuencias
Métodos de alineamiento de secuencias
El alineamiento de pares de secuencias consiste en encontrar la mejor forma de emparejar (aparear) dos secuencias, de forma tal que haya una máxima correspondencia entre los residuos Para realizar esto, una de las secuencias necesita ser corrida con relación a la otra para encontrar la posición donde se da el máximo de coincidencias Hay dos estrategias diferentes de alineamiento que son utilizadas: Alineamiento global Alineamiento local
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
29 / 61
Alineamiento de pares de secuencias
Métodos de alineamiento de secuencias
Métodos de alineamiento de secuencias En el alineamiento global, se asume que las dos secuencias que se van a alinear son generalmente similares sobre sus longitudes totales El alineamiento se lleva a cabo a todo lo largo de ambas secuencias para encontrar el mejor posible Este método es más aplicable para alinear dos secuencias relacionadas estrechamente de aproximadamente la misma longitud En el caso contrario no entregará buenos resultados, pues tiene problemas para reconocer regiones locales altamente similares entre dos secuencias
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
30 / 61
Alineamiento de pares de secuencias
Métodos de alineamiento de secuencias
Métodos de alineamiento de secuencias Por el contrario, el alineamiento local no asume que las dos secuencias en cuestión tienen similitud sobre la longitud total Sólo encuentra regiones locales con el más alto nivel de similitud entre las dos secuencias y alinea estas regiones sin preocuparse por el resto de las secuencias Este enfoque es el más apropiado para alinear secuencias biológicas divergentes que contienen módulos que son similares (dominios o motivos) y de esta forma encontrar patrones conservados en secuencias de ADN o proteínas Incluso las dos secuencias pueden ser de diferentes longitudes
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
31 / 61
Alineamiento de pares de secuencias
Métodos de alineamiento de secuencias
Métodos de alineamiento de secuencias
Alineamiento global de secuencias
Alineamiento local de secuencias
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
32 / 61
Alineamiento de pares de secuencias
Métodos de alineamiento de secuencias
Métodos de alineamiento de secuencias
Los algoritmos de alineamiento, tanto globales como locales son fundamentalmente similares y sólo difieren en la estrategia de optimización utilizada al alinear los residuos similares Ambos tipos de algoritmos pueden estar basados en uno de tres métodos: Matriz de puntos Programación dinámica Método de palabra corta
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
33 / 61
Alineamiento de pares de secuencias
1
Método de matriz de puntos
Alineamiento de pares de secuencias Introducción Evolución de secuencias Homología y similitud de secuencias Similitud e identidad de secuencias Métodos de alineamiento de secuencias Método de matriz de puntos Programación dinámica Tarea
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
34 / 61
Alineamiento de pares de secuencias
Método de matriz de puntos
Método de matriz de puntos
El método de la matriz de puntos es una forma gráfica de comparar dos secuencias utilizando una matriz bidimensional Las secuencias comparadas se escriben en los ejes vertical y horizontal de la matriz La comparación es realizada verificando la similitud entre cada residuo de una secuencia contra los de la otra
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
35 / 61
Alineamiento de pares de secuencias
Método de matriz de puntos
Método de matriz de puntos
Si una coincidencia de residuos es encontrada, un punto se coloca en la gráfica De otra forma, las posiciones de la matriz se dejan en blanco Cuando las dos secuencias tienen regiones substancialmente similares, muchos puntos se alinean para formar líneas diagonales continuas, las cuales revelan el alineamiento de las secuencias
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
36 / 61
Alineamiento de pares de secuencias
Método de matriz de puntos
Método de matriz de puntos
Si hay interrupciones en las líneas diagonales, éstas indican inserciones o eliminaciones Las líneas diagonales paralelas representan regiones repetitivas de las secuencias
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
37 / 61
Alineamiento de pares de secuencias
Método de matriz de puntos
Método de matriz de puntos Ejemplo del método de la matriz de puntos
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
38 / 61
Alineamiento de pares de secuencias
Método de matriz de puntos
Método de matriz de puntos
Cuando este método es usado para comparar secuencias largas genera un alto grado de ruido En la mayoría de los casos hay demasiados puntos en la gráfica, lo que dificulta la identificación del verdadero alineamiento Para reducir el ruido, en vez de usar un solo residuo para verificar la similitud, se emplea (filtrado) una “ventana” de longitud fija que cubre un conjunto de pares de residuos
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
39 / 61
Alineamiento de pares de secuencias
Método de matriz de puntos
Método de matriz de puntos
Con esta técnica de filtrado los puntos solo se dibujan cuando un conjunto de residuos de tamaño igual al de la ventana de una secuencia coincide completamente con el de la otra secuencia Esta técnica ha demostrado ser efectiva reduciendo el nivel de ruido
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
40 / 61
Alineamiento de pares de secuencias
Método de matriz de puntos
Método de matriz de puntos
El método de la matriz de puntos despliega todas las posibles coincidencias de las secuencias Sin embargo, comúnmente el usuario debe construir el alineamiento completo al ir uniendo las diagonales Otra limitación de este método visual de análisis es que carece de rigor estadístico para medir la calidad del alineamiento
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
41 / 61
Alineamiento de pares de secuencias
Método de matriz de puntos
Método de matriz de puntos
Además, el método está restringido solo a alienamiento de pares de secuencias Los siguiente son ejemplos de páginas Web que proveen comparación de pares de secuencias usando matrices de puntos: Dotmatcher http://bioweb.pasteur.fr/seqanal/ interfaces/dotmatcher.html Dottup http://bioweb.pasteur.fr/seqanal/interfaces/ dottup.html Dothelix http: //www.genebee.msu.su/services/dhm/advanced.html MatrixPlot http://www.cbs.dtu.dk/services/MatrixPlot
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
42 / 61
Alineamiento de pares de secuencias
1
Programación dinámica
Alineamiento de pares de secuencias Introducción Evolución de secuencias Homología y similitud de secuencias Similitud e identidad de secuencias Métodos de alineamiento de secuencias Método de matriz de puntos Programación dinámica Tarea
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
43 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica La programación dinámica es un método que determina el alineamiento óptimo de dos secuencias al verificar las coincidencias para todos los posibles pares de caracteres entre las dos secuencias También crea una matriz bidimensional Sin embargo, encuentra un alineamiento en una forma más cuantitativa al convertir la matriz de puntos en una matriz de puntajes para contar las coincidencias y divergencias entre las secuencias Buscando el conjunto de puntajes más altos en esta matriz, es posible obtener de manera confiable el mejor alineamiento
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
44 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica
El método de programación dinámica se compone de 3 pasos fundamentales: 1 2 3
Inicialización Construcción de la matriz de puntajes Rastreo del alineamiento
Veamos un ejemplo de alineamiento de secuencias global utilizando el algoritmo de programación dinámica de Needleman/Wunsch
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
45 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica Ejemplo: Para este ejemplo las dos secuencias a alinear son: G A A T T C A G T T A (secuencia 1) G G A T C G A (secuencia 2) Por lo tanto las longitudes de las secuencias son X = 11 y Y = 7 respectivamente Utilizaremos el siguiente esquema de puntaje simple: Si,j = 1, si el residuo en la posición i de la secuencia uno es el mismo que el de la posición j de la secuencia dos; sino Si,j = 0 (no hay coincidencia) w = 0 (penalidad por hueco)
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
46 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica Inicialización El primer paso consiste en crear una matriz con X + 1 columnas y Y + 1 filas donde X y Y son los tamaños de las secuencias En este ejemplo asumimos que no hay penalidad por huecos (w = 0) por lo que llenamos la primera fila y columna con 0
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
47 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica
Construcción de la matriz de puntajes Se inicia en la esquina superior izquierda y se encuentra el máximo puntaje Mi,j para cada posición i, j Para conocer Mi,j se necesita saber el puntaje de las posiciones Mi−1,j , Mi,j−1 y Mi−1,j−1 y usar la siguiente fórmula: Mi,j = Max[Mi−1,j−1 + Si,j , Mi,j−1 + w, Mi−1,j + w]
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
(3)
48 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica Usando esta información el puntaje para la posición 1,1 en la matriz puede ser calculado En ambas secuencias el primer residuo es G entonces, S1,1 = 1, y como w = 0, entonces M1,1 = Max[M0,0 + 1, M1,0 + 0, M0,1 + 0] = Max[1, 0, 0] = 1 (4)
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
49 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica Como w = 0, el resto de la fila 1 y columna 1 puede llenarse con 1’s Tomemos de ejemplo la fila 1 columna 2 M1,2 = Max[M0,1 + 0, M1,1 + 0, M0,2 + 0] = Max[0, 1, 0] = 1 (5)
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
50 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica Ahora llenemos la columna 2. En la fila 2 que tendra el valor: M2,2 = Max[M1,1 + 0, M2,1 + 0, M1,2 + 0] = Max[0, 1, 0] = 1 (6) Y la columna 2, fila 3: M3,2 = Max[M2,1 + 1, M3,1 + 0, M2,2 + 0] = Max[2, 1, 1] = 2 (7)
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
51 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica
Usando el mismo procedimiento se llena la columna 3
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
52 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica
Después de calcular todos los valores, la matriz de puntajes queda así:
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
53 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica
Rastreo del alineamiento De la matriz anterior observamos que el puntaje máximo del alineamiento es 6 El paso de rastreo del alineamiento determina el alineamiento que lleva a este resultado Éste comienza en la posición MX ,Y de la matriz y verifica sus predecesores directos: Vecino a la izquierda (hueco en secuencia 2) Vecino en la diagonal (coincidencia/no coincidencia) Vecino hacia arriba (hueco en secuencia 1)
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
54 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica Se elige uno de los vecinos (marcados en rojo) Debido a que la celda actual vale 6, el único vecino que es posible elegir es el de la diagonal Lo que da el alineamiento A A
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
55 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica Ahora determinamos cual es el predecesor directo de la celda actual, en este caso la celda roja con el 5
Esto agrega un hueco a la secuencia 2, por lo que el alineamiento actual es: TA _ A Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
56 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica
Una vez más, el predecesor directo produce un hueco en la secuencia 2: TTA _ _ A
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
57 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica
Continuado estos pasos llegamos al siguiente alineamiento: GAATTCAGTTA GGA_ TC_ G_ _ A
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
58 / 61
Alineamiento de pares de secuencias
Programación dinámica
Programación dinámica
Una solución alternativa es el siguiente alineamiento: G_ AATTCAGTTA GG_ A_ TC_ G_ _ A
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
59 / 61
Alineamiento de pares de secuencias
1
Tarea
Alineamiento de pares de secuencias Introducción Evolución de secuencias Homología y similitud de secuencias Similitud e identidad de secuencias Métodos de alineamiento de secuencias Método de matriz de puntos Programación dinámica Tarea
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
60 / 61
Alineamiento de pares de secuencias
Tarea
Tarea
Implemente en el lenguaje de su preferencia el algoritmo de programación dinámica para alineamiento de pares de secuencias visto en clase. El algoritmo recibe como entrada dos secuencias (posiblemente de longitudes diferentes) tomadas de una BD biológica disponible en Internet, una matriz de puntajes y regresa el mejor alineamiento así como su puntaje. Debera entregar el código fuente documentado y un reporte (en Latex) indicando los detalles de su implementación y las instrucciones para utilizarlo Fecha de entrega: 6 de junio antes de las 16h00
Dr. Eduardo R ODRÍGUEZ T. (C INVESTAV)
Alineamiento de pares de secuencias
30 de mayo del 2013
61 / 61