Download Heurística Evolutiva-TSP para alineamiento de múltiples secuencias

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