Download cliques de relaciones no lineales
Document related concepts
Transcript
Agrupamiento de relaciones no lineales entre expresiones de genes Por Roberto Barchino Garrido 21/09/2009 Institut de Biotecnologia i de Biomedicina 1 Índice Introducción Programas desarrollados y análisis de los resultados Conclusiones 2 Introducción: Objetivos Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Clasificar las relaciones transitivas. Estudiar la relación entre procesos. Buscar los métodos y algoritmos que faciliten los puntos anteriores. Analizar los resultados y obtener conclusiones. 3 Introducción: Microarrays Introducción Fase 1 Fase 2 Cada celda representa a un gen. Fase 3 Trabajo Futuro Conclusiones La intensidad de color representa el nivel de expresión. 4 Introducción: Microarrays Introducción Fase 1 Niveles de expresión del gen SCHPDH bajo diferentes condiciones muestrales Fase 2 Fase 3 Trabajo Futuro Conclusiones 5 Introducción: Microarrays Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones 6 Fase 1 y 2 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Clasificar las relaciones transitivas entre grupos de genes cuyas expresiones mantengan todos ellos una relación no lineal. Estudiar los procesos y que relación a nivel de expresión tienen entre sí. Buscar los métodos y algoritmos que faciliten los puntos anteriores. Analizar los resultados y obtener conclusiones. 7 Fase 1 Introducción ¿Qué es una relación transitiva? Fase 1 Fase 2 Una relación todos con todos Fase 3 Trabajo Futuro Conclusiones A -> B B -> C C -> A Representación: grafos B A C 8 Fase 1 Representación actual de las relaciones. Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones 9 Fase 1 Introducción Fase 1 Fase 2 Necesidad de un algoritmo para encontrar relaciones transitorias entre las expresiones no lineales de genes. Fase 3 Trabajo Futuro Conclusiones Búsqueda de subgrafos completos dentro de grafos: Cliques 10 Fase 1 Introducción Fase 1 Fase 2 Fase 3 ¿Qué es un clique? Es un subgrafo completo dentro de un grafo. Trabajo Futuro F E Conclusiones H D B G I A C 11 Fase 1 Introducción Fase 1 Fase 2 Fase 3 Problema: Algoritmo NP-Completo Solución: MACE (MAximal Clique Enumerater) Trabajo Futuro F E Conclusiones H D B G I A C 12 Fase 1 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Leemos los datos de las relaciones no lineales entre las expresiones de genes de nuestra microarray. Creamos una matriz en la que se representa el grafo de relaciones Ejecutamos MACE Recuperamos la información de las relaciones. Estudiamos los datos obtenidos. 13 Fase 1 Introducción Fase 1 Fase 2 Número Nodos Número total Cliques Porcentaje Fase 3 Trabajo Futuro Conclusiones 3 1758 72% 4 632 26% 5 54 2% 14 Fase 2 Introducción Fase 1 Fase 2 Clasificar las relaciones según su tipo. Encontrar grafos isomorfos Problema NP-(completo). Fase 3 Trabajo Futuro Conclusiones 15 Fase 2 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Realmente no nos importa tanto la morfología como el tipo de relaciones que hay. Si tenemos en cuenta la morfología obtendremos muchas clases con pocos datos. En cualquier caso conviene agruparlos para facilitar la investigación. El investigador ya mirará en detalle el significado biológico de esa relación. 16 Fase 2 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Solución: IsoTypes. A cada tipo de relación se le asigna un valor. Se ordenan las relaciones de menor a mayor. Se clasifica por matching. 17 Fase 2 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Finalmente se obtienen 420 clases diferentes. Cada clase está formada por los cliques que tienen el mismo IsoType. No todas las clases son interesantes a nivel biológico. 18 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Relación 1: Activadora. Relación 8: Mutuamente excluyente 19 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Relación 8 y 17: Mutuamente excluyente. Relación 10: Inhibidora 20 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Relación 0: Activadora. Relación 9 y 12: inhibidoras 21 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Relación 5: Activadora. Relación 9: inhibidora. Relación 26: Activadora/Desactivadora 22 Fase 3 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Clasificar las relaciones transitivas entre grupos de genes cuyas expresiones mantengan todos ellos una relación no lineal. Estudiar los procesos y que relación a nivel de expresión tienen entre sí. Buscar los métodos y algoritmos que faciliten los puntos anteriores. Analizar los resultados y obtener conclusiones. 23 Fase 3 Introducción Fase 1 ¿Qué es un proceso? Varios genes que se coexpresan a la vez. Fase 2 Fase 3 proceso Trabajo Futuro Conclusiones relaciones lineales 24 Fase 3 Introducción Fase 1 Fase 2 Fase 3 ¿Qué buscamos? La relación a nivel de proceso. Clique de relaciones no lineales Trabajo Futuro Conclusiones Proceso 25 Fase 3 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Para cada clique. Comprobar con todos los cliques que tengan el mismo IsoType que los genes mantienen una relación lineal. Caso que sí: guardar. 26 Fase 3 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Problema: En caso de que el clique tenga aristas repetidas es necesario permutar para comprobar la linealidad. Permutar Complejidad factorial. 27 Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones 28 Trabajo Futuro Introducción Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Crear una herramienta que automatice la elaboración de procesos con diversas maneras construcción a partir de los archivos generados en la fase 3. En forma de clique de cliques. En forma de grafo de cliques lineales. 29 Conclusiones Introducción Objetivos cumplidos. Fase 1 Fase 2 Fase 3 Trabajo Futuro Conclusiones Transitividad predecible. Procesos con relaciones no complejas. Programa automatizado. 30 Agrupamiento de relaciones no lineales entre expresiones de genes Por Roberto Barchino Garrido Institut de Biotecnologia i de Biomedicina 31