Download Algoritmos de biclustering

Algoritmos de biclustering Rodrigo Santamaría 2012 Biclustering Rodrigo Santamaría 1. 
2. 
3. 
4. 
5. 
Expresión gené>ca Algoritmos de biclustering Validación Visualización Herramientas Biclustering EXPRESIÓN GENÉTICA Expresión gené>ca DNA
transcription
mRNA
translation
Protein
•  La tecnología de microarrays se basa en el dogma central de la biología molecular •  Mide los niveles de transcripción de mRNA en un determinado caso de estudio •  El nivel de transcripción NO es equivalente al nivel de expresión, aunque se suele hacer dicha asunción •  La degradación del mRNA y otros procesos pos-­‐
transcripcionales influyen en la expresión y no son cuan>ficables con microarrays Tecnología de microarray mRNA
microarray chip
Con la tecnología de microarray se “imprimen” las secuencias biológicas en un chip ~ De manera que podemos cuan>ficar el nivel de transcripción en una matriz numérica Microarray •  En cada celda de un chip se “pegan” miles de copias de un segmento de mRNA (sonda) •  Celdas dis>ntas con>enen secuencias de mRNA dis>ntas •  Todas las celdas con>enen el mismo nº de segmentos •  Se prepara una muestra con mRNA de nuestro caso de estudio •  La muestras se marcan con una e>queta fluorescente •  Nuestra muestra de estudio tendrá un número variable de mRNAs de cada segmento, según cuánto se transcriba Hibridación: proceso por el que dos cadenas de RNA complementarias se combinan por atracción bioquímica Análisis de la imagen: conversión de la can>dad de secuencias hibridadas (con e>queta fluorescente) en una intensidad de luz (un número) Matriz de expresión h1 d1 condi>ons h1 h2 d1 d2 • 
h2 d2 probes • 
• 
healthy pa>ents diseased pa>ents Matriz de expresión: cada matriz de intensidad se “es>ra” a una columna de la matriz de expresión Columna: condiciones (arrays, ensayos, casos, muestras, factores experimentales) Fila: sondas o conjuntos de sondas. Se resumirán en genes en el preprocesamiento Matriz de expresión condi>ons h1 h2 d1 d2 genes 103-­‐4 genes 101-­‐2 condi>ons Una matriz de expresión >ene un tamaño considerable à necesidad de métodos informá>cos para su análisis Análisis de datos de microarray ¿Qué genes influyen en el cáncer de mama? Decidir sobre los pacientes y los controles (edad, grado de la enfermedad, etc.) Construir chips de microarray con las muestras recogidas Conver>r la información del microarray a una matriz numérica analizable Realizar análisis inferenciales o exploratorios Validar los resultados a par>r del conocimiento existente y del diagnós>co en nuevos casos Análisis de datos de microarray expresión Problema biológico Generación de datos y procesamiento de la tecnología Análisis informá>co Confirmación y aplicación biológica Biclustering ALGORITMOS DE BICLUSTERING Eisen et al. 1998 Respuesta de 8600 genes humanos a la presencia de suero a lo largo del >empo Clustering de los genes cuya expresión cambia por un factor 3x en 2+ puntos de >empo •  A) Biosíntesis del colesterol •  B) Ciclo celular •  C) Respuesta inmediata-­‐temprana •  D) Señalización y angiogénesis •  E) Curación de heridas y remodelación de tejido Biclustering 1.  La ac>vación de un gen puede deberse a varias causas 2.  Los genes colaboran bajo una condiciones pero no bajo otras 1 Buscamos grupos solapables de genes con expresión similar bajo algunas condiciones 2 2 Algoritmos de biclustering ¿Qué buscamos? Tipos de bicluster ¿Cómo lo buscamos? Estrategias de biclustering Tipos de bicluster •  constante •  valor coherente (adi>vo) –  o factor de desplazamiento •  valor coherente (mul>plica>vo) –  o factor de escala •  evolución coherente evolución coherente valor coherente constante Estrategias de biclustering Estrategias de biclustering •  Two-­‐way clustering –  Cluster de filas y de columnas combinado para producir biclusters (efecto cuadrícula) •  Divide y vencerás –  Resolver el problema en submatrices –  Combinar resultados parciales para la solución •  Búsqueda itera[va avariciosa –  Resolución local del problema –  Incrementar itera>vamente la solución local Estrategias de biclustering •  Enumeración exhaus[va –  Búsqueda de cada bicluster posible, dado un determinado criterio •  Iden[ficación de parámetros de distribución –  Asume que los datos siguen un modelo estadís>co –  Ajusta los parámetros del modelo a los datos mediante una aproximación itera>va Algunos algoritmos Algoritmo Biclusters Estrategias Año Cheng & Church Valor coherente (adi>vo) Búsqueda avariciosa Modelo estadís>co 2000 Bimax Constante Divide y vencerás Enumeración exhaus>va 2006 ISA Valor coherente (adi>vo) Búsqueda avariciosa 2003 SAMBA Evolución coherente Búsqueda avariciosa Modelo estadís>co 2004 •  Analizados en dis>ntas revisiones/intercomparaciones –  U>lizados frecuentemente –  Cubren varios >pos y estrategias Cheng & Church •  Define un bicluster coherente adi>vo como –  aij = factorColumnaj + factorFilai – ruido •  El residuo rij es la diferencia entre el valor real y el del modelo –  aij = rij+factorColumnaj + factorFilai – ruido •  Cuanto más bajo sea el residuo, más coherente será el bicluster –  La estrategia busca minimizar residuos Cheng & Church •  Primer algoritmo de biclustering para matrices de expresión •  Aproximación muy extendida •  Devuelve muchos biclusters •  Malos resultados en intercomparaciones Bimax •  Convierte la matriz a una matriz binaria –  Si aij > T à a’ij=1; si no à a’ij=0 •  Busca todas las posibles submatrices de 1s en A’, mediante reordenaciones =0 =1 Bimax •  Exhaus>vo •  Rápido (si A’ >ene pocos 1s) •  Simplifica demasiado el problema •  Devuelve muchos biclusters SAMBA •  Sta>s>cal-­‐Algorithmic Method for Biclustering Analysis •  Busca módulos: grupos de genes correlacionados en dis>ntas situaciones –  No sólo expresión génica! –  Test de significa>vidad estadís>ca (p-­‐valores) SAMBA •  Permite integrar dis>ntos >pos de conocimiento •  Las evidencias biológicas pueden predisponer al algoritmo hacia un resultado Algoritmos de biclustering •  Ventajas –  Se adaptan mejor al comportamiento biológico teórico •  Desventajas –  Resultados más complejos •  Solapamiento, división de condiciones –  Métodos más heterogéneos •  Falta de estándares Bibliograra • 
• 
• 
• 
• 
• 
Revisión: S. Madeira and A. Oliveira. Biclustering algorithms for biological data analysis: a survey. IEEE/ACM Transac5ons of Computa5onal Biology and Bioinforma5cs, 1(1):24–45, 2004. Cheng&Church: Y. Cheng and G. M. Church. Biclustering of expression data. Proc. Int’l Conf Intell Syst Mol Biol., 8:93–103, 2000. Bimax e intercomparación: A. Prelic, S. Bleuer, P. Zimmermann, A. Wille, P. Bühlmann, et al. A systema>c comparison and evalua>on of biclustering methods for gene expression data. Bioinforma5cs, 22(9):1122–1129, 2006. ISA: S. Bergmann, J. Ihmels, and N. Barkai. Itera>ve signature algorithm for the analysis of large-­‐scale gene expression data. Phys. Rev. E, 67(3):031902, 2003. SAMBA: A. Tanay, R. Sharan, M. Kupiec, and R. Shamir. Revealing modularity and organiza>on in the yeast molecular network by inte-­‐ grated analysis of highly heterogeneus genomewide data. Proceedings of the Na5onal Academy of Sciences of the United States of America, 101(9):2981–2986, 2004. Plaid model: H.L.Turner, T.C.Bailey, W.J.Krzanowski, and C.A.Hemingway. Biclustering models for structured microarray data. IEEE/ACM Transac5ons on Computa5onal Biology and Bioinforma5cs, 2(4):316– 329, 2005. Biclustering VALIDACIÓN Validación •  Cómo determinar qué algoritmo es mejor –  Dis>ntas estrategias –  Dis>ntas definiciones de bicluster –  Dis>ntos problemas biológicos –  Información biológica en evolución •  Validación externa –  basada en información adicional •  Validación interna –  basada en la estructura interna de los datos Validación externa =biclusters que sabemos que están =biclusters recuperados por un algoritmo •  Sensibilidad: recuperar lo importante •  Especificidad: discriminar lo aleatorio sólo para datos sinté5cos Validación externa (biológica) • 
• 
• 
¿B2 es peor que B1? ¿Qué pasa si un bicluster es muy grande (B~G)? ¿Qué pasa si con el >empo se descubren/descartan genes cancerígenos (C varía)? Validación interna •  Medidas que determinen la calidad del biclustering desde el punto de vista de su estructura interna •  Por ej. basadas en la correlación o modelos >po Cheng & Church Validación: conclusiones •  Validación externa –  Sinté>ca: precisa pero no para casos reales –  Biológica: precisa pero desviada hacia información a priori y en constante evolución •  Validación interna –  Menos precisa pero independiente de fuentes externas Validación: conclusiones •  Compromiso entre –  Métodos que descubren muchas cosas nuevas •  pero quizás incorrectas –  Métodos que confirman lo ya conocido •  pero no aportan nada nuevo validación interna validación biológica Biclustering VISUALIZACIÓN Visualización de información Visualización de la información Visualización de la información Visualización de biclusters •  Reordenación –  Barkow et al. 2006 •  Individual Visualización de biclusters •  Reordenación y duplicación –  Grothaus et al. 2006 •  Visualización simultánea –  Ambigüedades Visualización de biclusters •  Conjuntos solapados –  Santamaría et al. 2007 Visualización de biclusters •  Localización mediante simulación de fuerzas –  Atracción de nodos conectados –  Repulsión de nodos desconectados Biclustering Bimax en Chen et al., 2003 Global transcrip5onal responses of fission yeast to environmental stress Visualización de biclusters Método Biclusters Niveles de múl[ples expresión Relación entre biclusters Exac[tud Reordenación No Sí No Exacta Reordenación y replicación Sí Sí No Ambigua Conjuntos solapados Sí No Sí Inexacta Biclustering HERRAMIENTAS Herramientas •  Proporcionan un entorno gráfico para realizar un análisis de biclustering –  Cargar matrices de expresión •  E información biológica relacionada –  Realizar biclustering •  También preprocesamiento y otras opciones de análisis –  Presentar resultados •  Mapas de calor, coordenadas paralelas, gráficas, etc. Herramientas Herramienta Biclustering Visualización Interacción Preprocesado Otros HCE No Heatmap Coordenadas paralelas Sca•er plots Alta Sí Clustering jerárquico EXpander SAMBA Heatmap Baja Sí Clustering jerárquico y k-­‐medias BicAT Bimax, CC, ISA, Heatmap Xmo>fs, OPSM Coordenadas paralelas Baja Básico BicOverlapper Bimax, CC, ISA, Heatmap Xmo>fs, Plaid Coordenadas paralelas Word cloud Conjuntos Redes Alta No -­‐ Recuperación de anotaciones Visualización de redes BicOverlapper •  Los datos de expresión no están solos –  Existe información sobre cada gen •  Funcional •  Relacional –  Cada condición está caracterizada •  Expresión, biclustering e información biológica Bibliograra • 
• 
• 
• 
• 
• 
• 
Intercomparación: A. Prelic, S. Bleuer, P. Zimmermann, A. Wille, P. Bühlmann, et al. A systema>c comparison and evalua>on of biclustering methods for gene expression data. Bioinforma5cs, 22(9):
1122–1129, 2006. Validación interna: Santamaría, R.; Quintales, L. and Therón, R. (2007), Methods to bicluster valida>on and comparison in microarray data, in Lecture Notes in Computer Science. IDEAL 2007, pp. 780–789. Visualización de la información: B. Fry. Computa>onal Informa>on Design. Ph.D. thesis, MIT, 2004. URL h•p://acg.media.mit.edu/people/fry/phd/. Visualización de la información: C. Ware. Informa>on Visualiza>on: Percep>on for Design. Diane Cerra, 2nd edi>on, 2004. BicAT: S. Barkow, S. Bleuer, A. Prelic, P. Zimmermann, and E. Zitzler. Bicat: a biclustering analysis toolbox. Bioinforma5cs, 22(10):1282– 1283, 2006. Expander: R. Shamir, A. Maron-­‐Katz, A. Tanay, C. Linhart, I. Stein-­‐ feld, et al. Expander -­‐ an integra>ve program suite for mi-­‐ croarray data analysis. BMC Bioinforma5cs, 6(232):1471–2105, 2005. BicOverlapper: Santamaría, R.; Therón, R. and Quintales, L. (2008), A visual analy>cs approach for understanding biclustering results from microarray data, BMC Bioinforma5cs 9(247). –  Santamaría, R.; Therón, R. and Quintales, L. (2008), BicOverlapper: A tool for bicluster visualiza>on, Bioinforma5cs 24(9), 1212–1213. – 
Bioinformá>ca en la USAL INVESTIGACIÓN Inves>gación en bioinformá>ca •  Visualización de la información –  BicOverlapper –  Treeview •  Visualización de taxonomías •  h•p://vis.usal.es/treevolu>on/videos/felidae.swf –  Voronto •  Mapeo de expresión con ontologías Inves>gación en bioinformá>ca •  Genómica funcional –  biclust •  Paquete con algoritmos de biclustering para R –  Biología de sistemas •  Revisión y caracterización –  Análisis de datos EMBL Interna>onal PhD Programme •  h•p://www.embl.de/training/eipp/ •  Unas 1000 solicitudes al año –  150 seleccionados para una entrevista –  50 seleccionados –  6 categorías, de las cuales 2 están relacionadas con la bioinformá>ca Otras visitas al EMBL •  Visitas no licenciados –  Hasta 12 meses de visita •  Visitas predoctorales –  Hasta 6 meses de estancia en un centro del EMBL –  Para realizar alguna parte de la tesis •  En ambos casos sin financiación directa –  Pero suelen financiarse con dinero de proyectos