Download Análisis de microarrays
Document related concepts
no text concepts found
Transcript
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