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