Download Análisis de microarrays

Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Algoritmos basados en cúmulos de partı́culas para
el análisis de microarrays de ADN
E. Alba, J. Garcı́a-Nieto y G. Luque
15 de febrero de 2007
1 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
1
Introducción
2
Análisis de microarrays de ADN
3
Algoritmos basados en cúmulos de partı́culas (PSO)
4
PSO para la reordenación de genes en MAs
Esquema de paralelización
5
Experimentos y resultados computacionales
Experimentos: resultados (I)
Experimentos: resultados (II)
Experimentos: resultados (III)
6
Conclusiones y trabajo futuro
2 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Introducción
• Mediante la técnica de microarrays de ADN (MAs) es posible
manejar desde cientos hasta decenas de miles de genes
3 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Introducción
• Mediante la técnica de microarrays de ADN (MAs) es posible
manejar desde cientos hasta decenas de miles de genes
• Por este motivo, son necesarias técnicas de reducción que permitan
agrupar genes con patrones de expresión relacionados
4 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Introducción
• Mediante la técnica de microarrays de ADN (MAs) es posible
manejar desde cientos hasta decenas de miles de genes
• Por este motivo, son necesarias técnicas de reducción que permitan
agrupar genes con patrones de expresión relacionados
• Para este propósito se vienen utilizando técnicas de clustering como
K-means o métodos aglomerativos
5 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Introducción
• Mediante la técnica de microarrays de ADN (MAs) es posible
manejar desde cientos hasta decenas de miles de genes
• Por este motivo, son necesarias técnicas de reducción que permitan
agrupar genes con patrones de expresión relacionados
• Para este propósito se vienen utilizando técnicas de clustering como
K-means o métodos aglomerativos
• Es posible mejorar más aún la calidad de las soluciones que se
obtienen con estos métodos
6 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Introducción
• Mediante la técnica de microarrays de ADN (MAs) es posible
manejar desde cientos hasta decenas de miles de genes
• Por este motivo, son necesarias técnicas de reducción que permitan
agrupar genes con patrones de expresión relacionados
• Para este propósito se vienen utilizando técnicas de clustering como
K-means o métodos aglomerativos
• Es posible mejorar más aún la calidad de las soluciones que se
obtienen con estos métodos
• En este trabajo se propone la utilización de algoritmos basados en
cúmulos de partı́culas (PSO) para realizar una reordenación de los
genes muestreados en un MA
7 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Microarrays
• Un microarray o “chip” de ADN es una plantilla de vidrio (o un
sustrado sólido) en la cual se disponen de manera sistemática
cientos o miles de muestras de moléculas de ADN
• Tras un proceso de hibridación y escaneo de imagen
expresión de la muestra 1
expresión de la muestra 2
expresión de la muestra m
cuantificación de niveles de color
gen 1
1.2
gen 2
1.0
1.1
1.1
1.2
1.0
1.1
0.5
0.2
0.3
0.4
...
0.3
0.4
1.1
0.3
1.3
0.5
1.0
1.0
1.2
1.1
1.2
1.3
1.3
1.2
1.8
1.1
2.2
1.0
3.5
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
-1
-1
gen n
• El objetivo es encontrar un orden óptimo de los genes en el MA
8 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Optimización basada en cúmulos de partı́culas (PSO)
Partı́cula
• Vector Solución (posición)
• Vector Velocidad (dirección)
(0.2, -1.4, 3.5)
(1.0, 10.3, 7.2)
Actualización
vi ← ω · vi + ϕ1 · rand1 · (pBesti − xi ) + ϕ2 · rand2 · (gi − xi )
xi ← xi + vi
Gráficamente
9 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Esquema de paralelización
PSO para la reordenación de genes en MAs
Representación
=1...n
• Microarray M = {gij }ij=1...m
, donde n es el número de genes y m es
el número de muestras por gen
• Solución (Posición): x = (2, 4, 3, 6, 1, 5)
• Velocidad:
v = [(3 → 1), (6 → 6), (1 → 5)]
• Movimiento:
x = (2, 4, 3, 6, 1, 5)
10 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Esquema de paralelización
PSO para la reordenación de genes en MAs
Representación
=1...n
• Microarray M = {gij }ij=1...m
, donde n es el número de genes y m es
el número de muestras por gen
• Solución (Posición): x = (2, 4, 3, 6, 1, 5)
• Velocidad:
v = [(3 → 1), (6 → 6), (1 → 5)]
• Movimiento:
x = (2, 4, 1, 6, 3, 5)
Función de evaluación: distancia euclı́dea con ventana deslizante
P Pmin(l+sw ,n)
• DT (π) = nl=1 i =max(l−s
w (i, l)D[πl , πi ]
w ,1)
Solución
(genes)
W
2
4
5
7
6
3
1
12
8
10
9
13 11
11 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Esquema de paralelización
Pseudocódigo
PSO para permutaciones de enteros
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
S ← InicializarCumulo()
while no se alcance la condición de parada do
for i = 1 to size(S) do
evaluar cada partı́cula xi del cúmulo S
if fitness(xi ) es mejor que fitness(pBesti ) then
pBesti ← xi ; fitness(pBesti ) ← fitness(xi )
end if
if fitness(pBesti ) es mejor que fitness(gi ) then
gi ← pBesti ; fitness(gi ) ← fitness(pBesti )
end if
end for
for i = 1 to size(S) do
vi ← vi ◦ ϕ1 ⊗ (pBesti ⊖ xi ) ◦ ϕ2 ⊗ (gi ⊖ xi )
xi ← xi ⊕ vi
end for
end while
Salida: la mejor solución encontrada
12 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Esquema de paralelización
Operadores
• Diferencia de posiciones (⊖):
genera una nueva velocidad (vector de pares (i → j))
13 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Esquema de paralelización
Operadores
• Diferencia de posiciones (⊖):
genera una nueva velocidad (vector de pares (i → j))
• Suma de velocidades (◦):
genera una nueva velocidad (trasposición de velocidades)
14 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Esquema de paralelización
Operadores
• Diferencia de posiciones (⊖):
genera una nueva velocidad (vector de pares (i → j))
• Suma de velocidades (◦):
genera una nueva velocidad (trasposición de velocidades)
• Producto coeficiente velocidad (⊗):
genera una nueva velocidad (reduce pares)
15 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Esquema de paralelización
Operadores
• Diferencia de posiciones (⊖):
genera una nueva velocidad (vector de pares (i → j))
• Suma de velocidades (◦):
genera una nueva velocidad (trasposición de velocidades)
• Producto coeficiente velocidad (⊗):
genera una nueva velocidad (reduce pares)
• Suma de posición con velocidad (⊕):
genera una nueva posición (movimiento)
16 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Esquema de paralelización
Operadores
• Diferencia de posiciones (⊖):
genera una nueva velocidad (vector de pares (i → j))
• Suma de velocidades (◦):
genera una nueva velocidad (trasposición de velocidades)
• Producto coeficiente velocidad (⊗):
genera una nueva velocidad (reduce pares)
• Suma de posición con velocidad (⊕):
genera una nueva posición (movimiento)
Búsqueda Local
Sucesivas operaciones de intercambio (swap de la posición) sobre la
mejor partı́cula del cúmulo.
17 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Esquema de paralelización
Operadores
• Diferencia de posiciones (⊖):
genera una nueva velocidad (vector de pares (i → j))
• Suma de velocidades (◦):
genera una nueva velocidad (trasposición de velocidades)
• Producto coeficiente velocidad (⊗):
genera una nueva velocidad (reduce pares)
• Suma de posición con velocidad (⊕):
genera una nueva posición (movimiento)
Búsqueda Local
Sucesivas operaciones de intercambio (swap de la posición) sobre la
mejor partı́cula del cúmulo.
• Estos operadores “mantienen las permutaciones”
18 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Esquema de paralelización
Esquema de paralelización
• Arquitectura de esqueletos de código de la biblioteca MALLBA
(versiones paralelas LAN/WAN) disponible en la URL
http://neo.lcc.uma.es/mallba/easy-mallba/index.html
• Modelo descentralizado grano grueso
• Topologı́a de anillo unidireccional
PSO
1
PSO
5
PSO
2
PSO
4
PSO
3
• Intercambio de soluciones: versión sı́ncrona vs. versión ası́ncrona
19 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Experimentos: resultados (I)
Experimentos: resultados (II)
Experimentos: resultados (III)
Experimentos
Instancias
• HERPES: herpes de Kaposi, 106 genes (21 muestra por gen)
• FIBROBLAST: fibroblasto, 517 genes (19 muestras por gen)
• DIAUXIC: salto diauxico, 210 genes (7 muestras por gen)
Parámetros
Parámetro
Tamaño del Cúmulo
Tamaño del Vecindario
Lı́mites de Inercia
Velocidad (Mı́n,Máx)
Frecuencia de Migración
Número de Procesos
Secuencial
100
8
(-10,10)
(0.4,1.4)
1
Paralelo
20
8
(-10,10)
(0.4,1.4)
8
5
- 30 ejecuciones independientes para conseguir confianza estadı́stica
- Cada ejecución realiza 500 iteraciones + búsqueda local en cada
iteración
20 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Experimentos: resultados (I)
Experimentos: resultados (II)
Experimentos: resultados (III)
Experimentos: resultados I
Distancias
Instancia
HERPES
FIBROBLAST
DIAUXIC
Algoritmo
PSO SEQ
PSO LAN SYNC
PSO LAN ASYNC
Memético
PSO SEQ
PSO LAN SYNC
PSO LAN ASYNC
Memético
PSO SEQ
PSO LAN SYNC
PSO LAN ASYNC
Memético
M
500.478
497.459
496.263
1359.680
1359.680
1362.980
355.047
349.232
345.796
-
MV
554.202
559.080
552.345
598.798
1391.060
1362.670
1386.700
1376.804
388.323
381.630
374.734
-
PE
0.00000 %
0.00000 %
0.00000 %
0.01035 %
0.00000 %
0.00718 %
0.00000 %
0.00000 %
0.00000 %
-
E
39800
50000
41900
50000
47000
50000
49700
49900
50000
-
T
707.54 s
1586.71 s
375.03 s
21436.40 s
16652.60 s
26972.40 s
797.55 s
909.14 s
2206.16 s
-
El PSO en su versión paralela ası́ncrona es la que ofrece mejores
resultados
21 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Experimentos: resultados (I)
Experimentos: resultados (II)
Experimentos: resultados (III)
Gráficamente
Distancias
1.400.000
1.200.000
1.000.000
PSO SEQ
800.000
PSO LAN SYNC
600.000
PSO LAN ASYNC
Memético
400.000
200.000
0
HERPES
FIBROBLAST
DIAUXIC
22 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Experimentos: resultados (I)
Experimentos: resultados (II)
Experimentos: resultados (III)
Gráficamente
Evolución
1200
PSO_SEQ
PSO_LAN_SYNC
PSO_LAN_ASYNC
1100
Fitness
1000
900
800
700
600
0
50
100
150
200
250
300
350
400
450
500
Número de iteraciones
23 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Experimentos: resultados (I)
Experimentos: resultados (II)
Experimentos: resultados (III)
Experimentos: resultados II
Speedup/Eficiencia
Instancia
HERPES
FIBROBLAST
DIAUXIC
Speedups1,5
2.299
1.444
2.856
Speedupa1,5
3.952
1.992
2.621
Eficiencias1,5
46 %
28 %
57 %
Eficienciaa1,5
70 %
40 %
52 %
Final
630
1600
500
Eficiencia alrededor del 50 %
La versión paralela ası́ncrona reporta más eficiencia
24 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Experimentos: resultados (I)
Experimentos: resultados (II)
Experimentos: resultados (III)
Experimentos: microarrays iniciales vs. óptimamente
ordenados
HERPES
Inicial
Resultado
25 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Experimentos: resultados (I)
Experimentos: resultados (II)
Experimentos: resultados (III)
Experimentos: microarrays iniciales vs. óptimamente
ordenados
HERPES
Inicial
Resultado
26 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Conclusiones y trabajo futuro
Conclusiones
• Hemos aplicado PSO para la reordenación eficiente de genes en
microarrays de ADN
• Hemos utilizado tres instancias reales de microarrays
• Además, evaluamos el PSO para permutaciones de enteros tanto en
versión secuencial como paralela
• Se mejoran las soluciones obtenidas por otros algortimos que
encontramos en la literatura
Trabajo futuro
• Estudiar nuevas versiones de PSO para permutaciones de enteros
• Evaluar nuevas instancias de microarray y realizar nuevas
comparaciones
• Incorporar funcionalidades de clustering jerárquico
27 / 28
Introducción
Análisis de microarrays de ADN
Algoritmos basados en cúmulos de partı́culas (PSO)
PSO para la reordenación de genes en MAs
Experimentos y resultados computacionales
Conclusiones y trabajo futuro
Preguntas
¡¡¡Gracias por su Atención!!!
28 / 28