Download Heurística Evolutiva-TSP para alineamiento de múltiples secuencias
Document related concepts
Transcript
Heurística Evolutiva-TSP para alineamiento de múltiples secuencias D.Sc. Yván Jesús Túpac Valdivia Ciencia de la Computación 07 de diciembre, 2012 Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 1 / 50 Resumen Este trabajo propone e implementa un método para el problema de alineamiento de múltiples secuencias (MSA), visto un (Travelling Salesman Problem – TSP) donde cada secuencia es vista como una ciudad y el mejor tour de visitas es usado como el orden en que se hará el alineamiento. El mejor orden es encontrado usando un algoritmo evolutivo de orden1 Los resultados de los experimentos son comparados con la heurística star para alineamiento múltiple 1 Published as: Optimizing multiple sequence alignments using traveling salesman problem and order-based evolutionary algorithms. In Proceedings of CIBB 2012, the Ninth International Meeting on Computational Intelligence Methods for Bioinformatics and Biostatistics, Houston, Texas, July 2012 Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 2 / 50 Contenido 1 Alineamiento de secuencias Secuencias ADN y de proteínas Problema de alineamiento Alineamiento global Alineamiento de Múltiples Secuencias 2 Heurísticas para MSA Star Alignment TSP Alignment 3 Solución usando Computación Evolutiva Algoritmos Evolutivos basados en orden Modelo TSP-EA Experimentos y resultados 4 Bibliografía Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 3 / 50 Alineamiento de secuencias Secuencias ADN y de proteínas Alineamiento de secuencias Secuencias de ADN Son sucesiones finitas del alfabeto de nucleótidos {A, C, G, T} que representan la estructura primaria de una molécula de ADN, con capacidad de almacenar y transportar información. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 4 / 50 Alineamiento de secuencias Secuencias ADN y de proteínas Alineamiento de secuencias Secuencias de Aminoácidos También llamadas secuencias peptídicas o secuencias de proteínas, son secuencias de aminoácidos unidos mediante Enlaces Peptídicos que forman las proteínas. Son 20 aminoácidos que forman el siguiente alfabeto {A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y}. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 5 / 50 Alineamiento de secuencias Problema de alineamiento Alineamiento de Secuencias Necesidad de alinear secuencias El alineamiento de secuencias es una forma de “acomodar las secuencias” de DNA o proteínas para identificar regiones que puedan significar relaciones funcionales, estructurales o evolutivas entre las secuencias. Figure: Alineamiento de Secuencias de Hemoglobina (proteína) Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 6 / 50 Alineamiento de secuencias Problema de alineamiento Alineamiento de Secuencias Alineamiento de pares (pairwise alignment) Dados dos strings de diferente longitud, alinearlos significa hacer estas dos secuencias de la misma longitud mediante la inserción de gaps Un gap (-) puede ser insertado en cualquier posición No se permite alinear 2 gaps en una misma columna Ejm. Dadas las cadenas CGACCTA, CGCCTA dos ejemplos “extremos” de alineamiento son: CGACCTA CG-CCTA CGACCTA------------CGCCTA La longitud de dos cadenas alineadas está en [max(m, n), m + n] Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 7 / 50 Alineamiento de secuencias Problema de alineamiento Alineamiento de Secuencias El problema de Alineamiento Mediante la menor inserción posible de gaps, hacer que las secuencias resultantes sean lo más similares posible. Esto caracteriza un problema de optimización Función de score: Se define la siguiente función de score por cada columna alineada. Columna igual diferente gap Score +1 −1 −2 El objetivo es maximizar el score total de todas las columnas resultantes C G A C C T A C G A C C T A C G – C C T - G C G – C C T G 1+1-2+1+1+1-1 = 2 1+1-2+1+1+1-2-2 = -1 Uso de Programación Dinámica [Bellman, 1957] Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 8 / 50 Alineamiento de secuencias Alineamiento global Alineamiento de Secuencias Algoritmo de Alineamiento Global [Needleman and Wunsch, 1970] Dadas las secuencias s y t, usar una matriz Mm+1×n+1 que almacene los valores de los alineamientos de todos los prefijos de s y t. Las posiciones M (0, 0), M (1, 0), . . . , M (m, 0) y M (0, 1), . . . , M (0, n) son conocidas y se rellenan de antemano. Las demás posiciones M (i 6= 0, j 6= 0) serán calculadas usando la siguiente expresión: M (i, j) = max M (i − 1, j − 1) ± 1 M (i − 1, j) − 2 (1) M (i, j − 1) − 2 La posición M (m, n) resultante contendrá el score de alineamiento óptimo entre s y t. Complejidad O(mn) Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 9 / 50 Alineamiento de secuencias Alineamiento global Alineamiento de Secuencias Algoritmo de Alineamiento Global: Ejemplo Alinear s = AAAC y t = AGC s t - A G C A A A C Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 10 / 50 Alineamiento de secuencias Alineamiento global Alineamiento de Secuencias Algoritmo de Alineamiento Global: Ejemplo Alinear s = AAAC y t = AGC t - A - 0 −2 −4 −6 A −2 A −4 A −6 C −8 s G Yván Túpac (C.Sc. – UCSP) C Aplicar la ecuación recursiva: M (i, j) = max M (i − 1, j − 1) ± 1 M (i − 1, j) − 2 M (i, j − 1) − 2 e ir completando los valores faltantes. Clase 01 07 de diciembre, 2012 11 / 50 Alineamiento de secuencias Alineamiento global Alineamiento de Secuencias Algoritmo de Alineamiento Global: Ejemplo Alinear s = AAAC y t = AGC t - A - 0 −2 −4 −6 A −2 A −4 −1 A −6 −3 −2 −1 C −8 −5 −4 −1 s 1 G C −1 −3 0 Yván Túpac (C.Sc. – UCSP) −2 Aplicar la ecuación recursiva: M (i, j) = max M (i − 1, j − 1) ± 1 M (i − 1, j) − 2 M (i, j − 1) − 2 e ir completando los valores faltantes. Clase 01 07 de diciembre, 2012 12 / 50 Alineamiento de secuencias Alineamiento global Alineamiento de Secuencias Algoritmo de Alineamiento Global: Ejemplo Alinear s = AAAC y t = AGC t - A - 0 −2 −4 −6 A −2 A −4 −1 A −6 −3 −2 −1 C −8 −5 −4 −1 s 1 G C −1 −3 0 Yván Túpac (C.Sc. – UCSP) −2 El score es M (m, n) = 1 Aún falta determinar el (los) alineamiento(s) resultantes Clase 01 07 de diciembre, 2012 13 / 50 Alineamiento de secuencias Alineamiento global Alineamiento de Secuencias Algoritmo de Alineamiento Global: Ejemplo Alinear s = AAAC y t = AGC t - A - 0 −2 −4 −6 A −2 A −4 −1 −2 Reconstruir las cadenas respetando las decisiones. A −6 −3 −2 −1 C −8 −5 −4 −1 Una bifurcación significa que hay más de un alineamiento óptimo. s 1 G C −1 −3 0 Yván Túpac (C.Sc. – UCSP) Para obtener los alineamientos: Partir de la posicion M (m, n) y recorrer las decisiones tomadas al aplicar la ecuación (1) Clase 01 07 de diciembre, 2012 14 / 50 Alineamiento de secuencias Alineamiento global Alineamiento de Secuencias Algoritmo de Alineamiento Global: Ejemplo Alinear s = AAAC y t = AGC t - A - 0 −2 −4 −6 A −2 A −4 −1 A −6 −3 −2 −1 C −8 −5 −4 −1 s 1 G C −1 −3 0 Yván Túpac (C.Sc. – UCSP) −2 Los alineamientos óptimos son: AAAC -AGC Clase 01 AAAC AAAC AG-C A-GC 07 de diciembre, 2012 15 / 50 Alineamiento de secuencias Alineamiento de Múltiples Secuencias Alineamiento de Múltiples Secuencias Motivación Se necesita alinear más de dos secuencias simultáneamente por las siguientes razones: Mayor evidencia de la similitud de pares para inferir funcionalidades y/o estructuras Detectar regiones de variabilidad o conservación (imposible con dos secuencias) en una familia de proteínas Es el paso inicial para los siguientes procesos Reconstrucción filogenética Predicción de estructuras secundarias en RNA Construcción de perfiles mediante modelos probabilísticos, de familias de proteínas o señales de ADN. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 16 / 50 Alineamiento de secuencias Alineamiento de Múltiples Secuencias Alineamiento de Múltiples Secuencias Definición [Setubal and Meidanis, 1997] Sean k secuencias S1 , S2 , . . . , Sk , un alineamiento de múltiples secuencias (Multiple Sequence Alignment – MSA) consiste en: Insertar gaps en las cadenas tal que todas las cadenas resulten con la misma longitud. No se permite una columna llena con puros gaps. Sean la siguientes 4 secuencias: Un alineamiento sería: MQPILLLV MLR-LL-MK-ILLLMPPVLILV MQPILLLV MLRLL MKILLL MPPVLILV Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 17 / 50 Alineamiento de secuencias Alineamiento de Múltiples Secuencias Alineamiento de Múltiples Secuencias Ejemplo Para el alineamiento anterior: MQPILLLV MLR-LL-MK-ILLLMPPVLILV ¿Cómo se calcula el score total? Una opción es sumar los alineamientos de todos los posibles pares (Sum of pairs SP). Por ejemplo, para la 4ta columna: SP(I , -, I , V ) = sc(I , -) + sc(I , I ) + sc(I , V )+ sc(-, I ) + sc(-, V ) + sc(I , V ) = −2 + 1 − 1 − 2 − 2 − 1 = −7 Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 18 / 50 Alineamiento de secuencias Alineamiento de Múltiples Secuencias Alineamiento de Múltiples Secuencias Observación A tomar en cuenta No se puede garantizar que el score de un alineamiento sea la suma de todos los scores óptimos por pares. Siempre habrá un par no alineado óptimamente Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 19 / 50 Alineamiento de secuencias Alineamiento de Múltiples Secuencias Alineamiento de Múltiples Secuencias Alineamiento Óptimo de Múltiples Secuencias Sean k secuencias S1 , . . . , Sk todas de longitud n. Si para alinear 2 secuencias (un par) se utiliza una matriz Mn+1×n+1 que almacena todas las soluciones, entonces, Para alinear k secuencias, se necesitará un array k-dimensional con (n + 1)k posiciones. Similar al alineamiento de pares, se debe observar la última columna del alineamiento, habiendo por cada secuencia 2 opciones a efectuar: - Colocar un caracter - Colocar un gap (-) Para las k secuencias se tendrían 2k − 1 posibilidades al excluir la posibilidad de tener sólo gaps). Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 20 / 50 Alineamiento de secuencias Alineamiento de Múltiples Secuencias Alineamiento de Múltiples Secuencias Alineamiento Óptimo de Múltiples Secuencias En resumen, para k secuencias de longitud n, el algoritmo debe realizar: 1 El llenado de un array de (n + 1)k posiciones. 2 Considerar 2k − 1 posibles valores en cada posición 3 Calcular la suma de pares por cada posibilidad k(k+1) . 2 obteniéndose una complejidad computacional de: O(n, k) = (n + 1)k (2k − 1)k 2 (2) La complejidad es exponencial con respecto a la cantidad de cadenas y es un problema NP-Complete. Si k > 10, la búsqueda ya se hace impráctica. Se hace necesario el uso de heurísticas para el problema MSA Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 21 / 50 Heurísticas para MSA Heurísticas para Alineamiento de Múltiples Secuencias Principio de consistencia Dada la complejidad del método exacto por programación dinámica, se debe pensar en métodos de menor complejidad que solucionen el problema de MSA, respetando el principio de consistencia. Principio de Consistencia: Se deben adicionar las secuencias a un alineamiento, una por una, manteniendo consistencia, usando la siguiente regla: “Once a gap, always a gap” Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 22 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment: Propuesto por [Gusfield, 1997], consiste en encontrar la secuencia mejor alineada a las demás (centro) mediante score por pares. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 23 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment: Propuesto por [Gusfield, 1997], consiste en encontrar la secuencia mejor alineada a las demás (centro) mediante score por pares. Se realiza el siguiente proceso: Encontrar los scores de todos los alineamientos por pares formando una matriz de scores S S3 S5 Encontrar el “centro” SC tal que: arg max c X (3) siC i6=C Alinear SC con las demás secuencias respetando el principio de consistencia. Yván Túpac (C.Sc. – UCSP) Clase 01 S2 S1 Centro en S1 S4 07 de diciembre, 2012 23 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Ejemplo: Sean las secuencias S1 , . . . , S5 : S1 S2 S3 S4 S5 Yván Túpac (C.Sc. – UCSP) A A A A A T T T T C T G C C T G G C T G C C A T A Clase 01 C C A C C A A T T C T T T T T T T T 07 de diciembre, 2012 24 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Ejemplo: Sean las secuencias S1 , . . . , S5 : S1 S2 S3 S4 S5 A A A A A T T T T C T G C C T G G C T G C C A T A C C A C C A A T T C T T T T T T T T Encontrar el centro SC con máximo score por pares, usando [Needleman and Wunsch, 1970] Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 24 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Ejemplo: Se calcula la matriz de scores por pares: S1 S2 S3 S4 S5 S1 × 7 −2 0 −3 2 S2 S3 S4 S5 7 −2 0 −3 × −2 0 −4 −2 × 0 −7 0 0 × −3 −4 −7 −3 × −1 −11 −3 −17 X Se encuentra el centro aplicando arg max c 2 1 −11 −3 −17 siC = 1. i6=C Por lo tanto, el centro será S1 Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 25 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Ejemplo: Se obtiene las secuencias alineadas con S1 : S1 A T T G C C A T Yván Túpac (C.Sc. – UCSP) Clase 01 T - - 07 de diciembre, 2012 26 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Ejemplo: Se obtiene las secuencias alineadas con S1 : S1 A T T G C C A T S2 A T G G C C A T Yván Túpac (C.Sc. – UCSP) Clase 01 T T - - 07 de diciembre, 2012 26 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Ejemplo: Se obtiene las S1 S2 S3 secuencias alineadas A T T G C A T G G C A T C - C Yván Túpac (C.Sc. – UCSP) Clase 01 con C C A S1 : A T A T A T T T T T T 07 de diciembre, 2012 26 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Ejemplo: Se obtiene las S1 S2 S3 S4 secuencias alineadas A T T G C A T G G C A T C - C A T C T T Yván Túpac (C.Sc. – UCSP) Clase 01 con C C A C S1 : A A A - T T T T T T T T T - T - 07 de diciembre, 2012 26 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Ejemplo: Se obtiene las secuencias alineadas con S1 : S1 A T T G C C A T T S2 A T G G C C A T T S3 A T C - C A A T T S4 A T C T T C - T T S5 A C T G A C C - Por el principio de consistencia, cualquier gap que se es retirado. Yván Túpac (C.Sc. – UCSP) Clase 01 - - T T - - introduce ya no 07 de diciembre, 2012 26 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Complejidad Computacional: Dominada por el cálculo de los alineamientos por pares. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 27 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Complejidad Computacional: Dominada por el cálculo de los alineamientos por pares. Se realizan k(k−1) alineamientos por pares, donde cada alineamiento 2 tiene complejidad n 2 , por usar el alineamiento global para secuencias de tamaño n. La complejidad del cálculo de los alineamientos por pares es O(n, k) = k 2 n 2 . Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 27 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Complejidad Computacional: Dominada por el cálculo de los alineamientos por pares. Se realizan k(k−1) alineamientos por pares, donde cada alineamiento 2 tiene complejidad n 2 , por usar el alineamiento global para secuencias de tamaño n. La complejidad del cálculo de los alineamientos por pares es O(n, k) = k 2 n 2 . Sea l el tamaño de la secuencia más grande, la complejidad total de cálculo será O(n, k) = k 2 n 2 + k 2 l que es un tiempo polinomial Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 27 / 50 Heurísticas para MSA Star Alignment Heurísticas para Alineamiento de Múltiples Secuencias Star Alignment Complejidad Computacional: Dominada por el cálculo de los alineamientos por pares. Se realizan k(k−1) alineamientos por pares, donde cada alineamiento 2 tiene complejidad n 2 , por usar el alineamiento global para secuencias de tamaño n. La complejidad del cálculo de los alineamientos por pares es O(n, k) = k 2 n 2 . Sea l el tamaño de la secuencia más grande, la complejidad total de cálculo será O(n, k) = k 2 n 2 + k 2 l que es un tiempo polinomial En realidad no se está optimizando el criterio de alineamiento por pares, pero esta heurística es un buen trade-off entre optimización y practicidad. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 27 / 50 Heurísticas para MSA TSP Alignment Heurísticas para Alineamiento de Múltiples Secuencias TSP Alignment Propuesto por [Korostensky and Gonnet, 1999] para modelar el problema MSA como un TSP (Travelling Salesman Problem) donde cada secuencia es como una de las ciudades del TSP y la distancia se basa en el score del alineamiento de los respectivos pares. Se define una matriz de distancias D entre secuencias calculada usando los scores S, donde: dij = smax − sij + 1 (4) donde sij = score(Si , Sj ) y smax es el máximo score en S Se trata de encontrar el “orden de visitas” que minimice la distancia recorrida. Es decir que la solución al problema MSA es la solución al TSP Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 28 / 50 Heurísticas para MSA TSP Alignment Heurísticas para Alineamiento de Múltiples Secuencias TSP Alignment Propuesto por [Korostensky and Gonnet, 1999] para modelar el problema MSA como un TSP (Travelling Salesman Problem) donde cada secuencia es como una de las ciudades del TSP y la distancia se basa en el score del alineamiento de los respectivos pares. S3 s35 S5 s13 s23 s34 S2 s12 s25 s15 S1 Tour de mı́nima distancia s14 s45 s24 S4 Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 29 / 50 Solución usando Computación Evolutiva Algoritmos Evolutivos basados en orden Algoritmos Evolutivos basados en orden Algoritmos evolutivos con individuos de tipo permutación: Definición Algoritmos Evolutivos basados en Orden Sea Φt una población de tamaño m definida como un conjunto Φt = {φi }m i=1 para la generación t. Un individuo φi ∈ Φt es un conjunto de elementos φi = {φi (1), . . . , φi (n)}, cuyos valores provienen de un alfabeto N = {1, 2, . . . , n} ⊂ N. Si φi (p) es el valor del p-ésimo elemento de φi , se cumple que φi (p) 6= φi (q) ⇔ p 6= q . Es claro que para dos individuos φi , φj , con i 6= j, no necesariamente se cumple φi (p) = φj (p). Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 30 / 50 Solución usando Computación Evolutiva Algoritmos Evolutivos basados en orden Algoritmos Evolutivos basados en orden Operadores evolutivos de orden i Mutación de desorden: Sea φ1 = {φ1 (1), . . . , φ1 (n)} un individuo seleccionado y ϕ ⊆ φ1 una sublista. El descendiente φ01 se forma desordenando los elementos de la sublista ϕ sublista ϕ φ1 = 1 2 3 4 5 6 7 8 sublista desordenada φ01 = 1 2 3 6 7 5 4 8 Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 31 / 50 Solución usando Computación Evolutiva Algoritmos Evolutivos basados en orden Algoritmos Evolutivos basados en orden Operadores evolutivos de orden ii Mutación de orden: Sea φ1 = {φ1 (1), . . . , φ1 (n)} un individuo seleccionado, y φ(a), φ(b), a < b dos elementos de φ1 . El descendiente φ01 se forma insertando φ1 (b) antes de φ1 (a) φ(a) φ(b) φ1 = 1 2 3 4 5 6 7 8 φ(b)φ(a) φ01 = 1 2 7 3 4 5 6 8 Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 32 / 50 Solución usando Computación Evolutiva Algoritmos Evolutivos basados en orden Algoritmos Evolutivos basados en orden Operadores evolutivos de orden iii Mutación de posición: Sea φ1 = {φ1 (1), . . . , φ1 (n)} un individuo seleccionado, y φ(a), φ(b), a < b dos elementos de φ1 . El descendiente φ01 se forma intercambiando los valores φ1 (a) y φ1 (b). φ(a) φ(b) φ1 = 1 2 3 4 5 6 7 8 φ(b) φ(a) φ01 = 1 2 7 4 5 6 3 8 Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 33 / 50 Solución usando Computación Evolutiva Algoritmos Evolutivos basados en orden Algoritmos Evolutivos basados en orden Operadores evolutivos de orden iv Cruce uniforme de orden: Sean φ1 ,φ2 dos individuos seleccionados. Un descendiente φ01 se forma haciendo lo siguiente: - Generar un patrón mk de n bits binarios. - Completar φ01 con los genes φ1 (i), i = 1, . . . , n cuya máscara es mk (i) = 1. - Crear una sublista ϕ usando los elementos restantes de φ1 . - Ordenar la sublista ϕ con el orden de sus elementos en φ2 . - Completar los espacios faltantes en φ1 con la lista ϕ reordenada. El otro descendiente φ02 se compondrá con los mismos pasos, pero en φ2 y usando el patrón negado mk . Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 34 / 50 Solución usando Computación Evolutiva Algoritmos Evolutivos basados en orden Algoritmos Evolutivos basados en orden Operadores evolutivos de orden iv Cruce uniforme de orden: φ1 = 1 2 3 4 5 6 7 8 φ2 = 8 6 4 2 7 5 3 1 φ01 = − 2 3 − 5 6 − − φ02 = 8 − − 2 − − 3 1 mk = 0 1 1 0 1 1 0 0 genes faltantes en φ1 : {1, 4, 7, 8}, ordenados por φ2 → {8, 4, 7, 1} genes faltantes en φ2 : {6, 4, 7, 5}, ordenados por φ1 → {4, 5, 6, 7} φ01 = 8 2 3 4 5 6 7 1 φ02 = 8 4 5 2 6 7 3 1 Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 35 / 50 Solución usando Computación Evolutiva Modelo TSP-EA Modelo TSP-EA Resolviendo el problema MSA como TCP con AE El uso de algoritmos de TSP fue propuesto por [Wan, 2002] para resolver el problema MSA. El uso de algoritmos evolutivos de orden para apoyar en la solución del TSP fue propuesto por [Banda et al., 2012], y se describe como sigue: 1 Se alinean todos los pares (Si , Sj ) usando Needleman-Wunsch construyendo la matriz S de scores. 2 Construir la matriz D usando la Eq.(4). 3 Iniciar el algoritmo evolutivo de orden para resolver el TSP, encontrando el tour de distancia mínima. 4 Con el mejor tour, construir el alineamiento múltiple aplicando el principio de consistencia: once a gap, always a gap, y luego calcular la suma de pares para obtener el score final. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 36 / 50 Solución usando Computación Evolutiva Modelo TSP-EA Modelo TSP-EA Resolviendo el problema MSA como TCP con AE 1 Representación El algoritmo evolutivo de orden puede naturalmente representar un problema de vendedor viajero haciendo que el individuo φi = {φi (1), . . . , φi (k)} ∈ Φ represente un tour aleatorio. 2 Evaluación Para evaluar el tour φi se calcula la distancia total recorrida para el orden dado por el individuo φ = {φ(1), φ(2), . . . , φ(n)} usando la matriz de distancias mediante la siguiente expresión: f (φi ) = n X (5) dφi (j−1)φi (j) j=2 donde no se considera el recorrido de retorno de la última ciudad a la primera del tour dφi (n)φi (1) , por no ser necesario. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 37 / 50 Solución usando Computación Evolutiva Modelo TSP-EA Modelo TSP-EA Resolviendo el problema MSA como TCP con AEO Sequences S = {s1 , . . . , sk } s1 = TACTACTCAGACTCAGTGAAGGGCC... s2 = CGGTTTGTCTTCTCCTTGGACACCT... .. . sk = CGAGTTACCATATCAGTAGACACGT... Calculate pairwise distances sij = score(si , sj ) dij = max sij − sij + 1 i,j Best alignment order Order-based evolutionary algorithm Φ0 : population of alignment orders Evaluate Φ0 (tour distance) Yván Túpac (C.Sc. – UCSP) φ(k)dk−1,k . . . while ∼(end condition) Selection and Reproduction φt+1 Clase 01 Evaluate Φt+1 (tour distance) d34 dk1 φ(1) φ(3) d12 φ(2) d23 validated by sum-of-pairs 07 de diciembre, 2012 38 / 50 Solución usando Computación Evolutiva Experimentos y resultados Modelo TSP-EA Experimentos y resultados Se realizaron experimentos usando una base de datos de secuencias ADN extraída de (NCBI)2 . De la base, se seleccionaron 500 secuencias para ser analizadas. Cada secuencia contiene de 80-120 nucleótidos. Los experimentos fueron hechos usando 50 grupos que constan de 10 secuencias cada uno. 2 National Center for Biotechnology Information, disponible en http://www.ncbi.nlm.nih.gov/ Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 39 / 50 Solución usando Computación Evolutiva Experimentos y resultados Modelo TSP-EA Experimentos y resultados Ejemplo de un grupo de 10 secuencias usadas AGCATCCCAGCCAGGTTCAGTGGCAGTGGGTCTGGGACAGACTTCACTCTCACCAT... AGATTCACCATCTCCAGAGACAATTCCAAGAACACGCTGTATCTTCAAATGGGCAG... GGGGTCCCATCAAGGTTCAGCGGCAGTGGATCTGGGACAGATTTCACTCTCACCAT... CGATTCACCATCTCCAGAGACAATTCCAAGAACACGCTGTATCTGCAAATGAACAG... CGATTCACCATCTCCAGAGACAACGCCAAGAACTCACTGTATCTGCAAATGAACAG... AGATTCACCATCTCCAGAGACAATTCCAAGAACACGCTGTATCTTCAAATGAACAG... AGAGTCACCATTACCAGGGACACATCCGCGAGCACAGCCTACATGGAGCTGAGCAG... CTCGAGTCAGGGGCTGAACTGGCAAAACCTGGGGCCTCAGTAAAGATGTCCTGCAA... CGATTCACCATCTCCAGAGACAACAGCAAAAACTCCCTGTATCTGCAAATGAACAG... AGGTTCACCATCTCCAGAGATGATTCAAAGAACACGGCGTATCTGCAAATGAACAG... Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 40 / 50 Solución usando Computación Evolutiva Experimentos y resultados Modelo TSP-EA Experimentos y resultados Se empleó la siguiente parametrización del modelo evolutivo para la búsqueda del mejor camino TSP Yván Túpac (C.Sc. – UCSP) Parameter Value Generaciones Población Probabilidad de crossover Probabilidad de mutación 100 100 70% 30% Clase 01 07 de diciembre, 2012 41 / 50 Solución usando Computación Evolutiva Experimentos y resultados Modelo TSP-EA Experimentos y resultados Luego de las diversas iteraciones (100 generaciones) se obtuvo el siguiente resultado: Yván Túpac (C.Sc. – UCSP) Score Star TSP-EA Maximum Minimum Average -1816 -7505 -4690 -566 -6410 -3319 Clase 01 07 de diciembre, 2012 42 / 50 Solución usando Computación Evolutiva Experimentos y resultados Modelo TSP-EA Experimentos y resultados Ejemplos de alineamientos obtenidos: Secuencias originales TACTATGCAGACTCCGTGACGGGCCGATTCGCCATCTCCAGAGACAATTCCAAGAACACTCT ACCTTCAGTAGCTATGCTATGCACTGGGTCCGCCAGGCTCCAGGGAAGGGACTGGAATATGT CGAGTCACCATATCAGTAGACACGTCCAAGAACCAGTTCTCCCTGAAGCTGAGCTCTGTGAC AGGCTCACCATCTCCAAGGACACCTCCAAAAACCAGGTGGTCCTTACAATGACCAACATGGA GGGGTCCCATCAAGGTTCAGCGGCAGTGGATCTGGGACAGAATTCACTCTCACCATCAGCAG GGAGTGCCAGATAGGTTCAGTGGCAGCGGGTCAGGGACAGATTTCACACTGAAAATCAGCCG CAGGTCACCATCTCAGCCGACAAGTCCATCAGCACCGCCTACCTGCAGTGGAGCAGCCTGAA GGGGTCCCATCAAGGTTCAGCGGCAGTGGATCTGGGACAGAATTCACTCTCACCATCAGCAG AGAGTCACCATGACCACAGACACATCCACGAGCACAGCCTACATGGAGCTGAGGAGCCTGAG GGGGTCCCATCAAGGTTCAGCGGCAGTGGATCTGGGACAGATTTCACTCTCACTATCAGCAG Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 43 / 50 Solución usando Computación Evolutiva Experimentos y resultados Modelo TSP-EA Experimentos y resultados Ejemplos de alineamientos obtenidos: Secuencias alineadas con Star alignment TACTAT–-GCA–-GACTCCGTGACGGG-CC-G–ATT-C-GC–CATCTCCAGAGACAATTCCACCTTCAGT-A–-GCTATGCT-AT-G-CA-CT-GGGTCC-GCCAGGCTCC-A––GGGAA–-G CGAGTC–ACC––AT-A–-T-CAGTA-G–A–C–-A-CG–TCC-AAGAACC-AG-T––-TCTCC AGGCTCA-CC-ATCTCCAAGGA-CA-CC-TC–C–AAA-A––-ACCAGGTG–-G––T-C–C–GGGGTC––CC––ATCAAGGTTCAGCG-G-C–A––-GT–GGAT-CTGGGACAGA-A––-TTCA GGAGTG–CCA––GATAGGTTCAGTGG-CA-G–C–-G-GG–TCA-GGGACAGATT-T–– -CACAC–-TG–-AA–AATCAGCCGGGTGGA–G–GCTG–AG–GATGTTGGGGTTTATTA–CTG CAGGTC–-ACC––ATC––T-CAGCC-GAC–AA––GT–CCAT-CAGC-ACCGC-C––-TAC-C GGGGTC––CC––ATCAAGGTTCAGCG-G-C–A––-GT–GGAT-CTGGGACAGA-T––-TTCA AGAGTC–-ACC––ATGACCA–CAGAC–AC–-A––-T–CCA–CGAGCACAGC-C––-TACA–– Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 44 / 50 Solución usando Computación Evolutiva Experimentos y resultados Modelo TSP-EA Experimentos y resultados Ejemplos de alineamientos obtenidos: Secuencias alineadas con TSP-AG TACTATGCAGACTCCGTGACGGGCCGATTCGCCAT––––CTCCAGAGACAATTCCAAGAACA –––––––-ACCTTCAGTAGCTATGCTATGCACTGGGTCCGCCAGGCTCCAGGGAAGGGACTG ––––––––––––CGAGTCACCAT––––ATCAGTAGACACGTCCAAGAAC-CAGTTCTC–-CC ––––––––––––AGGCTCACCAT––––CTCCAAGGACACCTCCA–AAAACCAG-GTGGTCCT –––––––––––GGGG–-TCCCAT–-CAAGGTTCAGC-GGCAGTGGATCTGGGAC-AGAATTC –––––––––––GGAG–-TGCCAG–-ATAGGTTCAGT-GGCAGCGGGTCAGGGAC-AGATTTC –––––––––––-CAGG-TCACCAT––––CTCAGCCGACAAGTCCATCAGCACCGC-CTA–-C –––––––––––GGGG–-TCCCAT–-CAAGGTTCAGC-GGCAGTGGATCTGGGAC-AGAATTC ––––––––––––AGAGTCACCAT––––GACCACAGACACATCCACGAGCACAGC-CTA–-CA –––––––––––GGGG–-TCCCAT–-CAAGGTTCAGC-GGCAGTGGATCTGGGAC-AGATTTC Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 45 / 50 Solución usando Computación Evolutiva Experimentos y resultados Modelo TSP-EA Conclusiones Se presentó una propuesta de uso de modelos evolutivos para solucionar el problema TSP aplicado a alineamiento de múltiples secuencias Se usó una medida de distancia adecuada a los enfoques TSP. Aunque un problema TSP no considera la jerarquía dada por un arbol (alineamiento progresivo) muestra buenos resultados, siendo estos superiores al modelo de alineamiento estrella y comparables con modelos progresivos. Se propone como trabajo futuro utilizar las características de individuos con jerarquía en árbol de los modelos de Programación Genética [Koza, 1989] para buscar el mejor árbol de alineamientos, y comparar con el algoritmo de alineamiento progresivo [Feng and Doolittle, 1987] Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 46 / 50 Bibliografía Bibliografía I Banda, J. D., Chuctaya, J. H., and Túpac, Y. J. (2012). Optimizing multiple sequence alignments using traveling salesman problem and order-based evolutionary algorithms. In Proceedings of CIBB 2012, the Ninth International Meeting on Computational Intelligence Methods for Bioinformatics and Biostatistics. Bellman, R. E. (1957). Dynamic Programming. Princeton University Press, Princeton NJ. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 47 / 50 Bibliografía Bibliografía II Feng, D.-F. and Doolittle, R. (1987). Progressive sequence alignment as a prerequisitetto correct phylogenetic trees. Journal of Molecular Evolution, 25:351–360. 10.1007/BF02603120. Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 48 / 50 Bibliografía Bibliografía III Korostensky, C. and Gonnet, G. (1999). Near optimal multiple sequence alignments using a traveling salesman problem approach. In String Processing and Information Retrieval Symposium, 1999 and International Workshop on Groupware, pages 105–114. Koza, J. R. (1989). Hierarchical genetic algorithms operating on populations of computer programs. In Sridharan, N. S., editor, Proceedings of the 11th International Joint Conference on Artificial Intelligence, pages 768–774. Morgan Kaufmann, San Mateo, California. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 49 / 50 Bibliografía Bibliografía IV Needleman, S. B. and Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443–453. Setubal, J. C. and Meidanis, J. (1997). Introduction to computational molecular biology. Boston: PWS Publishing Company. Wan, X. (2002). Multiple sequence alignment using traveling salesman problem algorithms. Yván Túpac (C.Sc. – UCSP) Clase 01 07 de diciembre, 2012 50 / 50