Download Grafos Interactivos Vía WEB - r-evolution research server
Document related concepts
Transcript
Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Grafos Interactivos Vía WEB Proyecto Final de Carrera del Alumno Darío Peña Seoane UAB(Universitat Autònoma de Barcelona) Setiembre 2007 Página 1 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Dedicatorias varias Indice Página 2 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Página 3 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 0 - Introducción El problema de determinar la función de una secuencia de DNA puede ser abordado desde diferentes vertientes, análisis de homología, búsqueda de motivos secuénciales, técnicas experimentales…etc. Otra aproximación al problema puede ser la extracción de conocimiento a partir del análisis de los datos de microarrays. Para ello se analizan los niveles de expresión de los genes, obtenidos de técnicas masivas de obtención de datos de datos usando microarrays, gracias a ellas, se pueden extraer los comportamientos relativos de los niveles de expresión de los diferentes genes. Esta información es muy importante ya que nos está determinando en cada momento cual es el conjunto de genes que lo expresan. Al expresarse los genes, se sintetizan las proteínas, y estas proteínas, actuando de forma independiente o conjuntamente con otras proteínas sintetizadas, dan lugar a las diferentes funciones celulares, en algunos casos desarrollando el tejido específico y, de esta manera, llevando cabo las funciones que hacen funcionar a todo organismo vivo. Para poder analizar los datos obtenidos de forma masiva comentados anteriormente, las herramientas matemáticas y estadísticas resultan realmente útiles. Sin embargo, pese a ser un estudio non-hypothesys-driven no es suficiente obtener rasgos generales, sino que cada vez es más necesario una mayor precisión por parte de dichos análisis, con resultados que contemplen la complejidad de los modelos biológicos y se ajusten cada vez más a los comportamientos reales. En este proyecto se persigue dicho objetivo mediante un particular enfoque de genetic networks. Dicho enfoque gira principalmente en torno al análisis de las relaciones no lineales entre los genes. Dado este enfoque no lineal, resulta también necesaria la búsqueda de una forma idónea para mostrar de forma detallada pero fácilmente interpretable estas relaciones. Trabajando en esta línea es usado un método no paramétrico para obtener y trabajar con las genetic networks generadas. Éstas representarán las relaciones lineales y no lineales entre pares de genes a partir de muestras no temporales obtenidas mediante microarrays. Una visión global de la red permite observar los genes distribuidos en clusters según su mayor o menor vinculación e identificar el tipo de relación que mantiene cada gen con el resto. Por otro lado, la operación zoom-in selecciona automáticamente los genes de mayor interés para todo estudio dado, y nos muestra en detalle el conjuntote estados que describen el comportamiento de los genes seleccionados como conjunto. Seleccionados los genes, es mostrada la relación entre los niveles de expresión de estos genes. En definitiva, la compresión de los datos obtenidos después de un análisis exhaustivo de las relaciones entre todos los genes presentes en una microarray pasa por poder visualizarlo en un espacio 2D. Es decir, poder representar las relaciones de correlación a través de la proximidad en el plano. 1 – Objetivos La ubicación en el espacio 2D de los genes es proporcionada por nuestro algoritmo específico para dicho cálculo a partir de las correlaciones obtenidas por el calculo de la PCOP para todos los pares de genes. Una vez obtenida esta ubicación el objetivo del proyecto es mostrarla gráficamente vía WEB y permitir operar sobre ella. Para conseguir dicho objetivo, se utilizarán las librerías JUNG(Java Universal Network/Graph Framework) para trabajar con grafos interactivos vía WEB. Página 4 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 A modo de resumen, los objetivos principales de dicho proyecto son implementar la graphical interface que permita: Mostrar o ocultar información sobre el grafo: o Grado de Correlación. o Nombre de los genes. o Filtrado de las relaciones por Grado de Correlación. Representar con niveles de gris el grado de correlación previamente calculado. Representar con colores los Clusters previamente calculados. Diferenciar gráficamente el minimum spanning tree previamente calculado. Permitir realizar las operaciones de zoom-in(selección automática de genes) y lanzar las interfaces de detalle. 2 – Bioinformática 2 – 1 Bioinformática La Biología computacional o bioinformática es la ciencia dedicada al estudio de los fenómenos biológicos de la microbiología molecular desde un punto de vista computacional, con el objetivo de ofrecer métodos robustos para la comprensión, simulación y predicción de comportamientos biológicos observados en los seres vivos. La bioinformática consiguió parte de la importancia que tiene actualmente con el nacimiento del Proyecto Genoma Humano (HGP). No se trataba simplemente de leer la secuencia de DNA del ser humano, ya que la parte práctica del HGP, obtener la secuencia con métodos analíticos de laboratorio, ya hace varios años que finalizó, pero la parte teórica, comprender el significado de 3.2 Gb de información, dista mucho de estar completada. Ante esta gran cantidad de datos que generan las nuevas técnicas de biología molecular, el reto fundamental de la bioinformática es adaptar y utilizar técnicas computacionales existentes, o crear nuevas, para poder extraer información útil de estos datos. Esta información ha de servir para complementar y validar la ya existente basada en experimentos clásicos, para generar nuevos conocimientos sobre determinados procesos biológicos y también descubrir nuevos. En campos como el proceso de descubrimiento de nuevos fármacos la bioinformática juega un papel fundamental. Combinada con las nuevas técnicas de biotecnología, la bioinformática permite identificar genes y proteínas causantes de enfermedades o de mecanismos de resistencia a antibióticos, de otra forma complicados de detectar. En estos métodos, permite analizar de forma extensiva y lo suficientemente amplia los genes implicados, recreando un modelo aproximado, y en consecuencia pudiendo intervenir en los procesos con fármacos más específicos, o incluso con nuevos paradigmas terapéuticos, como la terapia génica. La genómica, hasta hace poco la parte más importante de la bioinformática, consiste básicamente en el análisis de genomas, dedicada al descubrimiento y estudio de los genes que los componen. A partir de la secuenciación de un genoma la genómica interviene en diversos aspectos, uno de los principales es el ensamblaje de secuencias Página 5 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 obtenidas de forma aleatoria para conseguir la secuencia completa y ordenada del genoma, y encontrar los genes que contiene. Poco después del boom de la genómica, teniendo ya genomas con proteínas hipotéticas identificadas por métodos predictivos, hacía falta saber que proteína expresaba cada secuencia. De aquí nació la proteómica, para descubrir que es y que función tiene una proteína. Este proceso se aplica hoy en día rutinariamente en lo que se conoce como anotación del genoma, es decir, dar nombre y función a todas las proteínas hipotéticas localizadas. Éste último punto es el objetivo que persigue este proyecto. Un camino obvio hacia la proteómica es, simplemente, coger la secuencia de DNA, traducirla a proteína y predecir mediante simulación los plegamientos secundarios, terciarios y cuaternarios de la proteína y, en consecuencia, su estructura. Pero este camino presenta bastantes inconvenientes, por una parte se estima que, bien hecho, para una proteína pequeña (de unos 300 aminoácidos) se requieren 6 meses de proceso a 1 petaflop. Por otra parte, el modelo físico real es muy complejo y no se conoce lo suficiente como para poder simularlo en detalle. Así, todo y que se pudiera predecir bien el plegamiento a partir de cálculo, podría ser que se siguiese sin tener ni idea de que hace la proteína. La bioinformática sería otro campo más de aplicación de técnicas computacionales si no fuera porque el campo sobre el que se aplican en este caso, la biología molecular, está experimentando un crecimiento exponencial. Con este panorama, el número y la complejidad de los datos aumentan a un ritmo más alto que la capacidad de los ordenadores que los han de procesar, la necesidad de un fuerte desarrollo teórico y práctico en el entorno de las herramientas bioinformáticas se hace más que necesario. Otro de los problemas a la hora de tratar toda esta información es la gran cantidad de ruido que hay, al tratarse de datos obtenidos experimentalmente. Una vez se han clasificado los datos obtenidos, el último paso en el análisis de los mismos consiste en extraer la información biológica subyacente a los resultados experimentales. Para ello, se han desarrollado numerosas herramientas que obtienen información a partir de bases de datos u ontologías biológicas y permiten sacar conclusiones finales referentes al experimento realizado. Una especialidad dentro de la biotecnología es la denominada ingeniería metabólica, una nueva disciplina que tiene por objetivo último la optimización de las redes génicas, el estudio de la interacción entre los genes, y metabólicas, así como el desarrollo de software para su estudio. Otro campo biológico que trata la bioinformática es la recreación de modelos virtuales de predicción de rutas metabólicas, una ruta metabólica es una serie de reacciones químicas que ocurren dentro de una célula catalizadas por enzimas, para formar un producto metabólico cuyo objetivo puede ser su utilización o almacenamiento en la célula, o la iniciación de otra ruta metabólica. Página 6 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 2 – 2 Microarrays ¿Cómo puede entenderse un fenómeno sobre la base de la interpretación de grandes volúmenes de datos? ¿De qué manera puede utilizarse la información para la toma de decisiones? La respuesta a estas preguntas es el objetivo del datamining (minería de datos), un conjunto de técnicas agrupadas con el fin de crear mecanismos adecuados de dirección, entre ellas puede citarse la estadística, el reconocimiento de patrones, la clasificación y la predicción. Para descubrir patrones de relaciones útiles en un conjunto de datos se empezaron a utilizar métodos que fueron denominados de diferente forma, con el término Data Mining. Desde este ángulo, del Data Mining aplica una dinámica que se mueve en sentido contrario al método científico tradicional. Con frecuencia, el investigador formula una hipótesis; luego, diseña un experimento para captar los datos necesarios y realiza los experimentos que confirmen o refuten la hipótesis planteada. Este es un proceso, que realizado de forma rigurosa, debe generar nuevos conocimientos. En el Data Mining, por el contrario, se captan y procesan los datos con la esperanza de que de ellos surja una hipótesis apropiada. Se desea que los datos nos describan o indiquen el porqué presentan determinada configuración y comportamiento. 2.2.1 Microarrays El desarrollo clásico de un experimento de microarray de cDNA es un estudio de trascripción génica a lo largo del tiempo para dos condiciones, una será la de referencia y la otra será la propia del experimento. Así se podrá ver como afecta la condición dada a la trascripción de estos genes. Lo que se quiere ver son las diferencias en la expresión de los genes entre las dos condiciones. La trascripción génica es el proceso de síntesis del RNA, que inicia la producción de las proteínas que determinan los procesos biológicos. Un microarray de ADN consiste en un gran número de moléculas de ADN ordenadas sobre un sustrato sólido de manera que formen una matriz de secuencias en dos dimensiones. Estos fragmentos de material genético pueden ser secuencias cortas llamadas oligonucleótidos, o de mayor tamaño, cDNA (ADN complementario, sintetizado a partir de mRNA). A estos fragmentos de ADN de una sola hebra inmovilizados en un soporte, se les denomina a menudo sondas. Los ácidos nucleicos de las muestras a analizar se marcan por diversos métodos (enzimáticos, fluorescentes, etc.) y se incuban sobre el panel de sondas, permitiendo la hibridación (reconocimiento y unión entre moléculas complementarias) de secuencias homólogas. Durante la hibridación, las muestras de material genético marcadas, se unirán a sus complementarias inmovilizadas en el soporte del chip, permitiendo la identificación y cuantificación del ADN presente en la muestra (mutaciones, patógenos, etc.). Con posterioridad, el escáner y las herramientas informáticas permiten interpretar y analizar los datos obtenidos. Los microarrays de ADN, o micromatrices de material biológico, permiten la automatización simultánea de miles de ensayos. Página 7 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 2.2.2 Data Mining aplicado sobre microarrays Hay una serie de de etapas en el tratamiento y estudio de los datos obtenidos con microarrays, después de la obtención de los datos se normalizan, y un análisis común para facilitar el estudio de los datos obtenidos por microarrays es la obtención de clusters. El objetivo del análisis por clusters es, dada una matriz de genes y el resultado para diferentes experimentos realizados, encontrar un grupo de un conjunto de genes, de tal forma que los clusters resultantes sean homogéneos i estén bien separados. El punto clave es reducir la gran cantidad de datos caracterizándolos en grupos más pequeños de genes similares. Esto implica que los genes pertenecientes al mismo cluster han de ser tan similares entre ellos como sea posible, mientras que los genes de clusters diferentes han de ser tan disimilares como sea posible. Los algoritmos de clustering más usados que pueden dar un buen resultado en un tiempo razonable son los métodos de aglomeración. Los patrones de expresión de cada gen son agrupados por similitud. En principio, se puede suponer que genes que están relacionados en su expresión lo hacen por alguna razón biológica. Para encontrar esta razón biológica, lo primero es saber cuando se puede considerar que dos genes están correlacionados y cuando no, es decir, se ha de definir una distancia entre patrones. Según la distancia que se utilice para agrupar los diferentes patrones de expresión, se obtendrán diferentes grupos, por tanto, la distancia define la relación que se busca entre los genes. Los métodos más utilizados son la distancia euclidiana, correlación de Pearson y correlación de cosinus. No obstante, esta relación entre la similitud entre genes i la interacción de sus productos, no es en muchos casos nada clara. Sobretodo en aquellos en que estos productos estén asociados solo de forma transitoria. Además, en la práctica, la similitud entre clusters, ya no entre pares de genes, no tiene una definición única. Aunque los algoritmos de aglomeración son óptimos en cada paso según el criterio de agrupamiento elegido, la elección de este criterio puede afectar al resultado final. Existen diversos métodos o criterios para calcular las distancias entre los clusters que se construyen. Los más habituales son single-linkage, complete-linkage y average-linkage. 2 – 3 Las PCOP 2 – 3 – 1 Introducción La tecnología DNA microarray permite el análisis de alto rendimiento de expresiones de genes y permite a los investigadores testar la actividad de miles de genes al mismo tiempo en múltiples condiciones celulares. Este apartado presenta una nueva aproximación para relacionar genes, Principal Curves of Oriented-Points (PCOP) y minimum spanning tree para analizar series de datos temporales y no temporales, Ésta lleva a cabo un análisis detallado de patrones no lineales, n-dimensionales de una microarray. Esta información detallada es especialmente útil en el entorno biomédico la cual no es posible obtener en la aplicación de los métodos actuales de análisis. Para todos los ejemplos mostrados se han usado los datos de la microarray proporcionada por el National Cancer Institute (NCI, USA), [scherf et all, nature 2000]. Página 8 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Estos datos corresponden a las expresiones de 9703 cDNAS que representan aproximadamente 8000 genes únicos expresados en 60 líneas celulares, después de la administración de 1400 componentes químicos. Finalmente se han seleccionado las expresiones ponderadas de las 60 líneas celulares para 1416 genes y 200 sustancias antitumorales. 2 – 3 – 2 Las PCOP Las Principal Curves (curvas principales) han sido formuladas para extraer patrones de comportamientos no-lineales en análisis de datos multivariable. Este método describe las relaciones entre variables independientes mediante una curva continua trazada a través de una nube de puntos discretos, como por ejemplo entre datos experimentales de las microarrays de ADN. Además es inmune al ruido en los datos, preservando su información, el mayor problema de la tecnología basada en microarrays. Para espacios muestrales elipsoidales, es decir, una nube de puntos discretos en forma de elipse alrededor de una recta, estudiar las relaciones lineales entre variables independientes puede ser suficiente para describir el comportamiento de esas variables. En los demás casos, se necesita usar Principal Curves debido a que la relación entre ellas será más compleja. En nuestra aplicación se han usado las PCOP (Principal Curves of Oriented Points) formuladas por Delicado [Del01]. Delicado define las PCOP en la generalización a nivel local, de la siguiente propiedad de los componentes principales: Para una distribución normal multivariable X, si X se proyecta sobre un hyperplano, la varianza total de la proyección es mínima cuando el hyperplano es ortogonal al primer componente principal. Estos vectores locales de las componentes principales serán los vectores tangentes a la PCOP. En [25] se describe como definir con precisión estas áreas locales en el espacio global y las muestras pertenecientes a cada una de ellas. Para entender mejor como pueden aplicarse las PCOP sobre un conjunto de datos, se mostrará un ejemplo real: Página 9 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Los genes están sacados de la microarray anteriormente comentada, de la que además se extraerán los datos usados durante todo el trabajo. Se puede observar la Principal Curve calculada para estas variables y la densidad y varianza de la nube de puntos alo largo de ella. La curva muestra la relación no lineal entre las variables. El grado de correlación de esta relación nos los proporcionarán los valores de Generalizad Total Variance (Varianza Total Generalizada) y la Residual Variante (Varianza Residual), proporcionados por el cálculo de la PCOP. La varianza explicada por la curva permite saber si ésta puede seguir la tendencia de la nube de puntos. La varianza explicada mejora cuando la nube de puntos tiene un comportamiento regular bien identificado con el trazado de la curva. La Varianza Residual (VR) describe el grado de dispersión de las muestras alrededor de la curva, es decir, la varianza no explicada por la curva. La Varianza Total Generalizada (VTG) es la suma de estos dos parámetros de dispersión y el factor de correlación es igual a VTG dividido por VR. Página 10 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 ¿Porque usamos las PCOP? Los estudios biológicos actuales y especialmente la transcriptómica generan una enorme cantidad de datos que los científicos deben analizar para entender la célula al completo. PCOP (Principal Curves of Oriented Points) es un método que permite convertir enormes cantidades de datos asociados a dos o más variables independientes en patrones representativos. Además, PCOP no solo contempla los comportamientos lineales entre estas, sino que también evalúa las relaciones no lineales en un espacio multivariable. Uno de sus múltiples usos es, por ejemplo, comparar genes y, en concreto, microarrays de ADN. Una microarray es la disposición ordenada y conocida de miles de fragmentos de material biológico (ADN, ARN, Proteínas) sobre un soporte sólido (portaobjetos, vidrio, plástico). El material biológico se inmoviliza sobre ellos de forma que se sabe en cada punto de la matriz que es lo que se ha depositado permitiendo el posterior análisis. El número de posiciones en estas matrices puede llegar a alcanzar las decenas de miles; la gran cantidad de datos que generan este tipo de ensayos forman un marco ideal para la aplicación del método de PCOP. La potencia de la tecnología basada en microarrays de ADN es la capacidad de ofrecer datos de la expresión de los genes a través de diferentes muestras. No obstante, el análisis de microarrays desafía los métodos hypothesis-driven (dirigidos por hipótesis o predicciones) tradicionales y nos empuja al modelo de generación de hipótesis o nonhypothesis-driven. Para usar eficientemente este modelo, el análisis debe proporcionar al científico una visión global y asimismo permitir un examen mas profundo en aspectos más específicos de un subgrupo diferenciado de genes, ya que esa información global no permite, por ejemplo, comprender el comportamiento de un trío de genes en particular. El objetivo de la aplicación es proporcionar ese examen de una selección específica de genes pertenecientes a una microarray dada. Así, es posible agrupar en seis categorías, de acuerdo con sus formalismos, redes reguladoras a partir de datos de expresión de genes (modelos hypothesys-driven): 1. Aproximaciones basadas en modelos lineales. 2. Aproximaciones basadas en la descripción de los efectos reguladores usando conjunto de reglas lógicas. 3. aproximaciones basadas en un conjunto de ecuaciones diferenciales deterministas caracterizando los patrones de regulación en la red. 4. Modelos completamente cinéticos que sólo incluyen componentes estocásticos a nivel molecular. 5. Redes probabilísticas. 6. Redes neuronales. El problema principal estos modelos sobre la técnica de microarrays es precisamente su determinismo: a pesar de facilitar la visualización del sistema, al mismo tiempo ocultan su complejidad. La simplificación aplicada puede producir un modelo Página 11 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 incorrecto (especialmente cuando los datos proporcionados no incluyen todos los genes de la célula); además, esta simplificación puede no ser requerida por el científico que intenta usar el modelo, ya que será imposible separar, recobrar y analizar la información subyacente no descrita por el modelo. Nuestra aplicación, en cambio, trabaja con relaciones lineales y no lineales entre genes, gracias al uso de las PCOP, y es esta capacidad para detectar comportamientos no lineales en un espacio multivariable en donde radica su interés. Por otro lado, las herramientas que extraen el comportamiento de los genes a partir de microarrays trabajan con series de datos temporales. Este tipo de datos es útil para modelar sistemas como por ejemplo el ciclo celular, para detectar los genes reguladores o analizar la dinámica de las genetic networks. No obstante, debido a la limitación de las series temporales, este tipo de datos no es útil para ofrecer un completo y realista comportamiento de los genes; tan solo pueden estudiar los sucesos celulares sincrónicos temporalmente. El método PCOP no requiere series temporales de datos; analiza el comportamiento del conjunto de genes para todas las posibles condiciones celulares proporcionadas por la microarray. Estas condiciones pueden deberse a diferentes estímulos (temperatura, radiación, desnutrición...) y constituyen todo el espacio muestral; gracias al uso de PCOP, el sistema obtiene estados discretos a partir de las expresiones de los distintos genes, creando una secuencia de tendencias locales cuya suma conforma el comportamiento general de las relaciones de cada grupo de genes. Pattern análisis de microarrays[Esta sección la pongo en PCOP porque creo que es una consecuencia del cálculo de éstas] tu interfaz tiene un botón que lanza el patern análisis de las pcop, que es lo que aquí se explica, la interfaz que lanza tu aplicación. Si no lo pones en el sitio correcto no se entenderá que tu aplicación web lanza la herramienta que a continuación se explica. Has de diferenciar lo que es el calculo de las pcop entre todos los pares de genes (el pre-proceso), y el cálculo de la pocp como pattern análisis (o dependence análisis desde el applet) que se realiza para los genes seleccionados y que el investigador-usuario le interesa examinar. La clave de la aplicación web realizada es justamente esta, el lanzar el pattern análisis de los genes seleccionados (por los múltiples métodos que dispone el applet para ahcerlo, manual, por mspath, por búsqueda por nombre, por búsqueda de la distribución de las clases, etc…) Ten en cuenta que esto es la descripción de tu aplicación. La primera aplicación directa del método de PCOP es el Pattern Analysis (Análisis de Patrones), que determina el patrón subyacente en cualquier nube de puntos discretos. Combinando el hecho de que no se necesita conocer a priori la relación entre las variables consideradas ni es necesario que exista una relación lineal entre ellas, la aplicación aporta una importante herramienta para extraer conocimiento sobre grandes cantidades de datos biológicos. La Graphical Interface debe proporcionar los mecanismos para aprovechar al máximo toda la información proporcionada por la PCOP, lo que incluye varios servicios al investigador: Página 12 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 La representación geométrica de la PCOP junto a las muestras sobre la que se ha calculado. Permitiendo visualizar por pares hasta 8 variables, para ver estudiar el comportamiento del patrón para esas 2 variables. La representación paramétrica de la PCOP respecto las distintas variables en una sola gráfica para observar el comportamiento relativo de cada variable respecto a todas las demás. La representación de la Density (Densidad), Span (Amplitud) y Variance (Varianza) a lo largo de la curva, y observar sus valores para cada uno de los POPs (Principal Oriented Points) de la curva. Además, la Interface debe proporcionar al usuario la capacidad de examinar con detalle zonas de interés de la gráfica y moverse por ellas para analizar con la profundidad deseada el comportamiento de estas en el espacio. Para ello, la aplicación ofrece una serie de herramientas de visualización: Capacidad de hacer Zoom, tanto para acercarse o alejarse, encuadrando cualquier punto de la gráfica deseada. En todo momento, un indicador de escala informará al investigador del porcentaje de aumento que esta efectuando sobre la gráfica Capacidad para desplazarse por la gráfica intuitivamente moviéndola en la dirección deseada con la herramienta Drag (Arrastrar) Capacidad de cambiar en cualquier momento de una escala real de proporción 1:1 entre los dos ejes a una escala proporcional que aprovecha al máximo el área de visualización. Posibilidad de gestionar los colores de las diferentes variables en la representación paramétrica, y de la PCOP en la geométrica. 2 – 4 Genetic graph Este valor comentado nos señala en que medidas están relacionadas estas expresiones. Por tanto a partir de estos valores podemos generar el grafo con el que trabajar y con el que representar el experimento que el investigador desea realizar. El minimum-spanning tree es un árbol construido desde un conjunto de puntos que verifican esta propiedad: la suma de todos los pesos de las aristas deberá ser igual o más pequeña que la suma de los pesos de las aristas en otro árbol con la misma entrada de datos. Basado en la relación PCOP del análisis pairwise entre todos los genes de la microarray, se define el minimum spanning tree, donde estas aristas son la relación entre cada par de genes con su correspondiente valor de correlación. Estas aristas mantienen una relación decreasing-order basada en sus correspondientes valores Del uso de este valor en la expresión de genes, las relaciones representadas en el árbol pueden ser de cuatro tipos básicos: 1. Genes co-expressed positivamente. 2. Genes co-expressed negativamente. 3. Genes mutuamente excluidos en esta expresión. 4. Genes correlacionados no linealmente. La relación del tipo 1 o del tipo 2 involucra genes con una relación lineal. La relación de tipo 2 muestra genes los cuales son dependientes en esa expresión sólo porque uno de estos genes puede estar sobre expresado o infraexpresado para activar las fluctuaciones de expresión de otro gen. La relación de tipo 4 corresponde a la relación Página 13 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 de correlación completa, como los tipos 1 y 2, pero en el caso no lineal. Se puede observar que la tangente de los vectores de la curva es todo lo necesario para describir el tipo de curvas proporcionada por el cálculo PCOP (Delicado y Huerta 2003). En otras palabras, este valor describe inversamente el nivel de correlación de todos los genes correlacionados en su expresión, lineal o no lineal, y directamente la obertura del rango de las gene-expression activa o desactiva los genes mutuamente excluyentes. No obstante, los genes completamente independientes no son considerados. Los datos de la microarray son normalizados, y después no aparecen gamas de expresión muy diferentes respecto otros tales que en los análisis de pair-wise puede proporcionar un f baja que indica alta dependencia donde hay una dependencia completa. En la figura (A) el grafo obtenido usando R2 puede compararse, respecto al grafo de la Figura (B) usando la f proporcionada por el cálculo PCOP. En los grafos de la figura, la localización en el plano 2D del gen depende de la correlación con el resto de lo genes usando un algoritmo de layout force-direct con tres parámetros: atracción, repulsión y gravedad. En ambos grafos la mejor correlación es la misma (la relación lineal) y muchos de los genes al pertenecer a cada cluster también, pero otros genes, varían cuando las relaciones del tipo 3 y 4 son consideradas (Figura B). 2 – 6 Layout La comprensión de todos los datos obtenidos después de un análisis exhaustivo de las relaciones entre todos los genes presentes en una microarray pasa por poder visualizarlos en un espacio 2D. Es decir, poder representar las relaciones de correlación a través de la proximidad en el plano. Página 14 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 La representación mediante grafos de información da la posibilidad de organizar de manera eficiente gran cantidad de datos no homogéneos. Actualmente, un gran número de aplicaciones de carácter tanto científico como de ingeniería necesitan representar visiblemente por medio de grafos la información de sus trabajos, de ahí la importancia de su investigación. La generación automática de grafos es un problema de optimización extremadamente complejo no solo desde el punto de vista computacional. Muchas disciplinas, como la algorítmica, la teoría de grafos y la geometría computacional cooperan con el fin de encontrar nuevos algoritmos en este campo. 2 – 6 – 1 Características del Layout Hasta ahora los grafos se han definido como objetos matemáticos abstractos. Pero para dibujar un grafo a cada nodo se le ha de asignar una localización, es decir, un punto en el espacio. De la representación gráfica del grafo abstracto surge la distinción entre grafos planos y no planos. Si es posible dibujar los vértices en el plano de tal forma que no haya ningún cruce entre las aristas es un grafo plano. Como se puede ver en la figura 2, en el grafo K3,3 no hay ninguna permutación posible de nodos que lleve a eliminar todos los cruces entre sus aristas. Al dibujar un grafo normalmente se siguen unas convenciones, que tienen que ver con la representación y posicionamiento de nodos y aristas. Una lista completa de estas convenciones fue la que dio Sugiyama en [1], y que se muestra en la siguiente tabla: Página 15 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Tipo Convención Explicación Posicionamiento de nodos Libre Los nodos se pueden situar en cualquier lugar del plano, sin ninguna restricción. Los nodos se sitúan entre líneas paralelas, llamadas “capas” (layers). Un nodo es elegido para estar en el centro del dibujo y el resto es situado sobre círculos concéntricos a éste. Los nodos son situados en líneas radiales que salen desde un punto central del dibujo. Los nodos sólo pueden ser situados en una rejilla entera. Los nodos son situados en las intersecciones definidas por los círculos concéntricos y las líneas radiales de una rejilla polar. Las aristas son dibujadas como líneas rectas que conectan nodos. Las aristas son dibujadas como una secuencia de una o más líneas rectas. Las aristas son dibujadas cono líneas curvas de un cierto tipo. Las aristas son dibujadas siguiendo las líneas del sistema de coordenadas. Por ejemplo, en un una rejilla ortogonal y Polyline, cada línea ha de ser dibujada horizontal o verticalmente siguiendo una línea de la rejilla. Las aristas pueden ser dibujadas libremente sin restricciones del sistema de coordenadas. Líneas paralelas Círculos concéntricos Líneas radiales Rejilla ortogonal Rejilla polar Representación de aristas Straight-line Polyline Curved line Dependencia del Dependiente recorrido de las aristas en el sistema de coordenadas Independiente Igual que con las convenciones, también hay algunas reglas estéticas que deben ser utilizadas en los algoritmos de dibujo de grafos. Describen las propiedades aconsejables en la distribución del grafo para que la visualización sea apropiada. Algunas de las más importantes son: el área necesaria para dibujar el grafo completo debe ser lo menor posible, el ángulo entre las aristas de un nodo ha de ser maximizado, las caras de un dibujo plano deben ser dibujadas como polígonos convexos, intentar minimizar el número de cruces entre aristas... Aunque la mayoría de veces no es posible hacer que todas las reglas se cumplan a la vez, a veces la mejora de una de ellas implica empeorar otra. Por ejemplo, minimizar Página 16 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 los cruces entre aristas puede llevar a tener que incrementar la distancia de las aristas. Dando lugar a un problema de optimización para seleccionar la ponderación correcta de cada una de las reglas estéticas. 2 – 6 – 2 Métodos del Layout Dibujo de grafos ortogonales: diseñado para grafos no dirigidos y motivado para cumplir la regla estética de maximizar el ángulo entre las aristas incidentes en un nodo. También otras como evitar los cruces entre aristas, aunque para esto primero hay que hacer que el grafo sea plano. Los nodos se sitúan en una rejilla ortogonal, las aristas son polylines y están condicionadas al sistema de coordenadas. El método consta de tres pasos: planarizar, normalizar y ortogonalizar (reducir el grado de los nodos hasta un máximo de cuatro añadiendo nuevos nodos) y compactar. Dibujos basados en analogías físicas: estos grafos se basan en las convenciones de situar los nodos libremente en el plano, usando líneas rectas para unirlos y sin que dependan del sistema de coordenadas. Según el tipo de analogía se dividen en dos clases: Force-Directed Placement: intenta minimizar la energía interna del sistema para iterativamente modificar las posiciones de los nodos respondiendo a las fuerzas entre los nodos. El primer método de este tipo fue obra de Eades en [2], también llamado spring embbeder, modelaba el grafo como un sistema de anillos (rings) y muelles (springs). Página 17 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Energy-Based Placement: El algoritmo de Kamada y Kawai [3] utiliza muelles con una longitud proporcional al camino más corto entre dos nodos, los nodos adyacentes con muelles proporcionales a uno, dando una suma de energías potenciales que es la que directamente se minimiza con una modificación del algoritmo de Newton-Raphson, que mueve el nodo con mayor gradiente en cada iteración. Para grafos muy grandes también hay algoritmos basados en minimizar una función de energía como el descrito en [4], el algoritmo se llama ACE (Algebraic multigrid Computation of Eigenvectors). Minimiza la función de energía de Hall , y con este método se pueden dibujar grafos con un millón de nodos en poco tiempo. Dibujo jerárquico de grafos: Los nodos se sitúan en capas y se unen con aristas straightline o polyline independientemente del sistema de coordenadas. A pesar de usar un sistema de posicionamiento de nodos por capas, este método también da la posibilidad de situarlos usando círculos concéntricos o líneas radiales, con lo que se puede reducir en algunos casos el número de cruces de aristas. Dibujo de árboles: Los árboles son un tipo de grafos muy común. Según el tipo de representación se puede dividir en tres métodos: 1. Dibujo por capas: los árboles se pueden ver como grafos acíclicos, así que es posible adaptar fácilmente el método de dibujo jerárquico. Además, como los nodos no tienen ciclos, la distribución en capas se puede hacer cogiendo la profundidad de los nodos. 2. Dibujos circulares: se sitúa el nodo raíz en el centro del dibujo, y las diferentes capas en círculos concéntricos a éste. Para evitar cruces entre aristas a cada Página 18 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 subárbol se le asigna un sector normalmente proporcional en tamaño al número de nodos que tiene. Con este método generalmente se consiguen dibujos planos. 3. Dibujos ortogonales: este método sólo es aplicable en el caso de árboles binarios, donde cada nodo tiene exactamente dos hijos. Cada hijo es situado junto al padre, a la derecha, en la misma línea horizontal o exactamente debajo. Repitiendo este proceso se posicionan todos los nodos, y además, al igual que en el método anterior, a cada subárbol se le asigna su propia área para evitar superposiciones. 2 – 6 – 3 Grafo dividido en Clústeres Dados los problemas de la representación de un grafo completo, para pintar este se produce una separación en clusters. Intentar dibujar los clusters con la mayor exactitud posible, y después situar los clusters formando hyperclusters. Esta línea de desarrollo busca representar todos los genes sin considerar uno de mayor peso. Para ello y para superar los obstáculos de los algoritmos estudiados del apartado 3 se separan los genes en clusters, se calcula la posición relativa de cada gen dentro de su cluster, y después se sitúan los clusters. Para la separación en clusters se ha utilizado el método de single-linkage. Sean dos clusters Ci y Cj, la distancia por single-linkage entre los dos clusters es la calculada como la distancia mínima entre un miembro del conjunto i y uno del j. Este método genera clusters largos y poco densos. Discrimina outliers con facilidad (los outliers son observaciones fuera de lo frecuente que tienen una profunda influencia sobre el valor del coeficiente de correlación del total de datos). Clusters Aplicando single-linkage, los genes que pertenecen a un mismo cluster serán los que se unen por su mejor correlación, es decir, estarán dentro del mismo cluster todos aquellos genes que su mejor correlación sea con uno de los genes del cluster. Al utilizar singlelinkage se sigue la estructura del minimum spanning tree, y se sitúan más cerca los Página 19 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 genes que realmente están más cercanos en concordancia con la política de representar mejor las relaciones de los genes más correlacionados. Como ahora tratamos sólo con los genes del mismo cluster, los genes a ubicar son muchos menos y no resulta necesario ubicar el nuevo nodo según las posiciones de los tres anteriores en el mst. En esta nueva aproximación cada nuevo nodo que se inserte dependerá del resto de nodos de su cluster que ya hayan sido ubicados. Además, ahora nos podemos permitir que las distancias del mst se correspondan de forma exacta con las correlaciones que representan. Al situar un nodo, se busca su ubicación en un punto de la circunferencia que se forma con centro en la ubicación de su predecesor en el mst y como radio el valor de su correlación. Se selecciona entonces el punto de la circunferencia que minimiza el error respecto a las distancias con el resto de nodos. Se han probado diversos métodos para considerar dicho error. En las figuras 22, 23, 24 y 25 se puede observar su respectiva aplicación sobre el cluster del gen ‘SID W 362471, GUANYLATE CYCLASE SOLUBLE, BETA-1 CHAIN [5':AA018579, 3':AA018580]’. Figura 22: Ubicación del nuevo gen en función de la suma de errores respecto a los ya situados Página 20 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Figura 23: Ubicación del nuevo gen en función de la suma de errores dividiendo por la correlación Figura 24: Ubicación del nuevo gen en función de la suma de errores multiplicando por el valor absoluto del logaritmo de la correlación Figura 25: Sumar más error según distancia con la correlación La figura 22 es directamente eligiendo la posición en la que la suma de error, la diferencia que hay entre la distancia en el plano entre dos genes y su valor de correlación, con todos los nodos ya situados del cluster es menor. Pero una de las prioridades para la representación del grafo era que las distancias más correctas debían ser las que dejasen que el error que hubiera se acumulase preferiblemente en los nodos situados a mayor distancia. En esa línea se probaron las dos siguientes variaciones. Primero la que muestra la figura 23, dividiendo el error por la correlación, así el error de los nodos que deberían estar más cerca cuenta más en la suma final, tendiendo a situarse el nodo en la posición más correcta. Al usar la división se consigue un cálculo del error lineal en función de la distancia, para que la importancia de los más próximos sea aún mayor se puede utilizar una función logarítmica, utilizada en la figura 24. Como las correlaciones utilizadas están entre cero y uno, el valor absoluto de su logaritmo será Página 21 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 decreciente, y al multiplicarlo por el error se consigue aumentar la importancia de la distancia en la suma final respecto a la prueba anterior. En el último caso, el de la figura 25, para intentar que los genes que deben estar lejos no queden cerca, uno de los problemas que se han venido repitiendo en las diferentes representaciones del grafo desde el principio, el error se ha ponderado en función de si está más cerca de lo que debería. Si la distancia en el plano es menor que su correlación ese valor influirá más en la suma total de error. Mientras que si está más alejado de lo que indica el valor de correlación penalizará menos. Con este último método se consigue la mejor aproximación a lo calculado manualmente, ya que se ha minimizado, en comparación con los tres métodos anteriormente explicados, el número de casos de nodos que se encuentran más cerca en el plano de lo que deberían por su valor de correlación respecto otros nodos. Es la implementación que se utilizará en la representación del grafo dividido en clusters de clusters. Utilizando las coordenadas obtenidas por el último método como valores iniciales en el algoritmo force-directed [16], en lugar de valores aleatorios para reducir el tiempo de cálculo, se consigue refinar el dibujo del grafo. El problema es que este tipo de algoritmos sitúan los nodos en cualquier posición del plano, y una de las restricciones impuestas era que se tenían que cumplir las distancias del mst. En este algoritmo [16], al final de cada iteración se calcula la energía de cada nodo para ubicarlo en una nueva posición. Se ha modificado para que, una vez ya ubicado en la nueva posición, se ajuste la distancia de la arista a su más cercano en el mst respetando el valor de correlación que los une. Figura 26: Minimizar una función de energía para reubicar los nodos de la figura 25 Con este método se pretendía que el error quedase lo más repartido posible entre todos los nodos del grafo. La estructura general del grafo se mantiene y únicamente se añade alguna pequeña modificación, algo que contando el tiempo de cálculo que añade, y teniendo en cuenta el tamaño de los grafos de los clusters para los que se utilizará, no sale rentable. Así que finalmente esta modificación no se utilizará en la implementación definitiva del algoritmo. Página 22 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 La última modificación que se ha probado, mostrada en la figura 27, es volver a calcular la posición de los nodos ya ubicados cada vez que se añade uno nuevo, con la intención de corregir y repartir el error entre todos ellos. Al situar un nuevo nodo se recorre el MST ya ubicado, a partir del último situado, modificando la posición de los genes para reajustar las distancias. Pero con cada iteración el grafo cambia su estructura, no tendiendo a estabilizarse ni en su forma ni en el reparto de errores entre los nodos. Figura 27: Algoritmo usado en la figura 25 con corrección de la posición de los nodos ya ubicados en cada nueva iteración. Hiperclusters Un hipercluster es un cluster de clusters. Los hipercluster se han montado con el mismo método de single-linkage, manteniendo las uniones entre los clusters siguiendo el mst. Con la posición relativa de los nodos dentro de los clusters calculada, queda ubicar en el plano los clusters dentro de cada hipercluster o cluster de clusters. Si hubiéramos utilizado el average-linkage en lugar del single-linkage para posicionar los clusters se calcularía la distancia media entre todos los elementos de un cluster y los del otro. Posibilidad que en este caso se descartó, debido a que en algunos clusters hay genes que excepto al nodo que se unen por single-linkage no están excesivamente próximos al resto de nodos del cluster. Utilizando single-linkage, los clusters se unen a aquellos que contienen el gen con el que uno de sus propios genes mantiene la mejor de las relaciones con los genes externos al cluster. La distancia entre clusters no será la distancia que realmente se mostrará en el grafo. Ya que es demasiado corta y si se utilizara la mayoría de clusters se superpondrían con los clusters contiguos. Para evitarlo, las distancias han sido escaladas de tal forma que los clusters vecinos, en el mst que conforman dentro del hipercluster, estén a la suficiente distancia como para no solaparse entre ellos. Para calcular las distancias escaladas, las que realmente se verán en el grafo, se ha buscado la circunferencia de radio menor que abarca cada cluster, centrada en el punto medio entre las coordenadas de todos los nodos que lo forman. Las distancias entre los clusters se escalan lo suficiente para que la longitud de la arista sea como mínimo la suma de los radios de los clusters. Con las distancias ya calculadas, el algoritmo para situar los clusters es muy parecido al utilizado para situar los nodos. Página 23 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Se va recorriendo en amplitud el mst que forman los clusters dentro del hipercluster . Y cada vez que se sitúa un nuevo cluster, se busca su posición con la distancia del mst respecto al último situado, se elige la ubicación en que la suma de errores con el resto de clusters es mínima, aplicando la misma corrección que al situar los genes en su cluster. Al igual que con los nodos, se utiliza el método de penalizar más que una distancia sea menor que lo que debería dada la correlación que representa. Al escalar las distancias del mst de clusters se consigue que no se superpongan los clusters vecinos. Pero todavía podría ser que el nuevo cluster se superponga con alguno del resto de los ya situados. Algo que no interesa ya que provocaría cruces entre aristas que dificultan la interpretación del grafo. Para evitar este problema se han probado dos soluciones. La primera es, al igual que como en el dibujo del grafo en que se usa un gen como semilla, usar una envolvente de la nube de puntos que forman los nodos pertenecientes a los clusters ya situados en el hipercluster. Y la segunda, comparar con cada cluster ya ubicado y comprobar que no se solapan. El problema de la primera solución es que a veces, al tener una envolvente conjunta, hay espacio que no está ocupado pero que queda dentro del perímetro, provocando que, en algunos casos, algunos clusters se separen demasiado de lo que podría ser una mejor ubicación. En cualquiera de los dos casos, si el nuevo cluster se superpone con alguna de las envolventes, se va alejando en la dirección respecto a su predecesor en el mst donde debía haber sido situado, con la posibilidad de ubicarlo en un ángulo de ciento veinte grados, de la misma forma que con los nodos en el apartado 4.1.2. Tanto los dos tipos de perímetro que se han utilizado, como la detección de puntos interiores y de solapamiento entre polígonos es la misma que se ha utilizado en la representación vista en el capítulo 4. Finalmente se ha decidido utilizar la comparación con el perímetro de cada cluster de forma independiente en la versión definitiva. A continuación se muestran los resultados de los cuatro hiperclusters que forman el grafo con los genes de muestra utilizados. 2 – 7 Selección de genes que vinculan otros genes[Revisar que la traducción no se Chévere] 2 – 7 – 1 Hierarchical Clustering En el Hierarchical Clustering, los genes son agrupados por una función de similitud aplicada a sus patrones de expresión. Para construir el Hierarchical Clustering, en cada paso, un gen o un cluster de genes se añaden a un gen, o cluster de genes, previamente añadido siguiendo la mejor correlación no añadida todavía. Como resultado, se obtiene un dendograma. El Hierarchical Clustering construye con los genes de la Tabla I,(si citas una tabla, has de poner esa tabla en el documento y correctamente numerar todas las tablas y citarlas por su numeración) usando single linkage y el factor f como función de similitud, el hierarchical clustering que se muestra en la siguiente figura. Página 24 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Obsérvese que de esta manera no se clasifican los genes por similitud en la expresión, pero sí por su valor de f. Por lo tanto, los clusters contendrán los genes los cuales sus relaciones demuestran un valor bajo de f, incluso si estas relaciones son de diversos tipos. Usando single-linkage, podemos garantizar que los genes que pertenecen a clusters diferentes son realmente independientes. La equivalencia entre patrones de expresión implica la semejanza en las relaciones de estos genes. La probabilidad de que dos patrones de expresión sean similares se presenta cuando el número de muestras cae. El punto clave para discriminar entre pares similares de nubes de muestras es la alta precisión del PCOP calculando el grado de correlación (el factor f). Como se demuestra en el Hierarchical Clustering representado en la figura, los genes los cuáles aparecen en el fondo del árbol tienen las correlaciones más altas (por lo tanto, es probable que tengan funcionalidades relacionadas). En general está muy mal redactado, y muy mal traducido, corrige las anteriores secciones que has redactado tu o traducido tu del inglés. Si haces referencias bibliográficas acuerdate de añadir las referencias al final del documento. Si haces referencias a factores f, o similares, tienes que asegurarte que se han explicado antes y hacer referencia a donde se han explicado (la sección). Las figuras del documento han de ir numeradas de la primera hasta la última, en orden creciente, y desde el texto hacer referencia a estas por su numeración. 2 – 7 – 2 Algoritmo de Selección Algoritmo de Selección Usando sólo el grafo o red es imposible notar un comportamiento específico entre las redes de genes. Para examinar este comportamiento en detalle, es necesaria la operación Página 25 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Zoom-in. En esta operación, los investigadores introducen los genes de interés. Considerando cuales de las consultas de genes introducidas por el investigador tienen un cierto nivel de correlación es el conjunto (nivel de correlación el cual el investigador no desea perder), el primer paso de la operación Zoom-in es seleccionar el máximo número de genes que conectan con el conjunto de consulta, pero que conservan el nivel de correlación del conjunto de la consulta en el nuevo conjunto query-plus-selectedgenes. Recordar que cada gene es una variable en un espacio multidimensional cuando se calcula la PCOP en un conjunto y su correspondiente valor f. Algoritmo de Selección siguiendo el Minimum-spanning tree[revisar esta traducción ya que no la veo muy correcta. No se si sería mejor hacer un resumen más corto, creo haber entrado demasiado en detalle] Hemos descrito las propiedades del Hierarchical Clustering, pero para seleccionar genes sólo necesitamos el Minimum-spanning tree implícito en él. Para el Algoritmo de Selección, seleccionamos los genes (nodos) del Minimumspanning tree, los cuales conectan los genes consultados siguiendo el Minimumspanning tree entre ellos. Esta selección cumple los objetivos de selección inicialmente descrita, y un algoritmo eficiente para llevar a cabo esta tarea, son descritos. Borrar texto coloreado Cuando construimos un Hierarchical Clustering usando single linkage, obtenemos un Minimum-spanning tree donde cada arista del árbol representa la relación usada para añadir cada nuevo gen o cluster de genes al hyerarchical clustering (Gower y Ross 1969), En este sentido, podemos aplicar sus clusters, su jerarquía y demás propiedades del Hierarchical Clustering a su correspondiente Minimum-spanning tree. La figura (B) de la sección Minimum-spanning tree muestra ésta correspondencia. Las figuras las has de numerar para todo el documento, no por secciones, Todo el texto pintado de marrón ha de borrarse: De esta manera podemos formular las siguientes definiciones: Un conjunto de genes enlazado por sus mejores correlaciones podría ser considerado como un cluster. Estos enlaces pueden llamarse relaciones intra-cluster. Un par de genes cuya relación intracluster de cada uno con el otro miembro del par pueden ser llamados par mínimo intracluster. Cada cluster puede estar presente en uno y sólo un par mínimo intra-cluster. Siguiendo las relaciones intra-cluster que enlazan a miembros del cluster, hay un camino entre cada gen del cluster y el par mínimo intra-cluster. Eso implica que el par mínimo intra-cluster será accesible desde cada gen del cluster siguiendo la mejor correlación de cada gen a través del camino. Observar que desde cada gen, una y sólo una relación intra-cluster lo deja, pero cualquier relación intra-cluster pueden alcanzarla. En la figura comentada antes puede verse dos clusters y sus respectivos pares mínimos intra-cluster puede ser observado (representados en el grafo b por la relación con los rangos 0 y 3). En Hierarchical Clustering, los clusters están enlazados a la jerarquía cluster-tree usando la mejor relación entre uno de estos genes con el resto de genes externos al cluster. Esta mejor relación del cluster puede ser nombrada relación Inte.-cluster. Para Página 26 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 cada cluster una sólo una relación intra-cluster puede dejarla, pero cualquier relación Inter-cluster puede alcanzarla. Ahora, para seleccionar los genes, sólo se necesita cargar las mejores correlaciones entre los genes y los cluster (relaciones intra-cluster y inter-cluster) y seguir hacia las parejas minimum inter-cluster y intra-cluster desde la consulta de genes buscada para el punto de partida. En este sentido, seguimos la trayectoria de los genes (nodos) del minimum-spanning path seleccionados con la consulta de genes. Centrándose en la descripción del algoritmo, este comienza desde la consulta de genes, que cogerá la peor relación intra.-cluster en cada paso. Si los diferentes caminos no se cruzan, porque las consultas de genes no pertenecen al mismo cluster, el algoritmo buscará el cluster de encuentro siguiendo la relación inter-cluster, cogiendo la peor relación inter-cluster en cada paso también. Para cada cluster visitado, el algoritmo repetirá el proceso para seleccionar los genes visitados que cruzan el cluster. El algoritmo efectuará de la misma manera para tratar los clusters de clusters. De esta manera, el algoritmo solo necesitará la mejor correlación de cada gen y de cada cluster (relaciones intrac-cluster y inter-cluster) para establecer la selección de gen para todo el conjunto posible de consultas de genes. Ahora, hay dos puntos calientes que mencionar sobre las propiedades del minimumspanning tree: 1. La relación inter-cluster siempre representa la peor correlación de las relaciones intra-cluster del gen del cual primero la deja. La relación inter-cluster que deja el cluster siempre representa la mejor correlación inter-cluster que alcanza el cluster. Por eso, en el camino que cruza el cluster (el cual siempre cruza el par minimum intra-cluster), el camino entre el par minimum intra-cluster y el gene desde el cual deja la relación inter-cluster usualmente representa la mejor correlación entre los camino entre los genes que alcanza la relación inter-cluster y el par minimum intra-cluster. 2. En el camino desde el cluster hasta el par minimum inter-cluster, cada relación inter-cluster cruzada representa una mejor correlación más cercano al par mínimo que es. Por tanto, el camino que cruza el cluster desde el gene el cual recibe la relación inter-cluster hacia el gene desde el cual la relación intercluster del cluster lo deja) usualmente representa una mejor correlación el más cercano al par mínimo que es el cluster. Estas dos propiedades permiten a los científicos investigar los objetivos seleccionados inicialmente esperados. Primero, el conjunto de los genes seleccionados tenderá a maximizar la correlación entre ellos mismos y el conjunto de genes seleccionados respecto a cualquier otro conjunto de genes con el mismo número de genes. Segundo, el sistema tenderá a seleccionar el máximo número de genes para conectar los diferentes genes consultados sin perder el grado de correlación que estos mantienen. En este caso la correlación a través de los genes seleccionados siempre estará sujeta a la microarray de genes y las sample conditions para construir el árbol de partida (un pobre rango de samples conditions o una carencia de genes relevantes podría significar que los resultados serán poco precisos). Página 27 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 El texto de esta sección ha estado corregido, pues la traducción del inglés era pésima, teniendo en cuenta a que trabajando en el tema deberías entender de que se habla. Bueno, corrige la traducción de las anteriores secciones basándote en esto. 2 – 8 Definir clases de muestra y estudiar su efecto sobre las relaciones 2 – 8 – 1 Clustering La PCOP se define mediante la generalización, a nivel local, de las propiedades de la varianza de los componentes principales para un espacio multidimensional. Del espacio muestral proporcionado, el cálculo de las PCOP obtiene una serie de estados discretizados calculados a nivel local.. Estos estados representan los POPs (Principal Oriented Points), y conforman la PCOP (Principal Curve of Oriented Points) o patrón subyacente. El usuario puede desear conocer que muestras han contribuido a generar cada uno de estos POPs para entender como han afectado estas al patrón subyacente. De esta forma, el investigador puede examinar con detalle los diferentes comportamientos locales de la PCOP. La aplicación de Clustering (Agrupación) proporciona esta y otras interesantes posibilidades. La Graphical Interface genera los POPs de forma interactiva, permitiendo al usuario seleccionarlos y manipularlos de diversas maneras: Usando la herramienta de Selección para señalar uno o varios POPs , diferenciando los POPs actualmente seleccionados del resto. Los POPs pueden seleccionarse en cualquiera de las gráficas (tanto geométricas como paramétricas); la selección del usuario se mantendrá para todas ellas. Se pueden agrupar las muestras que abarca la selección actual de POPs en varios grupos o clusters (actualmente 8) facilitados por la aplicación que se mostrarán de distinto color en las gráficas geométricas, para poder analizar grupos de muestras de diferentes selecciones de POPs y hacer un análisis simultáneo de varias de ellas. Si el usuario lo desea puede descargar tres ficheros con las muestras pertenecientes a los grupos seleccionados para su examen posterior, o como plantilla para la herramienta Colouring (que se explica a continuación), o como nuevos datos de entrada para la herramienta Pattern Analysis. 2 – 8 – 2 Colouring Las muestras que conforman la nube de puntos discretos a analizar representan, en el caso de análisis de microarrays, las expresiones de los genes respecto a múltiples experimentos. Mediante la representación geométrica, el usuario obtiene una representación visual de los valores de la muestras de entrada para cada combinación de pares de variables de las muestras introducidas. El investigador puede desear colorear entonces, varias de estas muestras para facilitar su seguimiento en las diferentes vistas, correspondientes a cada combinación de pares de Página 28 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 variables, o bien entre diferentes Interfaces si las diferentes combinaciones de variables se han estudiado como diferentes experimentos mediante la herramienta de Pattern Analysis. Para ello, la Graphical Interface proporciona la aplicación de Colouring (Coloración), que permite manipular de múltiples formas grupos de muestras y colorearlos:: El usuario puede formar varios grupos de muestras (actualmente 8); esas muestras se colorarán de distinto color que las muestras no seleccionadas o las muestras de otros grupos (el color de los distintos grupos puede cambiarse según las preferencias del investigador). Se pueden modificar los grupos tantas veces como desee o eliminar las selecciones realizadas. Los diferentes grupos seleccionados pueden activarse o desactivarse, permitiendo o impidiendo su coloración sobre las diferentes vistas de la representación geométrica. Así, podemos seleccionar varios grupos de muestras y estudiarlos de forma independiente o bien conjuntamente con los grupos que deseemos. Las muestras pueden o bien seleccionarse mediante la aplicación Clustering explicada en el apartado anterior, o bien manualmente por rango de valores. Si el usuario lo desea puede descargar tres ficheros con las muestras pertenecientes a los grupos seleccionados para su examen posterior, o como plantilla para esta misma herramienta, o como nuevos datos de entrada para la herramienta Pattern Analysis. [La sección siguiente es la traducción más o menos de la documentación de JUNG intentando dar una vista general de las posibilidades. Dime si es extensa, si no, si es demasiado teórica, es explicar como generar un grafo, etc etc….] Entras mucho en detalle, pero eso no tendría que ser más problema que confundir al jurado en que has hecho tu y que no. Lo problemático es que metes mucha info de clases y propiedades que tu no usas. Y esas sobran. Solo has de citarlas en tu discusión de porque has implementado las cosas de cierta manera, pero solo citandolas y explicando el porque de tu decisión, y no en esta sección. En resumen, que borres del apartado 3, todo lo que tu no uses a partir de la sección “grafos vértices y aristas”. 3 – Librerías JUNG 3 – 1 Introducción 3 - 1 - 1 Descripción JUNG(Java Universal Network/Graph Framework) es una biblioteca de software que proporciona un lenguaje común y extensible para modelar, analizar y visualización de los datos que se pueden representar como un grafo o red. Se escribe en Java, que permite que las JUNG-based applications hagan uso de las extensas capacidades incorporadas en la API de Java, así como los de otras bibliotecas de terceras personas existentes de Java. Página 29 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 La arquitectura de JUNG se diseña como ayuda para el desarrollo de una gran variedad de representaciones de entidades y sus relaciones, tales como grafos dirigidos y no dirigidos, grafos multimodales, grafos con aristas paralelas e hipergrafos. Proporciona un mecanismo para describir grafos, entidades, y relaciones basados en metadata. Esto facilita la creación de herramientas analíticas para conjunto de datos complejos que pueden examinar las relaciones entre estas entidades así como las metadatas unidas a cada entidad y relación. La distribución actual de JUNG incluye la implementación de un gran número de algoritmos de teoría de grafos, minería de datos, y análisis de redes sociales, tal como rutinas de clustering, de descomposición, de optimización, generación aleatoria de grafos, análisis estadístico, y el cálculo de distancias en grafos, de flujos, y de otras medidas de importancia (centrality, PageRank, HITS, etc.). JUNG también proporciona un framework de visualización que hace más fácil construir herramientas para la exploración interactiva de los datos de la red. Los usuarios pueden utilizar uno de los algoritmos de layout proporcionados, o utilizar el propio framework para crear sus propios layouts personalizados. Además, los mecanismos de filtro que se proporcionan permiten que los usuarios enfoquen su atención, o sus algoritmos, en partes específicas del grafo. Como biblioteca open-source, JUNG proporciona un framework común para el análisis y la visualización de grafos y redes. 3 - 1 - 2 ¿Por qué existe JUNG? Según la documentación oficial del proyecto JUNG, la creación del framework fue una percepción de la necesidad de crear una herramienta genérica, flexible y potente para la creación, manipulación, análisis y visualización de Grafos y Redes en Java. El hecho de que no existieran otras herramientas o APIS para este objetivo, hizo que se trabajara en el desarrollo de una nueva ya que ninguna de las anteriores satisfacía las necesidades y requerimientos en el marco de los proyectos que desarrollaban los autores en sus respectivos departamentos. Aún así, existen otras herramientas que se pueden adecuar más a las necesidades y capacidades específicas de otros proyectos de menor envergadura. 3 - 1 - 3 ¿Qué es y qué no es JUNG? JUNG es un framework que permite la creación de herramientas de diseño y visualización de grafos y redes. Puede ser utilizado en el marco de creación de pequeñas porciones de código para probar ideas o en la creación de herramientas con una interfaz gráfica de usuario sofisticada. JUNG no es en si misma una herramienta final (ni lo intenta ser). Es posible construir una herramienta basada en JUNG, pero para ello es necesario conocer el lenguaje de programación Java. JUNG proporciona pequeños ejemplos para poder desarrollar pequeñas tareas, pero son ejemplos de cómo utilizar JUNG, no son ejemplos de herramientas en el sentido del propio significado de la palabra. Página 30 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Pasamos a hacer un pequeño resumen de las posibilidades del framework donde podremos ver algunas de los objetos usados en este proyecto, no todos, pero si las clases y objetos básicos de los cuales se han derivado los objetos creados para satisfacer los objetivos de éste. La intención de los siguientes apartados es explicar a grandes rasgos las operaciones y las funcionalidades básicas que componen este framework para que una persona con unos mínimos conocimientos de Java pueda usarlo. 3 – 2 Grafos, Vértices y Aristas 3 – 2 – 1 Propiedades y Operaciones básicas Grafos, Vértices y Aristas tienen, cada uno, propiedades que se pueden extraer de ellos, y operaciones que pueden realizar ellos (o que se pueden realizar sobre ellos). Las operaciones enumeradas en la parte inferior tienen el comportamiento garantizado para cualquier Grafo, Vértice o Arista que se hayan definido en JUNG. Dependiendo del tipo específico de Grafo, Vértice o Arista, y de la implementación realizada, un objeto como estos, puede tener otras operaciones y características disponibles. Grafos: newInstance(): Retorna un grafo del mismo tipo del grafo que invoca éste método. addVertex(v): Añade un nuevo Vértice a este Grafo y devuelve una instancia del mismo. addEdge(e): Añade una nueva arista a este Grafo y devuelve una instancia de la misma. getVertices(): Devuelve el conjunto de Vértices que tiene el Grafo. getEdges(): Devuelve el conjunto de Aristas que tiene el Grafo. numVertices(): Retorna el número de Vértices que tiene el Grafo. numEdges(): Retorna el número de Aristas que tiene el Grafo. removeVertex(v): Elimina el Vértice v del Grafo. removeEdge(e): Elimina la Arista e del Grafo. removeVertices(s): Elimina todos los Vértices del conjunto s en el Grafo. removeEdges(s): Elimina todas las Aristas del conjunto s en el Grafo. removeAllVertices(): Elimina todos los Vértices del Grafo. removeAllEdges(): Elimina todas las Aristas del Grafo. copy(): Realiza una copia del Grafo y de todo su contenido. Vértices: getGraph(): Retorna una referencia del Grafo que contiene este Vértice. getNeighbours(): Retorna un conjunto con todos los Vértices conectados por aristas a éste mismo. getIncidentEdges(): Retorna un conjunto con todas las Arista incidentes a éste Vértice. degree(): Retorna el número de Aristas incidentes a éste Vértice. getEquivalentVertex(g): Retorna el Vértice en el Grafo g especificado, si éste, es equivalente al Vértice dado. isNeighbor(v): Retorna true si el Vértice especificado v y el Vértice dado, están conectados por, al menos, una Arista, false sino. Página 31 de 97 Darío Peña Seoane isIncident(e): Fecha de creación 11/11/2007 81946322 Retorna true si la Arista e es incidente en el Vértice dado, false sino. Elimina todas las Aristas del Grafo que son incidentes en este Vértice. copy(g): Crea una copia de este Vértice en el Grafo g especificado. removeAllIncidentsEdges(): Aristas: getGraph(): Retorna una referencia del Grafo que contiene esta Arista. getIncidentVertices(): Retorna el conjunto de Vértices que son incidentes a esta Arista. getEquivalentEdge(g): Retorna la Arista en el Grafo g especificado, si ésta, es equivalente a la Arista dada. numVertices(): Retorna el número de Vértices incidentes en esta Arista. isIncident(v): Retorna true si el Vértice v especificado es incidente en esta Arista, false sino. copy(): Crea una copia de esta Arista en el Grafo g especificado. 3 – 2 – 2 Tipos El package Graph contiene especificaciones (mediante Java interfaces), con varios niveles de abstracción, para grafos, vértices y aristas. ArchetypeGraph, ArchetypeVertex, y ArchetypeEdge La interfaz Archetype especifica el comportamiento de grafos generalizados, vértices y aristas; estos se diseñaron para abarcar todo tipo de grafos, incluyendo grafos dirigidos y grafos no dirigidos, grafos con datos incluidos (Ej. aristas con peso), hipergrafos, y grafos con aristas paralelas. Todas las implementaciones de los grafos, vértices y aristas deben implementan una de estas interfaces (o una interfaz que herede de estas interfaces). Los métodos enumerados anteriormente están disponibles para los objetos que implementan dichas interfaces. Graph, Vertex y Edge Estas interfaces heredan de las interfaces Archetype y especifican el comportamiento para los Grafos (binarios) en los que cada arista conecta exactamente dos vértices; esta limitación permite la definición de un gran número de nuevos métodos. DirectedGraph y DirectedEdge es un tipo de arista que impone un orden en los vértices incidentes. DirectedGraph es una interfaz etiquetada para implementaciones de Graph en los cuales su conjunto de aristas son implementaciones de DirectedEdge. Así, por ejemplo, el autor de un método que se crea para operar sólo con grafos dirigidos debe asegurar que el argumento del grafo pasado al método debe ser un DirectedEdge DirectedGraph. UndirectedGraph y UndirectedEdge Estas interfaces son análogas a las correspondientes DirectedGraph y DirectedEdge mencionadas anteriormente, pero para grafos no dirigidos y aristas no dirigidas (donde no se impone un orden en los vértices incidentes). Página 32 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 El package graph.impl contiene varias implementaciones de estas especificaciones del package Graph. Actualmente, todo el código de este package está diseñado para soportar grafos binarios. AbstractSparseGraph, AbstractSparseVertex y AbstractSparseEdge Estas clases son el esqueleto de las implementaciones de las interfaces Graph, Vertex y Edge. Este intento es para minimizar el esfuerzo requerido para implementar dichas interfaces, mientras no sea necesario saber si el grafo es o no dirigido. Estas clases, y todas las heredadas a partir de ella, están diseñadas para grafos donde, sólo en algunas ocasiones, el número de aristas es superior al de vértices. Esta no es la mejor implementación para manipular grafos densos, donde cada vértice está conectado a varios vértices. Al ser clases abstractas, el usuario no puede crear instancias de ellas. DirectedSparseGraph, DirectedSparseVertex y DirectedSparseEdge Estas clases extienden las clases abstractas de Graph, Vertex y Edge para grafos dirigidos; las clases Graph y Edge implementan DirectedGraph y DirectedEdge interfaces, respectivamente. UndirectedSparseGraph, UndirectedSparseVertex y UndirectedSparseEdge Estas clases extienden las clases abstractas de Graph, Vertex y Edge para grafos no dirigidos; las clases Graph y Edge implementan UndirectedGraph y UndirectedEdge interfaces, respectivamente. 3 – 2 - 3 Creando y Añadiendo Elementos Crear un grafo es directo: llamar al constructor del tipo de grafo deseado. Graph g = new DirectedSparseGraph(); Crea un nuevo grafo dirigido y lo asigna a la variable del tipo Graph. (Mirar la Javadoc para los detalles del tipo Graph y de la implmentación DirectedSparseGraph) También puede crear un grafo leyendo éste desde un fichero (comentado posteriormente en la sección Entrada y Salida) o generándo un random graph (comentado posteriormente en la sección Algoritmos). Una vez haya creado el grafo, puede crear vértices y añadirlos al grafo: Vertex v1 = (Vertex) g.addVertex(newDirectedSparseVertex()); Vertex v2 = (Vertex) g.addVertex(newDirectedSparseVertex()); y una vez tiene vértices, puede conectarlos con aristas: DirectedEdge e = (DirectedEdge) g.addEdge(new DirectedSparseEdge(v1,v2)); Se puede observar que se crean vértices y aristas y se agregan al grafo combinando dos operaciones en sólo una línea de código. La naturaleza de estas dos etapas del proceso permiten crear vértices o aristas “huérfanos” y que no formen parte de ningún grafo. Página 33 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Esto se da como compromiso entre las common practices en las APIs de Java y los efectos secundarios de constructores y la semántica de grafos. Sin embargo, el comportamiento de un método JUNG para aristas o vértices, con la excepción del método getGraph(), no está especificad para vértices/aristas huérfanos. Las implementaciones de JUNG nunca crearán este tipo de elementos, y se recomienda que los usuarios sigan está práctica jerarquizando la llamada al constructor dentro del método que agrega ese elemento al grafo (como en los ejemplos mostrados). Algunas restricciones a tener en cuenta: Un vértice/arista sólo puede formar parte de un grafo al mismo tiempo. Un vértice/arista sólo puede ser añadido a un grafo al mismo tiempo. Una arista no puede ser creada y ser incidente en un vértice huérfano. Una arista no puede ser creada uniendo vértices incidentes en diferentes grafos. El vértice creado debe de coincidir con el tipo de grafo donde se añade. (Así, por ejemplo, no se puede añadir un DirectedSparseVertex en una implementación UndirectedGraph). La arista creada debe coincidir con el tipo de vértice que conecta, y con el tipo de grafo en el cual es añadida. Si algunas de estas restricciones no se cumple, se genera un error en tiempo de ejecución, y se genera una excepción del tipo FatalException . Todas estas restricciones son detectadas en cuanto ocurren, pero puede ocurrir que algunas de estas no sean tan evidentes y el error que se genere sea más sutil y por tanto más difícil de detectar. 3 – 2 – 4 Equivalencia y Copia de Objetos Puede realizar la copia de un grafo, de un vértice o de una arista desde un grafo (el original) a otro (nuevo grafo). La copia de un vértice o de una arista realiza tres acciones: El nuevo vértice o la nueva arista es creada en el nuevo grafo, y del mismo tipo que los originales. Todos los datos de usuario son respetados en la copia y son copiados desde el elemento original al copiado. (El comportamiento de cómo se copian los datos de usuario cuando el original se copia es discutida en la sección User Data) Una relación de equivalencia es creada entre el vértice/arista original ( y los vértices/aristas con los que es equivalente el vértice original) y la copia. La copia de un grafo realiza tres acciones: Se crea un nuevo grafo del mismo tipo que el original. Todos los datos de usuario son respetados en la copia y son copiados desde el elemento original al copiado. (El comportamiento de cómo se copian los datos de usuario cuando el original se copia es discutida en la sección User Data) Página 34 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Cada vértice y arista del grafo original se copian (como se comentó anteriormente) al nuevo grafo. El siguiente código crea un grafo, crea dos vértices y una arista y los añade a éste, entonces, copia cada vértice y la arista desde el grafo original a un nuevo grafo destino. Graph original = new DirectedSparseGraph(); Vertex v1_orig = original.addVertex(new DirectedSparseVertex()); Vertex v2_orig = original.addVertex(new DirectedSparseVertex()); DirectedEdge e_orig = original.addEdge(newDirectedSparseEdge()); Graph target = new DirectedSparseGraph(); Vertex v1_copy = v1_orig.copy(target); Vertex v2_copy = v2_orig.copy(target); DirectedEdge e_copy = e_orig.copy(target); Los vértices v1_copy and v2_copy son equivalentes a los vértices v1_orig y v2_orig, respectivamente, y la arista e_copy es equivalente a la arista e_orig. Esto implica, que cada uno de las siguientes declaraciones sean evaluadas a true: v1_orig == v1_copy.getEquivalentVertex(original); v2_orig == v2_copy.getEquivalentVertex(original); v1_copy == v1_orig.getEquivalentVertex(target); v2_copy == v2_copy.getEquivalentVertex(target); e_orig == e_copy.getEquivalentEdge(original); e_copy == e_orig.getEquivalentEdge(target); Como conveniencia, los métodos Java equal están implementados para respetar esta relación de equivalencia, así, las declaraciones siguientes serán evaluadas a true: Página 35 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 v1_orig.equals(v1_copy); v1_copy.equlas(v1_orig); v2_orig.equals(v2_copy); v2_copy.equals(v2_orig); e_orig.equals(e_copy); e_copy.equals(e_orig); Hay algunas restricciones que gobiernan la manera de cómo un vértice o una arista pueden ser copiadas: El grafo original y el destino pueden no ser iguales. Los vértices incidentes de una arista deben tener equivalencia en el grafo destino para poder copiar ésta en éste (así, en el ejemplo anterior, no podríamos haber copiado la arista e_orig hasta no haber copiado sus vértices incidentes v1_orig y v2_orig) Dos vértices equivalentes, o dos aristas, no pueden existir en el mismo grafo. Así un vértice o una arista no pueden ser copiados en un grafo si en éste existe un elemento equivalente. 3 – 2 – 5 Eliminando Vértices y Aristas Para eliminar un vértice o una arista de un grafo, se debe invocar al método apropiad de eliminación: g.removeEdge(e); g.removeVertex(v); Eliminar una arista del grafo no afectará cualquier otra pare del grafo. Eliminando un vértice del grafo podría provocar que las aristas incidentes con este vértice sean eliminadas si estas se convierten en aristas ill-formed (Una arista ill-formed es aquella arista que es incidente a un número erróneo de vértices. In grafos donde las aristas están definidas para conectar exactamente dos vértices, eliminar una vértice provocará el borrado de todas sus aristas incidentes). Eliminar un elemento de un grafo no libera la memoria usada para almacenar este objeto. (De hecho, se puede eliminar un elemento del grafo y re-insertarlo en este u otro grafo diferente). Como en todos los programa Java, the Java garbage collector es el responsable de liberar memoria de un objeto si éste lleva un tiempo sin usarse. Eliminar un elemento de un grafo no siempre elimina ninguna estructura de datos de usuario (discutido en la sección User Data); los usuarios son responsables de actualizar esas estructuras si es necesario. 3 – 3 User Data Los usuarios pueden asociar datos a los grafos, a las aristas y a los vértices de dos maneras: extensión de clases y el mecanismo de anotación de JUNG built – in. 3 – 3 – 1 Extensión de Clases El usuario puede extender las clases proporcionadas de manera que incluyan variables/propiedades (y métodos para manipular estos campos) que el usuario desee. Este mecanismo es muy apropiado para aplicaciones que se diseñan para operar con Página 36 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 conjuntos específicos de datos, donde cada uno de estos elementos tiene propiedades conocidas. Por ejemplo, una red que representa una autopista puede almacenar, para cada tramo de la autopista entre sus salidas (Ej., una arista) la longitud de ese tramo. La posibilidad para extender las clases de JUNG es una característica del lenguaje Java, y no es sólo específico de JUNG. Sin embargo, éstas clases deben asegurarse de que las clases AbstractSparse usen el método Object.clone() para copiar vértices, aristas y grafos; por lo tanto, las copias de estos objetos serán del tipo “shallow copies”. (Para más información de la clonación de objetos, y los tipos de copia deep y shallow, consulte el Java Tutorial). El siguiente ejemplo crea una clase haciendo un extends de la clase DirectedSparseVertex y lleva con él algunos de sus propios datos de ejemplo. Se puede observar que la rutina parece exactamente una extensión de la clase estándar de Java. PersonVertex extends DirectedSparseVertex { private String name; private List publications; public PersonVertex( String name, List publications ) { this.name = name; this.publications = publications; } public List getPublications() { return publications; } } Pueden existir circunstancias bajo las cuales es mejor almacenar la información a través del mecanismo de anotación discutido más adelante, o el sistema de extends de la clase. En particular, el mecanismo de anotación es sustancialmente más flexible que la extensión de clases. Y es por ello que muchos de los objetos del proyecto son mecanismos de anotación para poder acceder flexible y rápidamente a la información, proporcionada por el preproceso, del grafo. 3 – 3 – 2 Anotación JUNG El package JUNG utils provee un mecanismo built-in, la clase UserData, para almacenar elementos con datos incorporados. Este mecanismo es muy apropiado para manejar datos que puedan ser de tipo temporal o específicos (Ej., datos que no todos los elementos del mismo tipo de un grafo tenga o necesiten). Cada implementación de un grafo JUNG, vértice o arista extiende la clase provee las siguiente operaciones: UserData y addUserDatum(key, datum, copyaction): Añade el objeto específico datum con su key específica, para poder recuperarlo posteriormente del repositorio de datos de usuario de dicho objeto, y con su específica copyaction. getUserDatum(key): Recupera el objeto asociado a su key específica de recuperación desde el repositorio de datos de usuario de dicho objeto. removeUserDatum(key): Elimina el objeto asociado a su key específica de recuperación desde el repositorio de datos de usuario de dicho objeto. setUserDatum(key, datum, copyaction): Reemplaza el objeto con su key específica, para poder recuperarlo posteriormente del repositorio de datos de Página 37 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 usuario de dicho objeto, y con su específica copyaction. Si el objeto no existe, este método es equivalente a AddUserDatum(key, datum, copyaction). importUserDatum(udc): Recupera los datos de usuario almacendos en udc (el repositorio de datos de usuario de otro elemento del grafo) y copia éste a este objeto del repositorio de datos de usuario, acorde con las restricciones de cada copyaction. getUserDatumKeyIterator(): Retorna un iterator del objeto que almacena el conjunto de key del repositorio de datos de usuario; esto permite al usuario examinar el contenido del repositorio de datos de este objeto. getUserDatumCopyAction(key): Recupera la copyaction del datum con la key específica de recuperación para este objeto del repositorio de datos del usuario. (El proposito y la semántica de las copyactions se discute en la sección posterior titulada Copiando User Data) Aquí tenemos un ejemplo de cómo estos datos de usuario son almacenados, como podemos acceder a ellos, modificarlos y eliminarlos: Vertex v = (Vertex) g.addVertex(new DirectedSparseVertex()); Vertex w = (Vertex) g.addVertex(new DirectedSparseVertex()); String name_key = "name"; String current_address_key = "address"; String current_student_key = "student"; v.addUserDatum(name_key, "Carl Jung", UserData.SHARED); w.addUserDatum(name_key, "Sigmund Freud", UserData.SHARED); v.addUserDatum(current_address_key, "Vienna, AU", UserData.SHARED); v.addUserDatum(current_student_key, w, UserData.REMOVE ... String v_name = v.getUserDatum(namekey); v.setUserDatum(current_address_key, "Basel, SW",UserData.SHARED); v.removeUserDatum(current_student_key); Este ejemplo muestra como los userdata pueden contener cualquier objeto de Java, incluyendo otros vértices. 3 – 3 – 3 Copiando User Data Cuando un elemento del grafo es copiado (con el método copy), este nuevo elemento creado b invoca importUserData(a), el cual procura copiar cada uno de los objetos del repositorio de datos del usuario de a al repositorio de datos de usuario del b. El comportamiento de cada intento de copia, dependerá de la copy action especificada cuando el correspondiente objeto fue creado. La interfaz UserDataContainer contiene una interfaz llamada CopyAction, la cual consiste en un método simple de firma, onCopy(value, source, target). importUserData(a) recupera la copy action de cada elemento del repositorio de datos de usuario. Esta copy action llama al método onCopy(datum, a, b), y basándose en su resultado, decide que hacer con la específica datum. JUNG provee tres implementaciones diferentes de UserData.REMOVE y UserData.SHARED. CopyAction: UserData.CLONE, UserData.CLONE’s, versión del método onCopy(), devuelve una copia del datum del usuario, definido éste por el método de Java clone(); importUserData, entonces, coloca Página 38 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 esta copia en el repositorio de datos del usuario del grafo destino. Esta clonación es completamente independiente de la original. (Si el datum del usuario no soporta el método clone(), onCopy generará una excepción Java, CloneNotSupportedException). UserData.SHARED’s, versión del método onCopy(), devuelve una referencia del datum original del usuario; importUserData, entonces, coloca esta referencia en el repositorio de datos del usuario del grafo destino. Así, cualquier cambio en el datum del usuario que sea hecho por uno de sus elementos del grafo, se verá reflejado en todos los elementos que compartan dicho datum del usuario. UserData.REMOVE’s, versión del método onCopy(), devuelve null; esto es, los datos de usuario que se creen con esta copy action no serán copiados con el método copy(). 3 – 4 Decorators, Indexers y Labellers JUNG incluye unas clases que convenientemente proveen de ejemplos estructurados de uso de repositorios de datos de usuario; estas pueden ser encontradas en el package graph.decorators. Comentaremos brevemente dos de estas clases aquí; para más detalles y ver otros ejemplos disponibles, ver la Javadoc documentation 3 – 4 – 1 Indexer contiene métodos para crear un mapping entre los vértices de un grafo y los enteros {0, 1, …, n-1} (donde n es el número de vértices del grafo). Provee mecanismos para recuperar el índice de un vértice dado (getIndex(v)) o el vértice de un índice específico (getVertex(i)). Entre otras cosas, Indexer también mapea, si lo ve conveniente, un conjunto de vértices en un array, usando el índice de cada vértice como índice dentro del array. Indexer Nota: Si el grafo que está indexado es modificado, el usuario puede llamar el método updateIndex para cerciorarse de que todos los vértices están indexados correctamente. 3 – 4 – 2 StringLabeller es similar a Indexer; proporciona facilidades para encontrar vértices proporcionando un string (etiqueta) o viceversa. Así mismo, las etiquetas son userdefined y estas no necesitan seguir ningún patrón en particular. Vértices no han sido etiquetados simplemente porque no serían accesibles desde el indexer. StringLabeller 3 – 5 Input y Output Actualmente JUNG provee soporte parcial para dos tipos de formato diferentes: el formato Pajek (para lectura y escritura) y el formato de fichero GraphML (lectura sólo). Las clases y métodos relevantes pueden encontrarse dentro del package io. Nota: Consultar la Javadoc documentation para ver la lista de comandos y etiquetas que actualmente soporta los readers y writers de JUNG. Página 39 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 El proyecto JUNG no posee un formato de archivo nativo para la representación de Grafos. 3 – 6 Algoritmos JUNG provee un gran número de diferentes algoritmos para grafos y redes. Generalmente hablando, cada tipo de algoritmo tiene su propio package. Este es uno de los aspectos más complejo y de más rápido desarrollo en JUNG; asegurarse de chequear la Javadoc documentation and release notes para asegurarse de tener toda la información sobre las últimas operaciones disponibles, y cómo usar estas. 3 – 6 – 1 Operaciones en Grafos y Matrices Estos algoritmos están incluidos en el package principal algortihms (en la clase GraphMatrixOperations y la interfaz MatrixElementOperations). Matrices es una de las representaciones más comunes de datos de red. GraphMatrixOperations abarca dos clases de operaciones: estas son, tipicamente, operaciones de cast de matrices, pero que pueden ser eficientemente implementadas aprovenchándose de la extructura de los grafo; y operaciones que usan el package CERN Colt package para la manipulación numérica de matrices. Algunas de estas operaciones en la clase GraphMatrixOperations requiere la implementación de MatrixElementOperations, para especificar el comportamiento de una operación sobre un elemento en particular. Esencialmente, los métodos de MatrixElementOperations especifican como se comporta el vector interno equivalente del producto. Por ejemplo, implementaciones de esta interficie especificarán como los elementos del grafo tratan los valores como numéricos o Booleanos. Actualmente, GraphMatrixOperations contiene las siguientes operaciones: square(g, meo): retorna el grafo correspondiente a el cuadrado de la matriz de adyacencia (matriz de pesos) que especifica la codificación del grafo especificado, donde el elemento de manipulación está definido por el parámetro meo, una implementación de MattrixElementOperations. computeMeanFirstPassageMatrix(g, edgeWeightKey, dist): calcula el all-pairs mean-first passage time (donde los pesos tienen un user data key edgeWeightKey) para el grafo especificado. graphhToSparseMatrix(g, edgeWeightKey): retorna el objeto Colt SparseDoubleMatrix2D que representa los pesos de las aristas (donde los pesos tienen un user data key edgeWeightKey) para el grafo especificado. mapTo1DMatrix(m): retorna el objeto Colt DoubleMatrix1D que corresponde al mapa de vértices especificado m al tipo Double de Java. Los tipos matrix retornados por graphToSparseMatrix y mapTo1DMatrix se pueden pasar a las bibliotecas Colt CERN, que permiten que los usuarios hagan uso de las herramientas proporcionadas por éstas en sus grafos de JUNG. Página 40 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 3 – 6 – 2 Clustering Estos algoritmos están incluidos en el package algorithms.cluster. Un cluster es una colección de objetos donde todos son similares a cada uno en algún aspecto. En una red, la similitud es a menudo basada en propiedades de topología como la conectividad, pero en ocasiones puede estar basada también en propiedades de vértices y aristas de una red. Actualmente, el package contiene las siguientes clases: BicomponentClusterer: Encuentra todos los componentes bipartitos (o bloques) de un grafo no dirigido g, donde cada componente es definido por el máximo inducido del subgrafo bipartito de g. EdgeBetweennessClusterer: Calcula los clusters de un grafo basándose en las propiedades de intermediación (Betweenness) de las aristas (Algoritmo relacionado: BetweennessCentrality, en la sección de Algoritmos Importantes) WeakComponentClusterer: Encuentra componentes débiles en un grafo g, donde una componente débil es definida por la máxima conectividad débil de un subgrafo de g. 3 – 6 – 3 Topología, Caminos y Flujos Estos algoritmos realizan operaciones (y calculan propiedades) en grafos relacionadas con la topología de grafos (esto es, estructuras y subestructuras formadas por los caminos que forman lo vértices por su enlace con las aristas). Esta categoría de algoritmos incluyen las siguientes clases: Package algorithms.connectivity: o BFSDistanceLabeler: Etiqueta cada vértice en el grafo con la longitud del camino más corto sin peso en sus aristas desde un vértice especifico en el grafo. o KNeighborhoodExtractor: Devuelve el subgrafo del grafo de quién sus vértices no están separados más de k aristas desde un vértice específico del grafo. Package algorithms.flows: o EdmondsKarpMaxFlow: Etiqueta cada arista en un grafo dirigido, con el flujo a través de esa arista que es constante con el flujo máximo para el grafo. Package algorithms.shortestpath: o DijkstraShortestPath: Etiqueta cada vértice en el grafo con la longitud del shortest weighted path desde ese específico vértice en el grafo. o UnweightedShortestath: Calcula el shortest path pero de un grafo sin peso en sus aristas. 3- 6 – 4 Importancia Estos algoritmos están incluidos en el package algorithms.importance. Algoritmos de importancia de redes miden la importancia de cada vértice (o arista) de acuerdo con un conjunto de criterios que usualmente se basan en el posicionamiento de este vértice, o arista en relación al resto del grafo. Página 41 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Algunos de los siguientes algoritmos parten de que el grafo es una red de Markov: un grafo directo con peso en sus aristas en los cuales los vértices representan estados, las aristas representan transiciones entre estados, y el peso de éstas representan probabilidades de la transición. La probabilidad estacionaria para un vértice v es la probabilidad limitada a que, dado un estado arbitrario de inicio, y un gran número de transiciones, el estado actual será el de v. Esta categoría de algoritmos incluyen las siguientes clases (añadiendo a otras clases que proveen una relación estructuras entre estas clases): BetweennessCentrality: Etiqueta cada vértice y arista del grafo con el valor que se deriva del número de caminos mínimos que pasan a través de ellos. DegreeDistributionRanker: Clasifica cada nodo según su grado. PageRank: Clasifica cada vértice en una red de Markov modificada según su probabilidad estacionaria. PageRankWithPriors: Clasifica cada vértice en una red de Markov modificada según su probabilidad estacionaria, relativa a un conjunto de vértices raíz. HITS: Clasifica cada vértice en un grafo según su medida de importancia tipo “hubs-and-authorities”. HITSWithPriors: Clasifica cada vértice en un grafo según su medida de importancia tipo “hubs-and-authorities” , relativa a un conjunto de vértices raíz. KStepMarkov: Clasifica cada vértice de acuerdo con una aproximación rápida del algoritmo PageRankWithPriors. MarkovCentrality: Clasifica cada vértice en una red de Harkov según una agregación del primer paso por otros vértices. WeightedNIPaths: Clasifica cada vértice del grafo según la longitud y las trayectorias de los caminos disjuntos que terminan en ese vértice, relativo a un conjunto de vértices raíz. 3 – 6 – 5 Estadísticas Estos algoritmos están incluidos en el package statistics, e incluye las siguientes clases: DegreeDistributions: Clase de funciones para analizar el grado de distribución de un conjunto de vértices. GraphStatistics: Conjunto de medidas estadísticas para las propiedades estructurales de un grafo. Histogram: Clase de propósito general para la representación de distribuciones e Histogramas. 3 – 7 Filtrado El mecanismo de filtrado de JUNG elimina los vértices y las aristas seleccionadas de grafos de entrada, y devuelve nuevos grafos. Estos nuevos grafos son una copia del original, conteniendo las mismas aristas y los mismos vértices, excepto aquellos o aquellas que hayan sido borrados. Un Filter coge un grafo, y retorna un UnassembledGraph. Página 42 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Un UnassembledGraph es un mecanismo de almacenamiento temporal de nodos y aristas: lo lleva a cabo para todos los vértices (y al menos todas las aristas) que serán colocadas al final, filtrando el grafo. En algunas circunstancias, sólo sabiendo que vértices pasaran el filtro es suficiente; esta información puede ser accesible directamente desde el UnassembleGraph con la llamada getUntouchedEdges() y getUntouchedVertices(), las cuales retornan un conjunto de aristas, o un conjunto de vértices que pasan el filtro, respectivamente. Sin embargo, la mayoría de las ocasiones, se necesita acceder al nuevo grafo que pasa el filtro; esto es posible con el método assemble() de la clase UnassembledGraph(), el cual construye el nuevo grafo. Assemble() copia cada vértice que pasa el filtro en el nuevo grafo, y copia cada aristas que pasa el filtro original en el nuevo grafo si ésta es incidente en todos los vértices que pasan el filtro (esto asegura que el resultado sea un grafo well-formed). Resaltar que esto significa que no todas las aristas retornadas con el método getUntouchedEdges() serán copiadas dentro del nuevo grafo. Assemble() puede ser lento, y en algunos casos es deseable encadenar varios filtros en una sola fila y no llamar al método assemble() hasta que el último filtro no se haya ejecutado. Esto esta solucionado creando un filtro que implemente la interfaz EfficientFilter. EfficientFilter es un tipo de filtro que filtra un UnassembledGraph, y retorna otro UnassembledGraph. Un filtro que examina características estructurales de grafos no es, probablemente, muy apropiado para implementar EfficientFilter, porque UnassembledGraph puede contener información topológica incorrecta (en particular, según lo observado anteriormente, el conjunto de aristas puede incluir aristas illformed). Es responsabilidad del usuario determinar cuando un mecanismo de filtro puede ser implementado con EfficientFilter. Mientras el usuario escribe un filtro común simplemente implementando la interfaz, es a menudo más fácil hacer una extensión de una o dos clases base proveedoras Filter, VertexAcceptFilter y EdgeAcceptFilter. Todas estas requieren que el usuario escriba el método boolean acceptVertex(vertex) o bolean acceptEdge(edge), respectivamente. Por defecto, estos no se declaran para ser EfficientFilters; Sin embargo, los usuarios pueden crear extensiones de estos filtros que sean ciertamente EfficientFilter. El mecanismo SerialFilter aplica una serie de filtros secuencialmente a un grafo específico, en el orden en el cual él es añadido al SerialFilter. Cuando el filtro es aplicado, éste chequea para mirar cual de ellos es un EfficcientFilter, y las llamadas assemble que se necesitan. La interfaz LevelFilter fue diseñada para ser usada en conjunción con el mecanismo GraphDraw. LevelFilters son filtros que cogen un parámetro integer, que se usa para determinar la operación de este filtro (por ejemplo, filtrar aristas con su peso más pequeño que el valor de este parámetro). Con LevelFilter, se puede añadir un control tipo slider en una visualización que controle dicho parámetro directamente y así el usuario pueda controlarlo para cambiar el grafo dinámicamente. Documentación detallada y ejemplos de código para filtrar se pueden encontrar en Javadoc para estas clases. Página 43 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 3 – 8 Visualización El package de visualización de JUNG provee mecanismos de presentación y renderización de grafos. Las implementaciones actuales del renderer usan la API de Java Swing para mostrar grafos, pero puede ser implementada usando otros juegos de herramientas. En general, la visualización está compuesta por: Un layout, que coge el grafo y determina la localización de cada vértice que se ha de dibujar. Un (Swing) componente, donde los datos son renderizados. (Implementaciones actuales usan VisualizationViewer, que es una extensión de la clase Swing JPanel). Un renderer, que coge los datos proveídos por el layout y pinta vértices y aristas en el componente proveído. Entonces, seleccionando uno de estos tres, es posible coordinar el dibujado. La implementación por defecto atraviesa el Layout, preguntándole por las localizaciones de los vértices, y pinta estos individualmente con el Renderer encima del componente Swing. Además, la infraestructura GraphDraw simplifica muchas de estas transformaciones empaquetando VisualizationViewer, Render y Layout juntos. Usuarios pueden costumizar el visualizador apropiadamente. (Código de ejemplo disponible en la documentación de GraphDraw). La implementación actual soporta sólo algoritmos de layout de (binarios) grafos 2D; no da soporte de visualización para otros tipos de grafos (como hipergrafos). Este package, y el package visualization.graphdraw, también incluyen utilidades y clases de soporte para facilitar la personalización de la visualización de un grafo. Por ejemplo, vea las notas en FadingVertexLayout para un mecanismo que se puede usar para crear efectos de atenuación cuando los vértices son filtrados y posteriormente restaurados. 3 – 9 Utilidades JUNG incluye un número de clases utilizables, que incluyen: package util: o GraphUtils: Contiene métodos convenientes para operaciones como creación de grafos basados en especificas aristas o vértices. Algunos métodos específicos incluyen: addEdge(graph, vertex1, vertex) Añade una arista en un grafo entre dos vértices. La arista es, adecuadamente, una directedSparseEdge. addUndirectedVertices(graph, n), addVertices(graph, n) Añade n no dirigidos (o dirigidos, respectivamente) vértices al grafo de entrada. getLabel(StringLabeller, vertex) devuelve la etiqueta del vertex de entrada almacenado en StringLabeller. Si el vértice no es miembro del grafo el cual StringLabeller ha etiquetado, y el grafo contiene el vertex equivalente al parámetro, retorna la Página 44 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 etiqueta equivalente. Esto es útil para recoger la etiqueta de un vértice dado si este está siendo ejecutado a través de un filtro. translateAll(vértices,graph), translateAllEdges(edges, graph) devuelve un subconjunto de vértices (o aristas, respectivamente) desde el grafo de entrada que corresponden con los elementos al conjunto de entrada. Esta es la mejor vía para encontrar los vértices originales en un grafo después de que algunas partes de éste hayan sido filtradas. o MutableDouble: Envuelve un valor de la primitiva tipo double en un objeto mutable. o MutableInteger: Envuelve un valor de la primitiva tipo int en un objeto mutable. package random.generator: o EppsteinPowerLawGenerator: Devuelve un grafo no dirigido tal que los grados de los vértices están distribuidos según la ley de la energía. o KleinbergSmallWorldGenerator: Devuelve un grafo con conectividad small-world. 3 – 10 Código de Ejemplo La distribución de JUNG incluye infinidad de ejemplos de código con la proposición de mostrar al usuario como construir tareas simples usando JUNG. Dos de estos ejemplos, los más completos y representativos, y de los cuales, se han sacado la mayoría de las ideas para el desarrollo de la web interface son: SimpleGraphDraw: Muestra una programa simple par visualizar un grafo usando JUNG. ClusteringDemo: Aplicación simple que demuestra como usar filtros, el algoritmo EdgeBetweennesClusterer, y como renderizar usando VertexColorFunction y EdgeColorFunction para crear el contraste visual entre elementos. Además puede ser ejecutado como un Applet de Java. 4 – Aplicación Web para análisis de Microarrays. 4 – 1 Introducción [He hecho primero una explicación de cómo funciona la aplicación del revresearch, espero haberlo entendido bien.] Es mejor que pases de explicar la anterior aplicación, y te centres en explicar en rasgos generales que existe y cita un ejemplo de operaciones permite realizar, pero sin entrar en detalle. Sí explica en detalle la subida de las microarrays, el preproceso, y luego las operaciones que se lanzan desde tu aplicación gráfica. Pero de la actualmente existente no expliques nada, porque te equivocarás. Si que has de explicar el preproceso que se hace cuando la microarray es subida, y como se nutre tu aplicación de el(el factors es calculado a partir de las correlaciones todos con todos que explicas en la introdución en la sección del genetic graph). Luego, en cada aplicación y preproceso que expliques tienes que hacer referencia a la sección de la introducción donde se habla del tema. En la introducción has puesto unas explicaciones de la aplicación (como el pattern análisis Página 45 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 que iría mejor aquí o antes de explicar el clustering, donde está ahora está descolocado) La subida de la microarray está mejor explicada en la sección siguiente en el texto que te pasé. Osea que borralo de aquí. Lo que mejor podrías hacer es eliminar entero este punto 4. Y reutilizar la información válida en la siguiente sección cuando expliques las operaciones que se lanzan desde tu aplicación web. Y sobretodos no repitas explicaciones Tal como se comenta en la introducción del documento, el objetivo de ésta aplicación Web es estudiar las relaciones de las expresiones entre genes desde un tipo de datos llamado microarray con un volumen grande de muestras y relaciones. Estas relaciones van de relaciones lineales, no lineales y excluyentes mutuas hasta complejas dependencias no continuas de expresiones de genes. El sistema está basado en patrones de análisis de relaciones de expresiones (dependencia continua), y el estudio de ejemplos de Microarrays de efectos de condiciones (dependencia no continua) sobre esas relaciones. Hasta ahora, en el IBB existe una aplicación que genera algunas de las operaciones que se desean incluir en la Herramienta Web. A partir de la selección de un microarray, es posible realizar éstas con él para poder extraer información relevante o poder realizar experimentos. Dario estas pantallas son para hacer un upload de una microarray no para seleccionarla. Está muy mal explicado además, no se entiende nada, bueno es normal si dices que son para seleccionarla y no para que el usuario suba su microarray para que pueda analizarla. Y como aclaración, realmente no se ha añadido ningun analisis nuevo con tu applet, solo se ha añadido una interfaz(como máximo la operación de mspath). Página 46 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Página 47 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 todos estos pantallazas y explicaciones asociadas que desaparezcan, pues esta mejor explicado en el texto de la sección siguiente donde se vuelve a explicar lo mismo. Página 48 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Las pantallas anteriores muestran como seleccionar el microarray y como costumizar los ficheros de actualización para hacer el upload del microarray cuando se desee. Notar que estos datos es posible también compartirlos con otros usuarios. Para evitar que existan ficheros de datos repetidos en el sistema, si un usuario quiere dar de alta una microarray que ya existe en el sistema, se desecharán los ficheros subidos por el usuario, y a cambio, el usuario tendrá permisos totales para acceder a la microarray y a toda la lista de genes, de igual modo como si la hubiese dado de alta el mismo. A partir de aquí, para poder realizar los experimentos, por ejemplo un Pattern-Analysis, o poder visualizar las correlaciones de algunos genes en particular, se deben de seleccionar éstos y para ello existen diferentes opciones. Una de ellas es la búsqueda por gen. Otra posible es la de seleccionarlos directamente a través de una lista con todos los genes del microarray. Con la lista de selección de genes es posible realizar diferentes operaciones o preparar “experimentos”. Se puede ver como es posible ver las correlaciones de todos los genes. Página 49 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Este gráfico está mal capturado, cógelo de http://revolutionresearch.uab.es Todas las correlaciones Microarray-pairwise son automáticamente calculadas cuando los datos del Microarray son actualizados. Que estás diciendo? Que son las microarray pairwise?, supongo que te estarás refiriendo a los cálculos de la correlación para pares de genes que se calcula en el preproceso y que has explicado en la introducción. Se puede usar dicha tabla con todos los genes para observar en que proporción están correlacionados un grupo de genes, o un solo gen, con el resto. Es necesario recordar que se trabaja con correlaciones no lineales. Se puede observar también el rango total de correlaciones para un gen en concreto. Para ello en cada fila con el gen que es posible seleccionar, tenemos un icono, el señalado en la figura siguiente donde haciendo clic es posible acceder a las correlaciones de este gen con todos los demás. Página 50 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 La operación Pattern-Analysis es una operación de relación entre genes que se puede lanzar de la misma manera que la anteriormente comentada. Una vez seleccionados los genes para el experimento se pueden normalizar los rangos de expresión de los genes en un formulario habilitado para ello. Página 51 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Haciendo Clic en Launch the Experiment tenemos un nuevo experimento el cual es posible consultar o modificar. Para ello, sobre uno de estos, haciendo clic sobre él, se accede al formulario con todas las operaciones disponibles. Todo esto del launch experiment no lo expliques pq desde tu applet ya no aparece como te comenté en un mail. Haciendo clic en el icono que representa una gráfica, se accede a los datos del experimento y a las operaciones disponibles. Página 52 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 A partir de aquí es posible lanzar la graphical interface para poder visualizar los resultados vía Web. En la página siguiente se puede ver la gráfica geométrica donde se muestra el patrón interno calculado para dos genes, el 1 y el 2, y se puede observar que es posible seleccionar todas las posibles patterns de genes dentro del cuadrante haciendo clic fácilmente sobre el cuadrado que corresponde la coordenada deseada que une los genes. Se pueden observar también la dependencia entre expresiones de genes. Página 53 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 En la interface existe un botón, “Menu”, donde haciendo clic aparecen diferentes operaciones para poder realizar. Página 54 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Haciendo clic en Parametric Plots aparece un nuevo menú donde podemos ir realizando diferentes operaciones. En la primera opción, Variables, que aparece por defecto, el eje de las X’s representa la PCOP y el eje de la Y’s representa la expresión de los genes para ser comparada. Se puede observar la distribución de la muestra a lo largo de la PCOP. En la segunda opción, Density, podemos ver las fluctuaciones de los datos de dispersión a lo largo de la PCOP. Página 55 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Haciendo clic en Variance, se puede observar en la página anterior la gráfica resultante. Con la herramienta de clustering, se podrán identificar las muestras del microarraycondition que contribuyen a cada comportamiento específico de los genes. A continuación podemos ver el Menú con todas las operaciones posibles. Seleccionando una POP se seleccionan las muestras de ejemplo asociadas a ella. Las áreas coloreadas representan los hiperclusters asociados para ese punto de vista. Página 56 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Se puede apreciar como cada punto de la gráfica tiene un color diferente. Y también que diferentes grupos de puntos comparten un color. Estos son los clusters los cuales, a través de la rejilla, se pueden ir seleccionando o no. Además se pueden realizar otras operaciones como la creación de clusters manualmente mediante el botón New Manual Clustering, Por último, es posible visualizar los datos asociados a los clusters que después pueden descargarse en 3 ficheros diferentes. Estos ficheros se pueden descargar haciendo clic en el botón Download, Estos 3 ficheros son: La lista de los clusters que es visualizan en ese momento por la pantalla con la paleta de colores asociada. La lista de todas las muestras que aparecen en la selección de los clusters y sus coordenadas relacionadas. La lista de los nombres de cada muestra que aparecen en la selección de los clusters. Estos ficheros se guardan en el directorio habilitado para el microarray, y se guardan enlaces en la base de datos para poder acceder a ellos si se desea consultar el análisis, o se pretende realizar el mismo análisis de nuevo. Estos clusters que se pueden definir constituirán la nueva paleta de colores de condiciones para las muestras. Esto nos sirve para estudiar las relaciones no continuas entre genes observando la distribución de las clases de muestras definidas en otras relaciones de genes El tamaño de estos clusters y su solapamiento depende de los parámetros usados para calcular las POPs en el calculo de las PCOPs. Página 57 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 A partir de esta operación de definición de la class-palette es posible actualizar la sample-conditions class. El usuario tiene dos alternativas: subir un fichero que contenga la distribución de grupos de muestras hechas(Figura 4.34-1), por ejemplo mediante un sample clustering realizado anteriormente sobre la PCOP de una relación entre genes, o crear el mismo, dichos grupos usando la web (Figura 4.34-2). Fig. Proceso de selección de muestras para una plantilla en el gestor de experimentos En el primer caso, el usuario deberá aportar un fichero que tenga la las muestras distribuidas por grupos. Estas muestras son excluyentes entre sí, es decir, si una muestra se encuentra en el grupo 1, no podrá encontrarse en ningún otro. La aplicación mantendrá un control sobre la verificación de las muestras a ser pintadas para evitar inconsistencias, como colorear una muestra que no existe en la microarray. En el segundo caso, podrá ir escogiendo de la lista de nombres de todas las muestras( las condiciones experimentales de la microarray), aquellas que le interesen, e ir formando los diferentes grupos o clases. Finalmente te, el usuario le dará un nombre a la plantilla que acaba de crear y quedará asociada a la microarray, además podrá descargarse esa misma plantilla en su ordenador. El diseño de la segunda opción está basado en las mismas tablas de selección que hay en la aplicación, de este modo, el usuario sin haber creado nunca ninguna plantilla, sabrá como debe emplearse la lista de nombres que tendrá delante. El resultado en la graphical interface seria el siguiente, muestras agrupadas por diferentes colores: Página 58 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Fig.4.35 Gráfica de un experimento con una plantilla de colores asociada La aplicación llevará un control sobre aquellos ficheros de colores que dependan del de la microarray, es decir los análisis ya hechos y almacenados en las diferentes views, ya que en el momento que la plantilla de colores de la microarray varíe, también lo deberán de hacer las que dependen de ella. De este modo, evitamos tener plantillas obsoletas que aporten información errónea al usuario. La última operación posible en esta aplicación creada para el IBB es la classdiscrimination gene search la cual lanza un cgi donde un programa c++ busca los genes que se expresan de lamanera predefinida por el usuario, y devuelve esos resultados. A partir de la actualización de la sample-class palette es posible realizar dicha búsqueda sobre estas clases. Es posible encontrar relaciones no continuas bajo un criterio específico (relacionando un conjunto inicial de genes para generar la classpalette con los genes encontrados en la búsqueda). Los genes mas correlacionados con los previos son también encontrados. Las dos figuras de la siguiente página realizan una búsqueda sobre los 4 genes en los que se basan todos los ejemplos. Página 59 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Pantalla para definir la búsqueda Pantalla resultado Esta pantalla resultado es importante ya que será la que devolverá los resultados a la Herramienta Vía Web y está deberá de mostrar estos genes encontrados señalándolos para su análisis.4 – 2 Estructura de la Interfaz Gráfica Vía Web 4 – 2 – 1 Herramienta actual Tal y como ya se ha comentado en el primer capítulo, este proyecto continúa con la herramienta Web básica que estaba en funcionamiento, con lo cual la base de datos ya tenía una estructura definida. Página 60 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 A partir del estudio de las necesidades que iba a tener la aplicación, la base de datos fue modificada para albergar tantos los cambios en las tablas existentes como las nuevas tablas para las diversas funcionalidades nuevas de la aplicación. El objetivo final era conseguir distribuir la información de todas las gestiones que se realizan, de una manera eficiente, fácilmente accesible, y en el caso que fuese preciso, fácilmente eliminables. Un ejemplo sería la rápida identificación de contenido de las tablas. Para realizar el diseño de la base de datos, se ha utilizado una versión gratuita del programa DB Designer4. Este programa es un sistema de diseño visual de base de datos que integra el diseño, modelado, creación y mantenimiento de la base de datos. Permite hacer ingeniería inversa de un modelo de base de datos existente, o en su defecto, la creación de tablas, especificando los campos y sus tipos, creación automática de claves e indica las interrelaciones entre ellas. Este programa además está desarrollado y optimizado para las bases de datos MYSQL, sistema que es el utilizado por la aplicación aquí desarrollada. A través de un modelo de la BD, se mostrarán las relaciones que hay entre las diferentes tablas, y la jerarquía existente entre ellas. Rel_02 Rel_01 Rel_06 Rel_05 Rel_03 Rel_04 Rel_07 Rel_08 Rel_09 Descripción de la base de datos Página 61 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Existen algunas tablas que son secundarias y que no están relacionadas con la aplicación directamente como por ejemplo, Sections, Sources y Downloads. Las tablas Sections y Sources están vinculadas entre ellas mediante una relación de 1-n, mientras que las tablas Sources y Downloads están vinculadas mediante una relación de 1-n. La tabla Sections se ocupa de guardar los diferentes tipos de secciones que tiene la página web y Sources, los diferentes tipos de elementos que contienen cada una de las anteriores. La tabla Downloads mantiene una lista de las descargas que se realizan en alguna de las subsecciones y del momento en las que fueron realizadas. Las principales tablas que aparecen en el modelo son Applicants, Experiments, View, Microarrays, Genes y Personalize_texp. Veamos con detenimiento, en que consiste cada una de ellas: Applicants y Experiments: la primera tabla se encargará de guardar la lista de usuarios, con todos sus datos, que utilizarán la aplicación. Esta tabla está vinculada con Experiments, que se ocupará de almacenar todos los datos de los experimentos que realice cualquier usuario, mediante una relación 1-n ya que un usuario puede tener n experimentos, pero un experimento solo puede pertenecer a un determinado usuario. Personalize_texp: se ocupa de guardar las preferencias de variables que tiene cada usuario a la hora de visualizar las tablas de experimentos en la aplicación, con lo cual está vinculada con la tabla Applicants con una relación de n-1, ya que una preferencia solo puede pertenecer a un usuario, pero en el caso contrario, un usuario puede tener n preferencias. Cabe decir que las preferencias que escoja un usuario, tan solo serán válidas durante la sesión de trabajo en las que fueron escogidas; en el instante que inicie una nueva sesión, el usuario verá en las tablas de experimentos, los campos por defecto, pudiendo modificarlos en cualquier momento. View: se ocupa de guardar las vistas creadas por el usuario, tanto para la gestión de experimentos como para la gestión de microarrays. Está vinculada a la tabla Applicants con una relación de n-1, puesto que cada vista solo puede pertenecer a un único usuario, y éste en cambio, puede tener n vistas. La tabla View también está vinculada con la tabla Microarrays en relación n-1, ya que del mismo modo, una vista solo puede pertenecer a una de las microarrays, y ésta por el contrario, puede tener n vistas. Microarrays: esta tabla se encargará de almacenar todas las microarrays que hayan sido dadas de alta por cualquier usuario. Está vinculada con la tabla de Applicants en relación n-1, ya que un usuario puede dar de alta a n microarrays, pero una microarray tan solo puede haber sido dada de alta por un usuario. Genes: se ocupa de guardar de todos los genes de las microarrays que estén dadas de alta. Está vinculada con la tabla de Applicants en relación n-1, puesto que un usuario puede acceder a n genes, pero un gen solo puede haber sido dado de alta por un usuario; también está vinculada con la tabla Microarrays en relación n-1, ya que un gen solo pertenece a una microarray, pero ésta puede tener n genes. Para identificar en la tabla de View, aquellas vistas que no correspondan a ninguna microarray en concreto, es decir, que pertenezcan a la gestión de experimentos, serán identificadas con el número 0, ya que como el índice de la tabla Microarrays es Página 62 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 automático, el primer índice será siempre 1, con lo cual no habrá incongruencias en el sistema. Cada microarray tendrá asociada una tabla Experiments específica, y será en dicha tabla donde se guardarán los datos y resultados de los experimentos realizados a partir de los datos de dicha microarray. Así, si en el futuro se quiere implementar una gestión, modificación o eliminación de microarrays diferente a la actual, la modularidad de la base de datos permitirá un acceso y una programación fácilmente realizable. Cabe añadir también, que dicha modularidad, hace que el trasvase de información para los futuros tratamientos de datos sea rápido y seguro. El diseño de la tabla de Genes ha sido pensado para que en el futuro, puedan añadirse unas funcionalidades concretas, como la modificación de los nombres de los genes según una plantilla específica, puesto que la mayoría de las veces, los genes no tienen un nombre específico sino un nombre alfa-numérico asignado temporalmente hasta la definición definitiva de uno. Página 63 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Creación de una microarray No es creación de una microarray sino upload de los datos de una micrarray. La creación de una microarray parte de la página de inicio, como puede comprobarse en la Figura 4.18. A través del botón “New microarray”, nos dirigiremos a la pantalla de introducción de los datos que identificarán a la microarray. El diseño de esta pantalla es similar al de la creación de un experimento, de esta forma, el usuario puede identificar y asociar operaciones de una manera más sencilla. El proceso es igual de simple: se indican los datos, y los ficheros de entrada. Veamos como deben ser los ficheros de datos: Fichero de muestras: matriz de datos numéricos. Las filas representan a los genes, y las columnas a las sustancias (experimentos) a las que se ha sometido a pruebas los genes. Fichero de genes: fichero con los nombres de los genes de la microarray Fichero de nombres de experimentos de la matriz: fichero con los nombres de los experimentos de la microarray. Los ficheros deben concordar en número, es decir, el número de filas de fichero de muestras debe ser igual al número de nombres de genes, y del mismo modo, el número de columnas del fichero de muestras, debe ser igual al número de nombres de experimentos. Si no es así, la microarray no será aceptada por la aplicación. Página 64 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Nombres de experimentos Nombres de genes Datos Debido a que las microarrays son matrices con un elevado número de datos, se optó por permitir al usuario que pudiera subir una microarray por partes. Primero habría de proporcionar unos ficheros que fuesen la base del resto de partes, y después especificar que partes subiría a continuación. Habría dos formas posibles: 1. El usuario añade más sustancias a la microarray: fichero de muestras y de sustancias. Datos originales Datos añadidos 2. El usuario añade más genes a la microarray: fichero de muestras y de genes. Datos originales Datos añadidos En ambas posibilidades se verificará que las dimensiones de la nueva microarray sigue siendo la correcta, y que los ficheros subidos tienen el formato adecuado. El usuario podrá visualizar en todo momento ( véase la Fig. 4.24 ) que tipos de ficheros ha subido junto con los de muestras: de genes o de sustancias. Una vez finalice el usuario de aportar ficheros, la matriz, si no hay ningún error, será dada de alta. En caso de que si que hubiese algún error, la aplicación informará al usuario de éste, para que pueda solventarlo. Página 65 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Fig.4.24 Pantalla de archivos parciales para la microarray Para evitar que existan ficheros de datos repetidos en el sistema, si un usuario quiere dar de alta una microarray que ya existe en el sistema, se desecharán los ficheros subidos por el usuario, y a cambio, el usuario tendrá permisos totales para acceder a la microarray y a toda la lista de genes, de igual modo como si la hubiese dado de alta el mismo. Sistema de Directorios Los directorios donde están almacenados todos los archivos que han sido, y son, utilizados por la aplicación, ya sea como archivos temporales o como resultado de las operaciones que se pueden realizar en ésta, se encuentran fuera del directorio público donde se encuentran todos los archivos que conforman la aplicación. La razón para dicha separación, se encuentra en evitar que dichos archivos puedan ser copiados por alguien ajeno a la aplicación, puesto que la implementación de la seguridad de usuarios no ha sido realizada en este proyecto, y cualquier persona desde un navegador podría acceder a los archivos mediante un http a la carpeta que contuviese dichos archivos. Para evitar lo descrito anteriormente, hasta que la seguridad en la aplicación sea implementada, si en el navegador no se introduce una dirección correcta, aparece una página web de error. El path donde se pueden encontrar, actualmente, todos los archivos de datos de la aplicación es /home/revresearch/cgi-bin/pcop. El directorio pcop se ramifica en otros directorios, los cuales corresponden a determinadas gestiones de la aplicación. Mostramos a continuación una figura del sistema de directorios: Página 66 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Figura 4.37 Sistema de directorios Descripción del sistema de directorios No expliques solo los directorios y ficheros que hay hasta ahora, añade todos los ficheros y archivos que tu has añadido y donde se guardan. Tal y como puede verse en la Figura 4.37 el directorio /pcop está formado por directorios y por archivos. Los archivos contenidos son de dos tipos: ejecutables, necesarios para la creación de experimentos tanto para el gestor de experimentos en Pattern como para el gestor de experimentos para Microarrays; y temporales, los cuales son utilizados para ejecutar las operaciones de la aplicación, y para introducir, secuencialmente, más datos al archivo. El tiempo de vida de los archivos temporales finaliza en el momento en que la operación que ha generado dicho archivo acaba. A continuación, pasaremos a describir la función de los directorios de /pcop: Compile: directorio donde se guardan y crean versiones diferentes del ejecutable utilizado para la aplicación. Pattern: este directorio está formado por un directorio y por conjuntos de archivos, identificables por el número de experimento al que representan. Un experimento, puede tener los siguientes archivos: o Num_experimento.input : archivo de entrada de datos proporcionado por el usuario. Consta de una matriz de datos numéricos. o Num_ experimento.snames: archivo de entrada de nombres de sustancias proporcionado por el usuario. Es opcional. o Num_experimento.ouput : archivo de salida generado por el programa o Num_experimento.var : archivo de salida generado por el programa o Num_experimento.cluster: archivo de salida generado por el programa Página 67 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 o Num_experimento.colors: archivo de entrada proporcionado por el usuario. Este archivo es la plantilla de colores correspondiente al experimento. Para que exista un experimento debe de haber siempre un archivo con la extensión .input . El experimento será considerado como válido si el programa de ejecución genera los archivos con las extensiones .output y .var , en caso contrario, es considerado fallido. El archivo con extensión .snames es opcional. Las extensiones .cluster y .colors , representan a los archivos que serán utilizados para sus respectivas aplicaciones.El directorio /classification almacenará los archivos temporales que serán utilizados para la aplicación Classification. En cada nueva operación de dicha aplicación, el contenido del directorio es eliminado. Microarray: este directorio está formado por varios directorios y por un archivo que contiene la correspondencia entre los nombres de las microarrays y sus identificadores. El directorio /classification almacenará los archivos temporales que serán utilizados para la aplicación Classification. En cada nueva operación de dicha aplicación, el contenido del directorio es eliminado. Por cada microarray que haya sido dada de alta por un usuario, existirá una carpeta, que de igual forma que en /pattern, albergará conjuntos de archivos que representarán a los experimentos realizados sobre los datos de la microarray. El nombre de un archivo estará compuesto por la posición de los genes seleccionados para la creación del experimento, junto con los valores de aquellos parámetros que no sean los de defecto. A parte de esos conjuntos de archivos, en cada carpeta habrá los tres archivos que representan a la microarray: Num_microarray.samples: archivo de datos Num_microarray.genes: archivo de nombres de genes Num_microarray.snames: archivo de nombres de sustancias 4 – 2 – 2 Preproceso Para poder trabajar con las muestras generadas de un microarray, se necesita un preproceso que nos genere, a partir de ellas, los ficheros necesarios para poder trabajar con la Interfaz Gráfica Vía Web, y que son aptos para poder trabajar con el framework JUNG. Este paso no es directo ya que se deben realizar operaciones a partir de estas muestras como el Layout de los genes en el espacio 2D (tal como se comenta en el algoritmo detallado del apartado 1), el cálculo del Minimum Spanning Tree y el cálculo de los cluster-color-values para cada uno de los genes. Tienes que haber explicado en el preproceso, que se lanza cuando se sube la microarray, de donde salen los ficheros factors.txt, names.txt y clusters.txt . Tienes que hacer más referencias a las secciones anteriores donde explicas parte de las cosas. Página 68 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 En el apartado anterior hemos visto como se generan los tres ficheros de datos con los cuales poder realizar el preproceso. Parar realizarlo usaremos un esquema como el que mostramos a continuación: Clusters.txt Factors.txt Names.txt Grafoclusters.cpp C++ BioFactors.net C Txt File Pajek File Mst.c BioMST.net Interfaz JUNG Los ficheros de entrada del preproceso se generan cuando un usuario sube un microarray al preproceso. Aquí se calculan la correlación de todos con todos para obtener la tabla de correlaciones por un lado, Factors.txt y luego, a partir de esta, se generan los ficheros de correlación de cada gen con los demás, para utilizarlos en la llamadas a las aplicaciones externas “correlations table”, “correlations” y “gene info” que comentaremos posteriormente. Este fichero tiene el formato siguiente en cada línea: idGen-i idGen-j weight(ij) El id de cada gen es 1-based y la weight es el peso de la arista del grafo, la correlación. Los otros dos ficheros también se generan en la subida del microarray. Con éstos y el comentado anteriormente, generamos dos programas que nos sirven para generar los ficheros que se ven en el esquema. Pasamos a detallar los dos programas usados. Grafoclusters.cpp Este programa genera el fichero BioFACTORS.net en el formato específico de JUNG y realiza para ellos las siguientes operaciones: El cálculo del Layout, tal como se comenta detalladamente en el apartado 1, para la ubicación de los genes en el espacio 2D según su grado de correlación mutua. A partir del fichero de Clusters y del fichero BioMST.net, se calcula el cluster-color-value para cada uno de los genes. Para calcular este valor lo Página 69 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 que se hace es calcular el valor medio para ese gen sumando las aristas que pertenecen al MST y que forman parte de ese cluster y se divide por el número de genes del cluster. Lógicamente, para cada gen que pertenece al cluster, el valor asignado es el mismo. Este valor servirá, posteriormente, para calcular el color con el que se debe de pintar el cluster en la Interface Vía Web. La generación propia del fichero BioFACTORS.net de salida apto para JUNG, recogiendo los valores de las coordenadas, calculadas en el Layout, las etiquetas de cada gen, proporcionadas por el fichero Names.txt, y el valor calculado del cluster-color-value. El formato del fichero es una extensión del formato PAJEK, usado para guardar información de grafos. Así, éste es el formato: *vertices n 1 “nombre-1” coord-X1 coord-Y1 color-cluster-value-1 … n “nombre-n” coord-Xn coord-Yn color-cluster-value-n *edges i j weight(ij) n es el número total de vértices del grafo y weight es el peso de la arista desde i a j, equivalentemente, la correlación entre los genes i y j. Las aristas incluidas en el preproceso no son todas las recogidas en el fichero de factors de la microarray. Si fuesen todas tendríamos un largegraph de n * (n-1) aristas y este volumen de información provocaría un rendimiento pobre en la Interface Vía Web. Así, después de analizar diversos valores para este número de aristas, se optó por guardar 2K5 aristas del microarray original. Éstas son las aristas que mejor correlación tienen, ya que son las más importantes para los estudios posteriores que se desean realizar. Mst.c Este programa genera el fichero BioMST.net. Calcula el Minimum Spanning Tree (MST) con las correlaciones de entrada del fichero Factors.txt. El algoritmo utilizado para este objetivo es el Algoritmo de Prim. Esto genera n – 1 aristas, el camino mínimo dentro del grafo que representa el microarray, y donde n es el número de genes, y lo guarda en el siguiente formato: ij weight(ij) Se optó por guardar las aristas resultantes del MST en un fichero diferente al principal debido a que, para la generación de éste principal, es necesario tener calculado previamente el MST para el cálculo posterior del clusters-color-value. Aunque después se podrían haber añadido las aristas del MST que no aparecieran en el filtro principal, se optó por tener en un fichero separado, ya que en la Interface Vía Web es mucho más flexible ya que se tratan estas aristas de una manera diferente para cargarlas en el grafo principal, se le añaden user- Página 70 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 data que las aristas del filtro no necesitan y que permiten una visualización diferente de la aristas que forman parte del MST. Así, y una vez generados los dos ficheros para poder trabajar con la Interface Vía Web, pasamos a describir como se ha implementado ésta. 4 – 2 – 2 Herramienta Interactiva Vía Web Como se ha comentado anteriormente, la Interactive Tool Vía Web está implementada en Tecnología Java ayudada por el framework JUNG. El Diagrama de casos de uso de la Interactive Tool, nos muestra la operatibilidad deseada de ésta (página X). El objetivo de la herramienta es el de poder, interactivamente, realizar operaciones sobre el grafo que representa un conjunto de genes de la microarray de entrada que lanza el usuario. La Web interface está dividida en dos partes bien diferenciadas: la primera es la ventana de visualización, donde se muestra el grafo; la segunda, el frame de operaciones, en la parte derecha, donde están todas las operaciones disponibles del usuario a modo de “Cuadro de Mandos”. En la página siguiente se puede ver una imagen de la Herramienta Web. El objetivo o idea principal es que, a medida que el usuario vaya realizando las operaciones, estas generen unos resultados que se puedan apreciar de forma visual en el grafo. En ocasiones, estas operaciones destacarán nodos en el grafo (genes) o aristas del grafo (la representación de las correlaciones entre los genes). Pero lo más importante de todo esto, es generar un conjunto de nodos seleccionados a partir de estas operaciones. Así, al final éstos nos servirían para poder compararlos, buscar información relevante sobre ellos, comparar con otros Microarrays y todo ello a través del lanzamiento de unas operaciones Página 71 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 externas. Página 72 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Página 73 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Detallaremos a partir de ahora como se comporta funcionalmente la Herramienta y mostraremos las operaciones que son posibles realizar con ella. Después detallaremos con más profundidad todos los packages creados para conseguir el objetivo, y el porqué de esta solución adoptada. Descripción Funcional Como hemos comentado, el objetivo final es conseguir un conjunto de nodos (genes) seleccionados, después de realizar una serie de operaciones sobre el grafo, que nos permitan lanzar las aplicaciones externas para poder visualizar detalles relevantes sobre ellos. Un conjunto de genes seleccionados se visualizan en la aplicación como se ve en la figura siguiente: Se puede apreciar como hay genes seleccionados con una shape tipo estrella, otros que están en color naranja, que pueden ser el resultado de una operación como el “mspath”, y otros de color amarillo que son genes seleccionados explícitamente por el usuario. Este conjunto de genes pueden ser lanzados a una aplicación externa perfectamente y también pueden ser deseleccionados para poder hacer otra búsqueda nueva, haciendo clic en cualquier parte del grafo con el Panel de Operaciones en “Mode Picking”, o es posible añadir manualmente alguno más pulsando la tecla Shift, y sin soltarla hacer clic sobre uno de los genes no seleccionados. De la misma manera se puede deseleccionar un gen de los que están seleccionados. Sabido el objetivo final, nos vamos a centrar en las operaciones, dividiendo éstas en bloques según su ubicación en el Panel de Operaciones. Bloque zoom-in: Página 74 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 mspath: Calcula el Shortest Path entre un grupo de genes seleccionados. Los genes seleccionados para la búsqueda del mspath son presentados en forma de Estrella de color naranja, y los nodos que forman parte del camino son presentados en color naranja suave. Se puede apreciar como el camino se pinta de color azul, los nodos se presentan con la inicial del gen y como las correlaciones son mostradas encima de las aristas. Página 75 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Dependence análisis: Realiza el cálculo del patrón que define la dependencia en la expresión de los genes seleccionados. Es decir, el patrón de su relación para las muestras de la microarray cargada. Lanza la operación externa y se muestra la pantalla siguiente: Correlations table: Lanza la tabla de correlaciones entre todos los genes de la microarray. Página 76 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Search: Realiza una búsqueda a partir del literal introducido en la Input Box. Si el Literal, exacto, forma parte de la Label del gen, este gen pasará a ser seleccionado. A continuación se muestran los genes encontrados, se resaltan con el Shape estrella naranja, en la búsqueda realizada para el literal Cytochrome. Página 77 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Bloque Gen info: Correlations: Lanza una consulta sobre el gen seleccionado y devuelve los genes más correlacionados con éste. Si hay más de un gen seleccionado lanza una pantalla por gen. En la página siguiente se puede observar la pantalla para uno de los genes encontrados en la operación descrita anteriormente. Página 78 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Gene: Lanza la información de la base de datos del NCBI(Nacional Center for Biotechnology Information). Si hay más de un gen seleccionado lanza una pantalla para cada gen. La imagen siguiente muestra la información recogida en el NCBI para un gen encontrado en la operación “Search”: Significative Geo Profiles: Lanza una consulta a la base de datos de microarray datasets dek NCBI, devolviendo las Microarrays con las que el gen seleccionado de contrastes relevantes para las muestras de esas Microarrays. La pantalla siguiente muestra para el gen anterior la pantalla comentada: Página 79 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Update Samples-Class Palete: Lanza un applet para cambiar la paleta de colores asociada a la microarray. Es decir, agrupa los diferentes samples de la microarray en colores de forma que se puedan distinguir dichos grupos cuando se visualizan las dependencias entre genes. Class –Distribution Gene Search: Lanza una búsqueda de los genes que se expresan de determinada forma para los grupos definidos para la Samples-Class Palette. Bloque Custom Operations: Zoom: Realiza un zoom sobre la ventana de visualización del grafo. Si el mouse dispone de rueda, la manipulación de esta también aplica un zoom sobre la ventana de visualización. Mode: Permite especificar el modo en el que el mouse actúa sobre el grafo. Tiene dos opciones: 1. Transforming: Mueve y arrastra el grafo en su totalidad a través de la ventana de visualización. 2. Picking: Sirve para seleccionar elementos del grafo, tanto nodos como aristas. Si se hace clic sobre la tecla Shift , y sin soltar ésta, la operación es acumulativa. Filter Correlations: Control que es un Java.Swing.JSlider que permite aplicar un filtro de correlaciones sobre el grafo permitiendo visualizarse sólo las aristas que tengan un valor menor o igual al escogido con el control. En la figura siguiente se puede observar la aplicación del filtro en el grafo realizando un zoom en una región de éste. Show Ops: Este bloque de operaciones sirve para visualizar en detalle elementos y entidades del grafo. Son: 1. Correlations: Muestra en cada arista el valor de dicha correlación. En la figura anterior se puede observar un ejemplo de esta operación conjuntamente con la de filtro. Página 80 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 2. Gene Names: Muestra las etiquetas de los genes. Aprovechando el ejemplo anterior y haciendo clic sobre Gene Names tenemos la siguiente pantalla de salida: 3. Show mstree: Muestra el minimum spanning tree asociado al grafo y calculado en el preproceso. 4. Paint: Bloque que sirve para pintar las aristas o los nodos de una manera predeterminada y que sirve para hallar información relevante en el grafo. Son dos operaciones de coloración del grafo: Correlations: Asigna un nivel de gris a cada arista equivalente a el valor de correlación que esta posee. La pantalla siguiente muestra cual es el resultado de pintar las correlaciones sobre el grafo filtrado y con la operación mstree realizada. Se aprecia en el zoom de la región del grafo como existen aristas con un color gris más tenue y otras con un gris más acentuado. Página 81 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Clusters: Asigna un color a cada nodo, calculando este color mediante algoritmos que detallaremos más adelante, y que dependen del color-cluster-value calculado en el preproceso. En la pantalla siguiente se pude apreciar como se detectan clusters de nodos con una dependencia entre si muy evidente. Hasta aquí hemos comentado a grandes rasgos que puede y que se espera de esta Herramienta Web. La manera de implementar todas estas operaciones se detallan a continuación mediante la explicación de los packages desarrollados en Java para la consecución del proyecto. En las descripción de las operaciones anteriores han de haber continuas referencias, a las secciones de la intro y similares donde se explican los métodos y tecnicas utilizadas. Lo que puedes hacer es si eliminas el punto 4.1, insertar la información válida de allí, en el punto donde explicas que esas operaciones son lanzadas. Porque ahora están muy mal explicadas allá. Explicalas más brebementes, y las que ya están bien explicadas en la intro, no las vuelvas a explicar(como el pattern análisis y el clustering). Quizás la única Página 82 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 que no este explicada anteriormente o posteriormente a esa sección sea la del class distribution gene search, que le puedes dedicar una sección para ella antes de explicar la interfaz web propiamente dicha, igual que la explicación de cómo se suben las palettas de colores que te pasé, a la que le deberías dedicar tb una sección antes de explicar la interfaz propiamente dicha. Sobretodo en esta sección de upload palette haz referencia a las secciones de clusters de samples desde la interfaz gráfica, porque sino no se entenderá de donde vienen estas clases (vienen de haberse realizado clusters de simples usando las PCOP calculadas). Si quieres tb hazle una sección a la interfaz flash, recuperando lo que escrivistes del tema en la sección eliminada, y otra sección que si deberás crear es para la tabla de correlaciones y las listas de genes más correlacionados (con lo que más que eliminada necesitada de una reorganización, y sí, de la eliminación de electos repetidos como la subida de una nueva microarray). Descripción del Desarrollo En el Apartado 3 se hizo una descripción del framework JUNG usado para la consecución de este proyecto, analizando las posibilidades que nos brinda éste y haciendo un recorrido rápido sobre las clases más importantes que lo conforma. Además, vimos la flexibilidad y rapidez con la que era posible desarrollar aplicaciones y herramientas útiles que al final nos permitieran el objetivo final de este proyecto. En sí, el desarrollo de nuevas clases no ha sido extenso, ya que JUNG proporciona toda la abstracción necesaria para la creación y manipulación de grafos, dejando que el programador sólo se tenga que centrar en lo que tiene que obtener, y en no cómo ha de implementarlo para conseguirlo: no ha de preocuparse de la topología de grafos. Sólo ha de centrarse en detalle en las operaciones necesarias para cumplir los objetivos funcionales, de ahí que se decidiera este framework como el ideal para el desarrollo de ésta Herramienta Web. Cómo se comenta anteriormente, la Herramienta es una herramienta Web, con un claro objetivo: disponibilidad absoluta desde cualquier ubicación ya que la idea es poder albergarla en un server desde el cual pueda ser ejecutada interactivamente desde cualquier ordenador personal conectado a Internet. Para ello, se crea un Applet, tecnología Java, que nos permite la ejecución en cualquier SO mediante la creación de un componente para que nuestra aplicación pueda ejecutarse en el contexto de un navegador Web. La website contenedora del Applet, BioProject.html, es la lanzadora de esta Herramienta. Invocará la clase de entrada que será BioProject.class y será la clase que se deberá especificar en el parámetro <code> de la definición de Applet dentro del código html de la página. El Applet necesita unos parámetros por defecto que nos señalan las características de la microarray cargada. Por tanto estos parámetros llegan con la URL de entrada a través de GET. El literal con todos los parámetros que se deben de pasar a la clase de entrada del Applet se genera mediante Javascript parseando la URL de entrada para poder asignar ese literal al único parámetro que posee el Applet. Una vez hecha esta introducción, pasamos a comentar los packages creados en el aplicativo: es.com.uab.ibb.bioproject Página 83 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Contiene la clase Applet que lanza la aplicación y la clase contenedora que genera el JPanel para visualizar la Interactive Tool. BioProject: Clase extends de la clase JApplet. El método más importante de esta clase es startFunction() el cual lee el grafo mediante la clase IBBPajekNetReader y genera un objeto contenedor BioProjectPanel para poder visualizar la Web Tool. El objeto comentado es un objeto Java.Swing.Component.JPanel y éste se encarga de toda la gestión implícita de la visualización y carga de la interface. BioProjectPanel: El componente sobre el cual construiremos la Web tool. Como hemos comentado antes, extends de la clase Swing JPanel, y que implementa la interfaz ActionListener para así poder recoger todos los eventos generados por lo controles incluidos en él. Se opta por la implementación ya que el objeto puede encapsular todos los eventos en el método heredado solamente mirando el control que genera dicho evento. Los métodos más significativos son los siguientes: BioProjectPanel(…): El propio constructor de la clase. Recibe los siguientes parámetros: o Objeto Graph que es el grafo leído del preproceso. o Objeto AppletContext con el contexto del Applet, que nos permitirá lanzar las Aplicaciones Externas a través del método showDocument(). o Objeto String en el que vienen los parámetros del Applet. Se debe de parsear para poder recoger los 3 parámetros importantes del aplicativo, el applicantID, el id_matrix y el name_matrix. o Objeto Set con el conjunto de aristas que forman el MST. o Objeto double con el máximo valor de correlación encontrado de las aristas del grafo filtrado en el preproceso. o Objeto double con el máximo valor de correlación encontrado de las aristas del MST calculado en el preproceso. o Objeto double con el máximo valor de color-cluster-value encontrado de los nodos del grafo filtrado en el preproceso. Podemos observar estos valores máximos, cotas, máximas, que nos sirven para realizar las operaciones descritas en el apartado anterior “Paint Clusters” y “Correlations” El constructor inicializa todos los atributos de la clase con estos valores y llama a dos métodos para iniciar la aplicación, getGraph() e initialize(). getGraph(): Devuelve el grafo filtrado por el valor de correlación 0. Por tanto sin aristas. Esto lo realiza mediante una llamada al objeto EdgeCorrelationsFilter que explicaremos posteriormente. El atributo de la clase mCurrentGraph guarda una instancia del Página 84 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 grafo filtrado. Señalar que el atributo mFactorsGraph es el que guarda en todo momento el grafo original completo calculado en el preproceso y que sobre él se van realizando las operaciones para generar un grafo resultado que siempre recaerá sobre mCurrentGraph. La motivación de esto es el poder tener siempre el mínimo grafo necesario en el viewer y para ello es necesario guardar el grafo original en un objeto y el visualizado en ese momento en otro. Una vez generado el grafo se recogen del original los UserDatum con las coordenadas del Layout de los nodos y se genera éste invocando al objeto BioProjectLayout() al cual se le pasa el grafo por parámetro. Para inicializar el Layout sólo queda entonces llamar al método del nuevo objeto initialize. initialize(): Es quizás el método más importante, ya que es el encargado de hacer el “on”, o puesta en marcha, de la Web tool. Para entender bien este método la mejor explicación es la de la figura xxx. JUNG, ya hemos comentado, tiene un clase contenedora extends de JPanel de Java Swing. Esta es VisualizationViewer, que recibirá un layout, en nuestro caso el que generamos con nuestra clase específica para ello, y un PlugabbleRenderer, clase donde se especifican todas las particularidades de los objetos y métodos que controlarán y pintarán el grafo, y sus componentes, según la operación en curso. A partir de los métodos propios del PlugabbleRenderer es posible especificar los objetos encargados de las tareas específicas para pintar aristas y nodos. Por ejemplo, y asumiendo que pr es el objeto renderer, y dependiendo de la operación en curso: o pr.setVertexPaintFunction(vcf): Establece en el renderer el objeto vcf, clase es.com.uab.ibb.bioproject.visualization.MyVertexPaintFunction, que gestiona con que color pintar el vértice. o pr.setVertexShapeFunction(vssa): Establece en el renderer el objeto vssa, clase es.com.uab.ibb.bioproject.visualization.MyVertexShapeSizeAspectFunction, que gestiona que size tendrá el vértice. o pr.setEdgePaintFunction(mepf): Establece en el renderer el objeto mepf, clase es.com.uab.ibb.bioproject.visualization.MyEdgePaintFunction, que gestiona con que color pintar las aristas. o pr.setEdgeStrokeFunction(mesf): Establece en el renderer el objeto mesf, clase es.com.uab.ibb.bioproject.visualization.MyEdgeStrokeFunction, que gestiona el Stroke que adopta la arista. o pr.setEdgeShapeFunction(new EdgeShape.Line()): Establece en el renderer que la forma que han de tener las aristas es el de una línea recta. o pr.setEdgeStringer(es): Establece en el renderer el objeto es, clase es.com.uab.ibb.bioproject.decorators.MyEdgeStringer, que gestiona si se ha o no de mostrar la label de las aristas. Página 85 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 o pr.setEdgeFontFunction(fhFont); Establece en el renderer el tipo de fuente que se mostrará en el labelled de las aristas. o pr.setVertexFontFunction(fhFont): Igual que antes pero para los vértices. Vemos que esta inicialización es muy importante para después visualizar el grafo de la manera esperada según la operación realizada. Por último existe el contenedor con la gestión de zoom sobre el viewer el cual se inicializa con la siguiente clase: GraphZoomScrollPane a la cual le pasamos el viewer y el cual será añadido como scrollPane a la clase BioProjectPanel, y una clase que gestiona los eventos de mouse, la clase DefaultModalGraphMouse. es.com.uab.ibb.bioproject.components Contiene la clase BioPanel que genera un Jpanel que es el que le da el aspecto al frame de la derecha donde están todas las operaciones.Es una clase extends de la clase Swing de Java Jpanel. es.com.uab.ibb.bioproject.decorators Contiene todas las clases que usan los Labellers y los UserData que se hacen servir para guardar información relevante como las aristas del MST, el clustercolor-value, etc. Pasamos a describir brevemente las clases que componen este package. BioToolTipFunctions: Esta clase clase es un extends de la clase edu.uci.ics.jung.graph.decorators.DefaultToolTipFunction. Esta clase está diseñada para hacer un get de los valores, tanto de una arista como de un vértice, cuando se genera el evento onmouseover. La motivación de la extensión de la clase comentada es para visualizar las etiquetas de los genes cuando el mouse lo posicionamos encima. El constructor de la clase recibe una edu.uci.ics.jung.graph.decorators.EdgeWeightLabeller parámetro que contiene los valores de todos los pesos de las Edges del grafo. Los métodos de acceso de la clase son: ● public String getToolTipText(Vertex v): Devuelve el String asociada al Vertex v con el método getUserDatum(key) donde key es la key asociada al user data y que tiene por nombre jung.io.PajekNetReader.Label. ● public String gettoolTipText(Edge e): Devuelve el String del valor del peso de la Edge e invocando al método del objeto EdgeWeightLabeller edge_weight que se pasa al constructor de la clase, getNumber(e). ColorVertexValue: Interfaz para la definición de métodos que debe implementar la clase que genera el Labeller que nos sirve para acceder al cluster-color-value de cada nodo. Es el metadata que creamos nosotros para encapsular toda la información sobre el cluster-color-value de cada nodo que se calcula en el preproceso. De esta manera, cuando se invoca Página 86 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 el método que retorna el color con el cual se ha de pintar el gen (nodo) si está habilitada la operación “Clusters”, puede a través de este objeto recoger el valor correspondiente de dicho nodo. VertexColorLabeller: Implementa la Interfaz anterior. Esta clase devuelve los valores asociados al metadata referido al cluster-colorvalue que se almacena en la carga del grafo. El constructor recibe un objeto del tipo Graph y tiene dos atributos importantes: ● El primero, de tipo estático, que es el key para poder acceder al User Data, este es el Objeto COLOR_DEFAULT_KEY y tiene el valor ColorDefaultKey. ● El Segundo, un HashMap, VertexColorMap que sirve para almacenar las parejas (Vertex, Double) con el cluster-color-value comentado para cada Vertex. Con este hashmap, es directo el acceso al color del nodo, de ahí su uso en la implementación de la intrerfaz. Los métodos de acceso más relevantes de esta clase son: ● public double getColor(Vertex v): Devuelve el cluster-colorvalue asociado a v. ● public void setColor(Vertex v, double colorVertex): Añade al atributo VertexColorMap la pareja (v, colorVertex) si v existe en el grafo pasado al constructor, sino genera una excepción del tipo IllegalArgumentException. MSTEdgeValue: Interfaz para la definición de los métodos que debe implementar la clase que genera el Labeller que nos sirve para saber si una arista forma parte o no del MST. Se realiza esta interfaz para así poder dotar al grafo de la información necesaria para poder diferenciar que aristas forman parte del MST y cuales no. Con esta interfaz tenemos el metadata necesario para esa gestión cuando haya que pintar posteriormente con lo métodos adecuados, las aristas. EdgeInMSTLabeller: Esta clase es similar a la clase VertexColorLabeller. Es un Labeller como ella, y si aquella implementaba la Interfaz correspondiente, esta implementa MSTEdgeValue. Al igual que la clase comentada tiene dos atributos idénticos en importancia: ● La key INMST_DEFAULT_KEY y tiene el valor InMSTDefaultKey. ● El HashMap edgeToMST que sirve para almacenar las parejas (ArchetypeEdge, bolean) que nos señalan si la arista pertenece o no al MST. Como vimos anteriormente, el acceso al valor es directo y por tanto muy flexible a la hora de llamar a los métodos de paintde las aristas y decidir como se ha de pintar. Los métodos de acceso más relevantes son: ● public boolean isInMST(ArchetypeEdge e): Devuelve un boolean con la pertinencia o no de e al MST del grafo. Página 87 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 ● public void setInMST(ArchetypeEdge e, boolean isIn): Añade al atributo edgeToMST la pareja (e, isIn) si e existe en el grafo. Sino genera un IllegalArgumentException. FontHandler: Clase que implementa dos Interfaces, edu.uci.ics.jung.graph.decorators.VertexFontFunction y edu.uci.ics.jung.graph.decorators.-EdgeFontFunction. Estas interfaces definen como deben de accederse a la Font asignada a los Vertices y a las Edges y con la cual se presentará la label asociada al nombre del gen o al peso de la arista. Se define un atributo, Bold, que es un flag para establecer el tipo Bold a la fuente y diferentes atributos de tipo Java.Awt.Font que sirven para definir las diferentes fuentes que se usarán. Los métodos de acceso son: ● public void setBold(boolean bold): Establece el valor del atributo bold. ● public Font getFont(Vertex v): Devuelve la clase Font asignada a v. ● public Font getFont(Edge e): Devuelve la clase Font asignada a e. MyEdgeStringer: Esta clase, al igual que la siguiente que se comentará, gestiona la visualización de la etiqueta asociada al objeto implementando para ello al Interfaz que corresponda. En ésta el objeto es una Edge cualquiera del grafo por tanto la Interfaz es edu.uci.ics.jung.graph.decorators.EdgeStringer. Según el tipo de operación realizada en el grafo, en este objeto son “mspath” y “correlations”, el constructor de la clase costumiza una serie de flags y de atributos para decidir si a través del método implementado debe devolver o no la label de dicho objeto para ser pintada en el grafo. Se usan flags booleanas para saber el tipo de operación en curso, y permiten fácilmente decidir si se ha de mostrar o no la etiqueta. Estos dos atributos boolean que controlan dichas operaciones son bMST y bShortestPath. Además para poder recoger dicha label necesitamos el Labeller donde se almacenan dichos valores, este será el objeto EdgeWeightLabeller pasado al constructor. Por último, el objeto donde están el Set con las Edges que han de ser visualizada su etiqueta. El método más importante es getLabel(ArchetypeEdge e) que retorna el Label de e si se dan las condiciones adecuadas. MyVertexStringerFunction: Como la anterior, esta clase gestiona la visualización de la etiqueta asociada a un objeto Vertex cualquiera del grafo. La interfaz implementada por esta clase es edu.uci.ics.jung.graph.decorators.VertexStringer. Según el tipo de operación realizada en el grafo, en este objeto son “Search” y “mspath”, el constructor de la clase costumiza como en la clase anterior los atributos necesarios para decidir si a través del método Página 88 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 implementado debe devolver o no la label asociada del objeto ArchetypeVertex para ser pintada en el grafo. Los dos atributos boolean que controlan las operaciones son bSearch y bShortestPath. Se necesita también el Set de ArchetypeVertex con los vértices los cuales deben mostrarse su etiqueta. El método más importante es getLabel(ArchetypeVertex v) que retorna el Label de v si se dan las condiciones adecuadas accediendo al valor a traves del User Data correspondiente. es.com.uab.ibb.bioproject.filters Contiene las dos clases que gestionan el filtro aplicado al grafo en la operación “Filter Correlations”. LevelDoubleFilter:Clase que define la interfaz que debe de gestionar los valores aceptados por el filtro del grafo. Define los getters y setters de los valores mínimos y máximosdel filtro y un extends de la Interfaz edu.uci.ics.jung.graph.filters.Filter. En el framework de JUNG existe una interfaz similar pero es para tipos de valores int, por tanto, se tuvo que realizar dicha implementación con datos de tipo Double para adecuarla a los valores de correlación que recogen los experimentos. EdgeCorrealtionsFilter: Clase que implementa dos interfaces, edu.uci.ics.jung.graph.filters.EfficientFilter y la comentada anteriormente y que es una clase extends de la clase abstracta edu.uci.ics.jung.graph.filters.GeneralEdgeAcceptFilter que define un método que cualquier clase heredada debe implementar para gestionar el comportamiento del filtro con las Edges que analiza. El constructor recibe una serie de parámetros para gestionar el comportamiento del filtro ya que el filtro puede estar activo conjuntamente con la operación “Show mstree” y por tanto no debe filtrar las aristas del MST del grafo.Por ello tiene dos atributos, uno un flag boolean bMST que nos señala si la operación está activada o no, y un Set edgesMSTSet con todas las Edges que forman parte del MST del grafo. El método, comentado antes, que ha de implementar la clase para poder aplicar el filtro al grafo es public boolean acceptEdge(Edge e) y sirve para aceptar o no e según los valores que el usuario va escogiendo mediante el control Slider que existe en la Herramienta Web. es.com.uab.ibb.bioproject-io Este package contiene una única clase, IBBPajekNetReader que es muy similar a la clase que viene en el framework JUNG edu.uci.ics.jung.io.PajekNetReader y que lee un fichero del tipo PAJEK con la definición del grafo. Para este proyecto se ha realizado una copia de ésta pero con modificaciones para adecuarla a nuestro objetivo. Página 89 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 El original no lee más allá del id, la label y de las coordenadas Layout del nodo. En la implementación de la Herramienta existe un parámetro más, el clustercolor-value y para ello se ha modificado la clase para poder leerlo, y además se ha modificado también para leer el fichero del MST generado en el preproceso y no añadir las aristas de éste si existen en el fichero del grafo filtrado en el preproceso. Se le pasan además, diversos User Data para que a la hora de generar el grafo lo haga con las metadtas que se hacen servir en la Herramienta. La manera de generar el grafo ya está comentada en el pequeño tutorial de JUNG del apartado 3. es.com.uab.ibb.bioproject.resources Este package contiene dos clases de apoyo de la Web tool. Ctes: Clase que contiene todas los atributos que hace servir la Herramienta y que su carácter final y static las hace invariables. Desde las labels de los botones de control, las keys de las User Data usadas, como los textos de aviso y error que se generan en las operaciones, son todas estas variables las guardadas en la clase. Esta clase, para mejorar la comprensión del origen del atributo y a que parte de la aplicación se refiere, está dividida en Interfaces que separan el contexto y la operatibilidad de los atributos. Utils: Clase que contiene métodos comunes a toda la Web Tool. Algunos de estos métodos, los más significativos: ● public static Set searchGenes(Set vertexs, String sText): Busca en vertexs si alguno de los elementos tienes una label que contenga el literal sText pasado como parámetro. La Label del vértice se recoge a través del método comentado getUserDatum al cual se le pasa la key correspondiente. Retorna un tipo Set con todos los genes encontrados. ● public static Color colorCorrelationAlgorithm(double weight, double maxWeight): Retorna el nivel de gris, pasado con el parámetro weight y ponderado con el máximo valor de correlación de las aristas del grafo pasado con el parámetro maxWeight. Este color servirá para pintar las aristas en la operación “Correlations”. ● public static Color colorClustersAlgorithm(double valueColor, double maxColorClusterValue): Retorna el color que pondera el valor del gen pasado en el parámetro valueColor con el máximo valor encontrado en el preproceso que genera el color-clustervalue de cada gen, y que viene dado por el parámetro maxColorClusterValue. Este valor se aplicará a la componente azul del RGB, que será el que irá cambiando según el valor del gen, dejando las demás componentes a un valor fijo. Esto permite visualizar el resultado de la operación “Clusters”. ● public static Set fushionPickeds(Set actualPickeds, Set newPickeds): Retorna un Set con la unión de los dos Set pasados Página 90 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 como parámetros que representan los genes resultados de la operación realizada, newPickeds, y los que habian seleccionados antes de dicha operación, actualPickeds. es.com.uab.ibb.bioproject.visualization Este package contiene todas las clases que se encargan de gestionar el paint de los diferentes componentes del grafo. BioProjectLayout: Clase que gestiona el Layout del grafo. Es una clase extends de la clase edu.uci.ics.jung.visualization.AbstractLayout y su método más importante es el método protected void initializeLocations() donde se llama a la clase superior donde se inicializan las coordenadas (x,y) de cada nodo que serán renderizadas en el viewer. La clase JUNG ya se encarga de realizar el Layout por nosotros pero hemos de especificar un Layout propio nuestro para poder realizarlo pasando el grafo en el constructor el cual tiene almacenadas las parejas de coordenadas a través del metadata LOCATIONS en cada vértice. MyEdgePaintFunction: Es un extends de la clase edu.uci.ics.jung.graph.decorators.-AbstractEdgePaintFunction. JUNG Para que esta clase pueda realizar bien su cometido, es necesario pasarle al constructor una serie de parámetros que preparan la clase, según las operaciones en curso que tenga el usuario, para decidir como pintar la arista. Estos son: EdgeInMSTLabeller que es el parámetro con el Labeller de las aristas que pertenecen o no al grafo. booleano que nos señala si se está en esos momentos mostrando el MST. booleano que nos señala si en ese momento se está mostrando un Shortest Path calculado con la operación “mspath”. EdgeWeightLabeller que es el parámetro con el Labeller de los pesos de las aristas. boolean que nos señala si se están mostrando las aristas con el color determinado por la operación “paint correlations”. double que nos señala el máximo valor de correlación hallado en el preproceso para las aristas. Este valor no es exactamente el valor de una arista, sino que es el valor medio entre la máxima correlación encontrada en el MST y el encontrado en el preproceso done un filtro determina las mejores aristas del grafo con menor valor de correlación. El método más importante de esta clase es obviamente el que determina el color de la arista, public Paint getDrawPaint(Edge e) donde e es la arista de la cual se ha de determinar el color con el que se ha de pintar. MyEdgeStrokeFunction: Es un extendí de la edu.uci.ics.jung.graph.decorators.EdgeStrokeFunction. clase JUNG Esta clase determina que aspecto tendrá la arista, en grosor y trazo. Para ello, la clase recibe unos parámetros en su constructor con la misma Página 91 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 filosofía que en la clase comentada antes, prepararla para poder decidir como ha de pintar la arista. Estos parámetros son: EdgeInMSTLabeller que es el parámetro con el Labeller de las aristas que pertenecen o no al grafo. booleano que nos señala si se está en esos momentos mostrando el MST. booleano que nos señala si en ese momento se está mostrando un Shortest Path calculado con la operación “mspath”; El método más importante de la clase es el que determina como pintarla y es public Stroke getStroke(Edge e) el cual nos devuelve un objeto Java java.awt.Stroke con el shape de la arista para las condiciones en curso. MyVertexPaintFunction: Es un extends de la edu.uci.ics.jung.graph.decorators.VertexPaintFunction. clase JUNG Esta clase gestiona con que color se ha de pintar un nodo, o gen. Con la misma filosofía que las clases que forman parte del package, al constructor se le pasan una serie de parámetros para decidir como pintar ese nodo: booleano que nos señala si en ese momento se está mostrando un Shortest Path calculado con la operación “mspath”. boolean que nos señala si el usuario quiere realizar la operación “Paint Clusters”. Un Set con los nodos que forman parte de ese Shortest Path si este existe. La motivación de la necesidad de éste objeto es la de tener esta operación siempre mostrada independientemente de si el usuario decide realizar otra diferente, que no sea el cálculo de otro camino mínimo. Un Set que contiene los últimos nodos calculados o encontrados a partir de una operación. La motivación de esto es para señalarlos con un color diferente de los que ya existían antes de la operación realizada. Un objeto Picked Info que tiene lo nodos los cuales están picked, seleccionados, en el grafo, y que puede ser consecuencia de que el usuario los haya seleccionado explícitamente o resultado de una operación. Double que nos guarda el máximo valor calculado en el preproceso para el color-cluster value de todos los genes. Nos sirve para ponderar el color a pintar del nodo en cuestión cuando se realiza la operación “Paint Clusters”. El método más importante de esta clase es public Paint getFillPaint(Vertex v) y que devuelve un objeto java.awt.Paint con el color calculado para ese nodo. MyVertexShapeSizeAspectFunction: Extends de la clase JUNG edu.uci.ics.jung.graph.decorators.AbstractVertexShapeFunction e implementa dos interfaces, edu.uci.ics.jung.graph.decorators.Página 92 de 97 Darío Peña Seoane VertexAspectRatioFunction VertexSizeFunction. Fecha de creación 11/11/2007 81946322 y edu.uci.ics.jung.graph.decorators.- Esta clase genera el shape y el tamaño del nodo según la operación en curso. EL constructor recibe unos parámetros para ello: Set con los vértices seleccionados en este momento resultado de las últimas operaciones o que el usuario a seleccionado explícitamente. Set con los vértices resultado de la última operación. Esto es necesario para “restar” este conjunto al anterior y poder “destacar” éstos de los anteriores. Esto se realizará cambiando su forma o su tamaño. Los dos métodos más importante de esta clase son: public int getSize(Vertex v) que devuelve un int con el tamaño del nodo. public Shape getShape(Vertex v) que devuelve un objeto java.awt.Shape con el shape del nodo. Puede devolver una elipse o una estrella, esta última para designar genes encontrados en operaciones del tipo “Search” por ejemplo. [creo que era necesario este apartado para justificar lo hecho y para hacer una valoración global del proyecto] Si, incluso podrías haberlo extendido un poco más. 5 – Conclusiones y valoración de los objetivos conseguidos Por último, en esta sección haremos una breve valoración del proyecto y de los objetivos que finalmente se han podido satisfacer, y las conclusiones a las que se han llegado. Pasamos primero a valorar el framework JUNG. La herramienta JUNG permite la realización de proyectos complejos, con una curva de aprendizaje bastante rápida. El inconveniente, si se le puede llamar inconveniente, es que el usuario ha de ser un programador con experiencia en la tecnología Java, con conocimientos sólidos en Applets, en Swing y que sea capaz de entender clases abstractas como las que JUNG posee. Estas clases, una vez entendido su funcionamiento, hace mucho más fácil el proceso de desarrollo de herramientas o porciones de código ya que JUNG se encarga de la topología y de todo el renderer del grafo, con lo que el usuario sólo ha de preocuparse de “que ha” de hacer, no “como” ha de hacerlo. A partir de esta afirmación la conclusión es que, la herramienta, es fácilmente ampliable ya que las clases que definen la lógica de como debe comportarse ésta, son prácticamente independientes de la implementación del framework JUNG. Por tanto, una mejora,.o nueva versión, de éste no debería provocar muchos cambios en el diseño. El proyecto JUNG dispone de un foro técnico de apoyo, sólo en inglés, donde los creadores del framework (destacable lo de los creadores, ya que su trabajo es Página 93 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 incansable, y la contestación al cualquier duda es realizada en no más de 24-48 horas) y otros usuarios con experiencia, facilitan soluciones rápidas para cualquier duda o problema que se tenga. Actualmente JUNG dispone de una nueva versión, JUNG Alpha2, que es una nueva aproximación que da un salto cualitativo en grafos 3D, y una mejora ostensible en el renderer del framework, cosa que con la versión usada en el proyecto, ha motivado algún inconveniente. Éste inconveniente tiene nombre: el rendimiento. Ha sido un hándicap a la hora de decidirse por la cantidad de información que se deseaba filtrar en el preproceso. Con cantidades en torno a las 10K correlaciones, la herramienta funcionaba con una lentitud notable y se hacia muy lento su uso, sobre todo si en el filtro se ampliaba el intervalo con el control habilitado al respecto. Así, después de numerosas pruebas, se decidió que un rendimiento óptimo era 2K5 más las aristas del MST. Así, una posible mejora de la Herramienta, pasa por intentar la migración a la nueva versión de JUNG para poder cargar más información del grafo. Para ello en el preproceso se puede fijar el número de aristas y es fácilmente ampliable en caso de que sea necesario. Excepto, este pequeño inconveniente, la elección de JUNG como framework para el desarrollo del proyecto está claramente justificada. Hablaremos ahora de la Web tool propia haciendo una valoración sobre todo de los objetivos conseguidos. Hasta ahora el IBB disponía de una Web tool para poder realizar estudios de experimentos que daban como resultado microarrays. Estos no proporcionaban una visión tan directa como puede ser una interface como la realizada. Este proyecto, además de que será utilizado por el Instituto, facilitará en gran manera la investigación para encontrar “particularidades” en los experimentos realizados, ya sea a través del descubrimiento de patrones, mediante clusters o la visualización de relaciones directas con ayuda de MST o Shortest Paths, etc, etc. La herramienta ha cumplido satisfactoriamente los objetivos principales del proyecto, pero se han quedado algunos objetivos por realizar, como por ejemplo la posibilidad de visualización de hiperclusters del grafo, que también son calculados en el preproceso pero no se muestran y se dejará para una implementación posterior. En cuanto a la usabilidad, la Herramienta satisface completamente este aspecto ya que se dispone de todo el área de la pantalla para poder visualizar el grafo, y se creyó oportuno el emplazamiento del menú de operaciones en un frame lateral que hace que sea muy discreto y no interfiera en la visualización del mismo. Además, este panel de operaciones está dividido en subsecciones que guardan relación a la operación que realizan y que dan una idea clara de cómo localizar la operación deseada. Otro de los objetivos planteados era la posibilidad de, a partir del cálculo de una serie de genes poder lanzar unas aplicaciones externas para poder hacer un estudio mucho más exhaustivo y con mejores resultados. Éste se ha conseguido en el diseño de la interface. Respecto a la reutilización, ya hemos comentado antes cuando hablábamos de JUNG que es posible ampliar la Herramienta sin necesidad de un cambio sustancial en lo ya realizado. Por tanto, el objetivo de reutilización también esta justificado y conseguido. Página 94 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Finalmente, la valoración global del proyecto es alta. Un nuevo framework del cual se conoce su funcionamiento, con filosofía freeware, el resultado final de la aplicación, el diseño final, todos estos aspectos se han solucionado de una forma satisfactoria. Pero lo más importante es el hecho de haber podido trabajar en un campo apasionante, como es el de la Bioinformática, y saber que la Interactive Web Tool será utilizada en el ámbito de la investigación médica. Este último objetivo es el más valorado, ya que es un pequeño grano de arena para poder ayudar a descifrar el comportamiento de la vida y de nosotros mismos. Página 95 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 Tables Table I. Genes usados en los ejemplos. Estos han sido seleccionados de una matriz de 1426 genes enconteraods en un studio de una microarray en la acción de 118 substancias antitumorales . Esta microarray es la muestra de entrada usada en todos los ejemplos mostrados en esta memoria. Entrez Gene CDK7, cyclin-dependent kinase 7 CDK6, cyclin-dependent kinase 6 CCND1, cyclin D1 CCND2, cyclin D2 CCNE1, cyclin E1 TGFBR2, transforming growth factor, beta receptor II (70/80kDa) TXNDC5, thioredoxin domain containing 5 (EndoPDI) CPVL, carboxypeptidase, vitellogenic-like CDKN2A, cyclin-dependent kinase inhibitor 2A (melanoma, p16) CDKN1A, cyclin-dependent kinase inhibitor 1A (p21, Cip1) GADD45A, growth arrest and DNA-damage-inducible, alpha ERCC5, excision repair cross-complementing 5 CDC34, cell division cycle 34 TP53, tumour protein p53 (Li-Fraumeni syndrome) MDM2, transformed 3T3 cell double minute 2, p53 binding protein (mouse) TNK2, tyrosine kinase, non-receptor, 2 (ACK) 6 – Bibliografía 1. Huerta M., Cerdano J., Peña D., Rodriguez A. y Querol E: PCOPGene-Net: Holistic Characterisation of cellular states from microarray data based on continuous and non-continuous analysis of gene-expression relationships. BCM Bioinformatics, 2009. Página 96 de 97 Darío Peña Seoane Fecha de creación 11/11/2007 81946322 2. Cedano J, Huerta M, Querol E. NCR-PCOPGene: An Exploratory Tool for Analysis of Sample-Classes Effect on Gene-Expression Relationships Advances in Bioinformatics, vol. 2008 3. Delicado, P. Another look at principal curves and surfaces. Journal of Multivariate Analysis, 77, 84-116, 2001. 4. Delicado, P. and Huerta, M.: 'Principal Curves of Oriented Points: Theoretical and computational improvements'. Computational Statistics 18, 293315, 2003. 5. Huerta M, Cedano J, Querol E: Analysis of nonlinear relations between expression profiles by the principal curves of oriented-points approach. J Bioinform Comput Biol. 6:367-386. 2008. 6. Cedano J, Huerta M, Estrada I, Ballllosera F, Conchillo O, Delicado P, Querol E. A web server for automatic analysis and extraction of relevant biological knowledge. Comput Biol Med. 37:1672-1675.2007. 7. Instituto de Biotecnología y de Biomedicina (IBB) de la Universidad Autónoma de Barcelona. http://ibb.uab.es/ibb 8. http://revolutionresearch.uab.es : Web server for on line microarray analysis supported by the Institute of Biotechnology and Biomedicine of the Autonomous University of Barcelona (IBB-UAB) Página 97 de 97