Biclustering sobre datos de expresión génica basado en búsqueda dispersa

Biclustering sobre datos de expresi´on g´enica basado en b´usqueda dispersa Juan Antonio Nepomuceno Chamorro, [email protected] Supervisado por los profesores doctores: Alicia Troncoso Lora, Jes´us S. Aguilar Ruiz Tesis enviada a la comisi´on acad´emica del programa de doctorado de Ingenier´ıa Inform´atica, bajo la l´ınea de investigaci´on Ingenier´ıa y Tecnolog´ıa del Software, siguiendo los requerimientos para su lectura en el Departamento de Lenguajes y Sistemas Inform´aticos. (Tesis Doctoral) ´ Indice general ´ Indice de figuras V ´ Indice de tablas IX I Introducci´on 1 1. Introducci´on 3 1.1. Motivaci´on ............................ 3 1.2. Planteamiento........................... 5 1.3. Objetivos ............................. 6 1.4. Principales contribuciones . . . . . . . . . . . . . . . . . . . . 7 1.5. Estructura de la memoria . . . . . . . . . . . . . . . . . . . . 11 2. Sobre Bioinform´atica en el siglo XXI 13 2.1. Introducci´on............................ 13 2.2. Dogma central de la Biolog´ıa Molecular . . . . . . . . . . . . 14 2.3. Ciencias´omicas.......................... 16 2.4. Bioinform´atica .......................... 16 2.4.1. Descubrimiento de biomarcadores . . . . . . . . . . . . 17 2.5. Rudimentos de Biolog´ıa . . . . . . . . . . . . . . . . . . . . . 18 2.5.1. T´erminos b´asicos . . . . . . . . . . . . . . . . . . . . . 19 II Estado del arte 23 3. Datos de expresi´on g´enica 25 3.1. Introducci´on............................ 25 3.2. Datos de microarrays . . . . . . . . . . . . . . . . . . . . . . . 27 3.3. Proceso de trabajo . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.1. Repositorios p´ublicos . . . . . . . . . . . . . . . . . . . 30 i ii ´ INDICE GENERAL 3.3.2. Procesamiento de los datos . . . . . . . . . . . . . . . 32 3.3.3. Genes: nomenclatura y anotaciones . . . . . . . . . . . 33 3.3.4. Ontolog´ıa de Genes: GO . . . . . . . . . . . . . . . . . 33 4. Biclustering de datos de expresi´on g´enica 35 4.1. Introducci´on............................ 35 4.2. Definiciones............................ 37 4.2.1. NP-completitud . . . . . . . . . . . . . . . . . . . . . . 39 4.2.2. Patrones.......................... 40 4.3. Principales algoritmos de Biclustering . . . . . . . . . . . . . 43 4.3.1. Algoritmos cl´asicos . . . . . . . . . . . . . . . . . . . . 44 4.3.2. Algoritmos basados en metaheur´ısticas . . . . . . . . . 46 4.3.3. Algoritmos basados en correlaci´on . . . . . . . . . . . 50 4.3.4. Otros algoritmos . . . . . . . . . . . . . . . . . . . . . 51 4.4. Metodolog´ıa de comparaci´on y validaci´on . . . . . . . . . . . 53 4.5. Nuevas tendencias . . . . . . . . . . . . . . . . . . . . . . . . 54 5. Apuntes sobre integraci´on de informaci´on biol´ogica 57 5.1. Introducci´on............................ 57 5.2. Integraci´on de informaci´on biol´ogica . . . . . . . . . . . . . . 58 5.2.1. Medidas de similutud funcional entre genes basadas enGO........................... 59 III Propuestas 61 6. Biclustering usando la B´usqueda Dispersa como motor de b´usqueda 63 6.1. Introducci´on............................ 63 6.2. B´usqueda Dispersa: esquema b´asico . . . . . . . . . . . . . . . 64 6.3. B´usqueda Dispersa: m´etodos y detalles . . . . . . . . . . . . . 68 6.4. Codificaci´on de las soluciones . . . . . . . . . . . . . . . . . . 68 6.4.1. M´etodo de diversificaci´on . . . . . . . . . . . . . . . . 69 6.5. Construcci´on y reconstrucci´on del conjunto de referencia . . . 70 6.6. M´etodo de generaci´on de nuevas soluciones . . . . . . . . . . 71 6.7. M´etodo de combinaci´on y actualizaci´on del conjunto de referencia ............................... 72 6.8. M´etodo de la mejora . . . . . . . . . . . . . . . . . . . . . . . 72 ´ INDICE GENERAL iii 7. Criterio de b´usqueda basado en correlaci´on 73 7.1. Introducci´on............................ 73 7.2. Propuesta SSCorr: correlaciones lineales I . . . . . . . . . . . 73 7.2.1. Evaluaci´on de biclusters: funci´on objetivo . . . . . . . 74 7.2.2. M´etodo de la mejora . . . . . . . . . . . . . . . . . . . 75 7.3. Propuesta BISS: correlaciones lineales II . . . . . . . . . . . . 77 7.3.1. Evaluaci´on de biclusters: funci´on objetivo . . . . . . . 77 7.3.2. M´etodo de la mejora. . . . . . . . . . . . . . . . . . . 78 8. Criterio de b´usqueda basado en la integraci´on de informaci´on biol´ogica 81 8.1. Introducci´on............................ 81 8.2. Propuesta GoldBinch: integraci´on de informaci´on biol´ogica . 81 8.2.1. Datos de entrada . . . . . . . . . . . . . . . . . . . . . 82 8.2.2. Funci´on Objetivo . . . . . . . . . . . . . . . . . . . . . 82 8.2.3. Descripci´on del algoritmo . . . . . . . . . . . . . . . . 86 8.2.4. M´etodo de la mejora . . . . . . . . . . . . . . . . . . . 87 IV Resultados 89 9. SScorr: resultados 91 9.1. Introducci´on............................ 91 9.2. Resultados............................. 92 9.3. Discusi´on ............................. 94 9.4. An´alisis comparativo . . . . . . . . . . . . . . . . . . . . . . . 96 9.5. Estudio biol´ogico . . . . . . . . . . . . . . . . . . . . . . . . . 100 10.BISS: resultados 101 10.1.Introducci´on............................101 10.2. Descripci´on de los datos . . . . . . . . . . . . . . . . . . . . . 101 10.3. Configuraci´on de par´ametros . . . . . . . . . . . . . . . . . . 102 10.4.Resultados.............................105 10.4.1. Comparaci´on con algoritmos cl´asicos . . . . . . . . . . 105 10.4.2. Comparaci´on con algoritmos basados en correlaci´on . 111 10.4.3. Estudio de la significancia biol´ogica de los biclusters . 116 11.GoldBinch: resultados 119 11.1.Introducci´on............................119 11.2.Datos ...............................119 11.3.Resultados.............................120 iv ´ INDICE GENERAL 11.4. Discusi´on de los resultados . . . . . . . . . . . . . . . . . . . . 131 11.5. Evaluaci´on biol´ogica cualitativa . . . . . . . . . . . . . . . . . 139 V Conclusiones 147 12.Conclusiones y trabajos futuros 149 12.1.Conclusiones ...........................149 12.2. Futuras l´ıneas de investigaci´on . . . . . . . . . . . . . . . . . 152 VI Ap´endices 153 Bibliograf´ıa 171 ´ Indice de figuras 2.1. M´etodos de integraci´on de datos para el descubrimiento de interacciones genot´ıpicas-phenot´ıpicas. . . . . . . . . . . . . . 18 3.1. Dogma dentral de la Biolog´ıa Molecular. . . . . . . . . . . . . 26 3.2. Plataforma de microarray. . . . . . . . . . . . . . . . . . . . . 27 3.3. Flujo de trabajo con datos producidos mediante microarrays. 30 3.4. Navegador del repositorio GEO: acceso a datos. . . . . . . . . 32 4.1. Bicluster con valores coherentes. . . . . . . . . . . . . . . . . 41 4.2. Bicluster con patrones de desplazamiento. . . . . . . . . . . . 43 4.3. Bicluster con patrones de escalado. . . . . . . . . . . . . . . . 43 4.4. Bicluster con patrones de inhibici´on-activaci´on. . . . . . . . . 44 6.1. Esquema B´usqueda Dispersa o Scatter Search para Biclustering. 65 6.2. Microarray y bicluster {G3,G5,G6—C2,C3}con su codificaci´on. 69 6.3. Operador de cruce uniforme. . . . . . . . . . . . . . . . . . . 71 7.1. A la izquierda un bicluster formado por genes que no siguen un mismo patr´on de expresi´on. A derecha otro bicluster con patrones de desplazamiento y escalado. . . . . . . . . . . . . . 75 7.2. Un biclusters antes (izquierda) y despu´es (derecha) de ser sometido al m´etodo de la mejora. . . . . . . . . . . . . . . . . 76 7.3. Un bicl´uster antes (l´ınea discontinua) y despu´es (l´ınea resaltada) de haber aplicado el m´etodo de la mejora. . . . . . . . 79 8.1. Esquema del algoritmo de biclustering propuesto basado en un esquema de b´usqueda dispersa. . . . . . . . . . . . . . . . 86 8.2. Un peque˜no ejemplo que ilustra el m´etodo de la mejora. . . . 88 9.1. Resultados para el dataset Yeast . . . . . . . . . . . . . . . . 93 9.2. Resultados para el dataset Lymphoma . . . . . . . . . . . . . 94 9.3. Resultados para el dataset GaschYeast (M1= 1, M2= 1) . . 95 v vi ´ INDICE DE FIGURAS 9.4. Resultados para el dataset GaschYeast (M1= 10, M2= 10) . 96 9.5. Comparaci´on entre los distintos algoritmos de biclustering para el dataset GaschYeast . . . . . . . . . . . . . . . . . . . . . 97 9.6. Comparaci´on entre los distintos algoritmos de biclustering para el dataset GaschYeast con una definici´on m´as restrictiva de enriquecimiento biol´ogico . . . . . . . . . . . . . . . . . . . 99 9.7. Comparaci´on entre el algoritmo propuesto y el algoritmo CCCBi para el dataset GaschYeast . . . . . . . . . . . . . . . . . . 100 10.1. Porcentaje de biclusters enriquecidos obtenidos con BISS con diferentes valores del par´ametro. . . . . . . . . . . . . . . . . 103 10.2. Porcentaje de biclusters enriquecidos seg´un el valor de la funci´onobjetivo............................104 10.3. Tama˜no de los biclusters obtenidos con los algoritmos BISS, ChCh, ISA y OPSM con los datos de GDS1116. . . . . . . . . 107 10.4. Porcentaje de biclusters enriquecidos obtenidos por BISS, ChCh, ISA and OPSM para las ramas de GO BP, CC y MF con los datos de GDS1116 y GaschYeast. . . . . . . . . . . . . . . . . 109 10.5. Porcentaje de biclusters enriquecidos obtenidos por BISS, ChCh, ISA y OPSM para las ramas de GO BP, CC y MF con los datos de GDS1116 y GaschYeast tras el proceso de filtrado. . 110 10.6. Tama˜no de los biclusters obtenidos por BISS, BCCA-not, BCCA-yes y BICLIC para los datos de GDS1116. . . . . . . . 112 10.7. Porcentaje de biclusters enriquecidos obtenidos por BISS, BCCAnot, BCCA-yes y BICLIC para las ramas de GO BP, CC y MF con los datos de GDS1116 y GaschYeast. . . . . . . . . . 115 10.8. Porcentaje de biclusters altamente enriquecidos obtenidos por BISS, BCCA-not, BCCA-yes y BICLIC para las ramas BP, CC y MF con los datos GDS1116 y GaschYeast. . . . . . . . 116 10.9. Representaci´on de un bicluster obtenido por BISS con los datos de Alzheimer. . . . . . . . . . . . . . . . . . . . . . . . 117 11.1. Porcentaje de biclusters enriquecidos para GDS1116. . . . . . 125 11.2. Porcentaje de biclusters enriquecidos para GDS2914. . . . . . 126 11.3. Tama˜no de los biclusters obtenidos con GDS1116 cuando la correlaci´on y la integraci´on biol´ogica tienen la misma importancia................................126 11.4. Tama˜no de los biclusters obtenidos con GDS1116 cuando la integraci´on biol´ogica es m´as importante que la correlaci´on. . . 127 ´ INDICE DE FIGURAS vii 11.5. Tama˜no de los biclusters obtenidos con GDS1116 cuando la correlaci´on es m´as importante que la integraci´on biol´ogica. . . 127 11.6. Porcentaje de solapamiento entre los biclusters obtenidos para GDS1116..............................129 11.7. Histograma para el porcentaje de solapamiento entre los biclusters obtenidos para GDS1116. . . . . . . . . . . . . . . . . 130 11.8. Tama˜no de los biclusters obtenidos para CC, ISA y OPSM paraGDS1116. ..........................131 11.9. Grupo de t´erminos GO obtenidos con Revigo para el bicluster 1 para la medida FracGO y la configuraci´on 211. S´olamente se agrupan dos t´erminos: protein-ubiquitination y metabolism. 144 11.10.Grupo de t´erminos GO obtenidos con Revigo para el bicluster 1 para la medida FracGO y la configuraci´on 211. S´olamente se agrupan dos t´erminos: protein-ubiquitination y metabolism. 145 41. Introducci´on yBioinform´atica. La Miner´ıa de Datos (o Data Mining) surge en los a˜nos noventa en el contexto del descubrimiento de conocimiento en las bases de datos (Knowledge Discovery in Databases o KDD). Tiene como principal labor el descubrimiento de conocimiento previamente desconocido a partir de grandes vol´umenes de datos. Fusiona aspectos de la Estad´ıstica y el Aprendizaje Autom´atico y su principal labor es llevar a cabo un proceso de ingenier´ıa que d´e el paso de la Informaci´on al Conocimiento. La Computaci´on Evolutiva utiliza la met´afora de la teor´ıa de la evoluci´on darwinista como marco de referencia de una serie de algoritmos de optimizaci´on. Estos algoritmos son de tipo aproximado es decir, no encuentran la soluci´on exacta del problema de optimizaci´on sino una aproximaci´on a la misma. Permiten tratar aquellos problemas de optimizaci´on computacionalmente intratables o NP-completos para los que no existe un algoritmo exacto que los resuelva. La Bioinform´atica consiste en el estudio y desarrollo de t´ecnicas que permitan, entre otros aspectos, el descubrimiento de nuevos biomarcadores o indicios que permitan tanto el pron´ostico como el diagn´ostico de enfermedades. El desarrollo de metodolog´ıas, tanto predictivas como de clasificaci´on, usando datos ´omicos constituye una de las principales tareas de la Bioinform´atica en la actualidad. Los datos de expresi´on g´enica obtenidos mediante la tecnolog´ıa de microarray son un tipo particular de datos ´omicos. Esta tecnolog´ıa permite monitorizar el nivel de expresi´on de un grupo de genes de una muestra obtenida en el laboratorio. De esta forma se pueden generar matrices de expresi´on donde cada elemento refleja el nivel de expresi´on de un gen bajo una determinada condici´on experimental. Este tipo de datos constituyen una fotograf´ıa del proceso de transcripci´on, mediante el que el ADN se transforma en ARN, por eso son datos transcript´omicos, por lo que constituyen una herramienta muy interesante para el estudio de procesos biol´ogicos y el descubrimiento de biomarcadores en general. Los conjuntos de datos, o datasets, de este tipo tienen como caracter´ıstica un n´umero muy elevado de genes, del orden de miles, frente a un n´umero reducido de condiciones, decenas, lo que determina el tipo de an´alisis que se efect´uen sobre ellos. Adem´as, por otro lado, la propia naturaleza del problema biol´ogico condiciona la tarea misma que se debe realizar. El Biclustering es una t´ecnica de aprendizaje no supervisado que agrupa tanto genes como condiciones. Este doble agrupamiento lo diferencia del clustering tradicional sobre este tipo de datos ya que s´olo agrupa o bien genes o condiciones. El objetivo es el descubrimiento de patrones locales m´as que la divisi´on en grupos de los datos para una posterior clasificaci´on. Mediante el biclustering se pueden descubrir grupos de genes que se expresen de una 1.2. Planteamiento 5 manera similar bajo unas determinadas condiciones. Es decir, se trata de un problema de b´usqueda de patrones para determinar qu´e genes se activan o desactivan cuando ocurren unas condiciones concretas objeto de estudio. Computacionalmente es un problema intratable o NP-completo. La motivaci´on de la tesis presentada es la elaboraci´on de una t´ecnica de biclustering mediante una metaheur´ıstica evolutiva, concretamente la b´usqueda dispersa (o scatter search). Se trata de un problema de Miner´ıa de Datos, el biclustering, abordado como un problema de optimizaci´on que se resuelve mediante una t´ecnica evolutiva, la b´usqueda dispersa, en el contexto del an´alisis de datos de expresi´on g´enica. Por lo tanto, el trabajo desarrollado constituye un claro ejemplo del tri´angulo antes descrito que tiene la Miner´ıa de Datos, la Computaci´on Evolutiva y la Bioinform´atica como v´ertices. 1.2. Planteamiento El punto de partida de la tesis presentada es el trabajo presentado en [1]. En este art´ıculo se demuestra que la medida que usualmente se utiliza como criterio de evaluaci´on en los algoritmos de biclustering, el residuo cuadr´atico medio (o Mean Squared Residue), no detecta cierto tipo de patrones importantes desde el punto de vista biol´ogico. Estos patrones son aquellos patrones con un escalado pronunciado entre los genes. El inicio del trabajo lo constituye el estudio de los criterios de b´usqueda de biclusters as´ı como el desarrollo de un algoritmo que permita su posterior uso. Tras varias aproximaciones, se plantea un algoritmo de biclustering basado en una metaheur´ıstica de b´usqueda dispersa. La propuesta SSCorr presenta la adaptaci´on del esquema de b´usqueda dispersa al contexto del biclustering. Se plantea el problema como un problema de optimizaci´on cuya funci´on objetivo basa su criterio de calidad en la correlaci´on lineal. Los resultados se analizan de una manera est´andar utilizando tres conjuntos de datos y, por otro lado, se presentan la comparaci´on con los algoritmos usados como marco de referencia en la mayor´ıa de los algoritmos de biclustering. Los buenos resultados obtenidos, junto con ciertas mejoras en la funci´on de calidad del algoritmo SSCorr, motivan una segunda propuesta BISS que captura patrones de activaci´on e inhibici´on de genes. En este paso se hace un especial ´enfasis en el an´alisis de los resultados y sobre todo en la comparaci´on con otras propuestas de la bibliograf´ıa, tanto los algoritmos generalmente utilizados como marco de referencia como otros algoritmos de biclustering basados en correlaciones lineales. Una de las tareas m´as complicadas en los trabajos de biclustering lo constituye las comparaciones entre algoritmos. Como se tratan de t´ecnicas no supervisadas, donde no hay una medida de 61. Introducci´on la precisi´on, se debe utilizar el conocimiento experto para la comparaci´on entre los resultados de los algoritmos. Para manejar dicho conocimiento se emplean repositorios de genes como Gene Ontology (GO), mediante los que se puede asociar una funcionalidad biol´ogica a un grupo de genes. Dicho estudio recibe el nombre de estudio de enriquecimiento de genes. En funci´on de si los biclusters encontrados representan o no una funci´on se establece un ranking entre los resultados obtenidos por los distintos algoritmos. Dicho ranking se establece seg´un el porcentaje de biclusters enriquecidos que cada algoritmo encuentra. El an´alisis biol´ogico de los resultados constituye una de las principales motivaciones para el trabajo que se presenta en BISS. En este trabajo no s´olo se ampl´ıa la propuesta anterior y se realiza un estudio comparativo m´as especializado, sino que se profundiza en la comparaci´on de los resultados desde un punto de vista biol´ogico. La experiencia adquirida en las propuestas de SSCorr y BISS, junto con un an´alisis de bibliograf´ıa existente, plantea una nueva propuesta, denominada como GoldBinch, que integra la informaci´on biol´ogica almacenada en GO, no ya como informaci´on que se use a posteriori en la fase de an´alisis de los resultados, sino como criterio de la b´usqueda en s´ı. Desde nuestro conocimiento, no existen algoritmos de biclustering que integren informaci´on biol´ogica como parte del criterio de b´usqueda de resultados. La integraci´on de informaci´on de distintas fuentes de datos, usando los repositorios p´ublicos existentes, es una de las ´ultimas tendencias en bioinform´atica. Se plantea un algoritmo de b´usqueda dispersa para biclustering cuya funci´on objetivo a˜nade un t´ermino extra que refleja, por cada bicluster que se eval´ue, la calidad de ese grupo de genes seg´un su informaci´on almacenada en GO. Se estudian dos posibilidades para dicho t´ermino de integraci´on de informaci´on biol´ogica, se comparan entre s´ı y se comprueba que los resultados son mejores cuando se usa informaci´on biol´ogica. Junto con la evaluaci´on est´andar usada en biclustering, se presenta tambi´en un an´alisis de tipo cualitativo que permite apreciar las diferencias entre las dos formas propuestas de integrar de la informaci´on biol´ogica. 1.3. Objetivos Los objetivos concretos de la presente tesis son: Estudio de los patrones de desplazamiento y escalado como punto de partida. Elecci´on de un criterio de calidad para el proceso de optimizaci´on que permita la b´usqueda de biclusters con dichos patrones. 1.4. Principales contribuciones 7 Desarrollo de un algoritmo de biclustering basado en una metaheur´ıstica de b´usqueda dispersa. Estudio de otro tipo de patrones biol´ogicos no contemplados anteriormente. Comparaci´on del algoritmo propuesto con otros algoritmos de la bibliograf´ıa, tanto de tipo general como aquellos basados en la correlaci´on lineal. Desarrollo de un algoritmo de biclustering que integre informaci´on biol´ogica junto un an´alisis de los resultados tanto cuantitativo como cualitativo. 1.4. Principales contribuciones Las propuestas realizadas en esta tesis han dado lugar a resultados publicados tanto en revistas como en conferencias nacionales e internacionales. Los resultados publicados en revistas son: Un algoritmo de biclustering basado en un esquema de b´usqueda dispersa. La funci´on objetivo se basa en correlaciones lineales entre los genes y captura patrones de desplazamiento y escalado. Los algoritmos de biclustering existentes en la bibliograf´ıa hasta ese momento se basaban en el residuo (MSR) como medida de calidad. Los resultados experimentales y las comparaciones con otros algoritmos se presentan siguiendo las pautas generales de otros art´ıculos de la bibliograf´ıa. La propuesta SSCorr descrita en los cap´ıtulos VII y IX se presenta en este trabajo: •“Biclustering of Gene Expression Data by Correlation-Based Scatter Search”. Juan A. Nepomuceno et al. BioData Mining, 2011, 4, 3. DOI: 10.1186/1756-0381-4-3, Impact Factor1: 1.54. Cuartil: Q2 (Categor´ıa: Mathematical and Computational Biology). Citas: (23 citas seg´un Google Scholar (01-05-2015)). Un algoritmo que mejora la funci´on objetivo del algoritmo anterior, as´ı como otros aspectos del esquema de b´usqueda dispersa. Se capturan de esta forma comportamientos de activaci´on-inhibici´on entre genes no contemplados anteriormente. El estudio experimental presentado hace 1La revista no ten´ıa ´ındice de impacto el a˜no de publicaci´on del art´ıculo. 81. Introducci´on especial hincapi´e en el contexto biol´ogico. La comparativa realizada se ha efectuado respecto a los algoritmos cl´asicos de biclustering as´ı como tambi´en respecto a otros algoritmos basados en la correlaci´on. La propuesta BISS descrita en los cap´ıtulos VII y X se presenta en este trabajo: •“Scatter Search-based identification of local patterns with positive and negative correlations in gene expression data”. Juan A. Nepomuceno et al. Applied Soft Computing. Impact Factor: 2.6. Cuartil: Q1 (Categor´ıa: Computer Science and Artificial Intelligence). Un algoritmo de biclustering que integra informaci´on biol´ogica en el criterio de b´usqueda. El algoritmo se basa en un esquema de b´usqueda dispersa que permite intercambiar varias medidas de integraci´on de informaci´on biol´ogica. El estudio experimental se lleva a cabo con un doble objetivo: mostrar que la integraci´on de informaci´on biol´ogica mejora los resultados, as´ı como estudiar las diferencias entre dos posibles formas de integrar la informaci´on. Se realiza un estudio tanto cuantitativo como cualitativo de los resultados. As´ı mismo, los resultados se comparan con los algoritmos cl´asicos de biclustering. La propuesta GoldBinch descrita en los cap´ıtulos VIII y XI se presenta en este trabajo: •“Integrating biological knowledge based on functional annotations for biclustering of gene expression data”. Juan A. Nepomuceno et al. Computer Methods and Programs in Biomedicine, 2015 May; 119(3):163-80. DOI: 10.1016/j.cmpb.2015.02.010, Impact Factor: 1.093. Cuartil: Q1 (Categor´ıa: Computer Science, Theory and Methods). As´ı mismo, los resultados publicados en congresos nacionales e internacionales son: Un estudio de m´etodos cl´asicos de optimizaci´on local para la detecci´on de patrones de desplazamiento y escalado. Las publicaciones asociadas son: •“Biclusters Evaluation Based on Shifting and Scaling Patterns’’. IDEAL 2007: 8th International Conference on Intelligent Data 1.4. CONTRIBUCIONES 9 Engineering and Automated Learning. Birmingham, UK, December, 16-19, 2007, pp. 840-849. •“Patrones en Biclusters usando T´ecnicas de Optimizaci´on sin Restricciones”. MAEB 2007: Metaheur´ısticas, Algoritmos Evolutivos y Bioinspirados. Tenerife, Espa˜na, pp. 413-417. •“Evaluaci´on de Biclusters basada en patrones de desplazamiento y escalado” Juan A. Nepomuceno et al. I Workshop Espa˜nol sobre Extracci´on y Validaci´on de Conocimiento en Bases de Datos Biom´edicas (EvaBio 2007). Salamanca, Spain. Un algoritmo de biclustering basado en un esquema h´ıbrido, entre una b´usqueda dispersa y un algoritmo gen´etico, que usa el residuo cuadr´atico (MSR) como criterio de b´usqueda de biclusters. Las publicaciones asociadas son: •“A Hybrid Metaheuristic for Biclustering Based on Scatter Search and Genetic Algorithms”. PRIB 2009: Pattern Recognition in Bioinformatics, 4th IAPR International Conference. Sheffield, UK, September 7-9, 2009, pp 199-210. •“Un algoritmo de Biclustering Basado en B´usqueda Dispersa y Algoritmos Gen´eticos” Juan A. Nepomuceno et al. II Workshop Espa˜nol sobre Extracci´on y Validaci´on de Conocimiento en Bases de Datos Biom´edicas (EvaBio 2009). Sevilla, Spain. Estudio del solapamiento entre los biclusters obtenidos por el algoritmo anteriormente presentado. Se analiza el papel de un factor de correcci´on del solape en la funci´on objetivo. •“An Overlapping Control-Biclustering Algorithm from Gene Expression Data”. ISDA 2009: International Conference on Intelligent Systems Design and Applications. Pisa, Italy, November 30-December 2, 2009, pp 1239-1244. Un algoritmo de biclustering inspirado en un esquema de b´usqueda dispersa que utiliza la correlaci´on como mecanismo de b´usqueda de biclusters. •“Evolutionary metaheuristic for biclustering based on linear correlations among genes”. SAC 2010: Proceedings of the 2010 ACM Symposium on Applied Computing (SAC). Sierre, Switzerland, March 22-26, 2010, 1143-1147. 10 1. Introducci´on Un primer algoritmo de biclustering basado en una b´usqueda dispersa. El algoritmo es una modificaci´on de algoritmo anterior de manera que se incorpora un m´etodo de la mejora en el esquema. Las publicaciones asociadas son: •“Correlation-Based Scatter Search for Discovering Biclusters from Gene Expression Data”. EvoBIO 2010: Proceedings of the 8th European Conference on Evolutionary Computation, Machine Learning and Data Mining. Istanbul, Turkey, April 7-9, 2010, pp 122133. •“B´usqueda Dispersa aplicada al descubrimiento de patrones en datos de expresi´on gen´etica”. MAEB 2010: Metaheur´ısticas, Algoritmos Evolutivos y Bioinspirados, Valencia, Espa˜na. Estudio de una b´usqueda local que mejore los resultados del algoritmo propuesto anteriormente. •“A local search in Scatter Search for improving Biclusters”. Juan A. Nepomuceno et al. 3th Congress on Natural and Biologically Inspired Computing (NaBIC 2011). Salamanca, Spain, 2011, pp 521-526. Estudio de la estructura interna de los biclusters obtenidos as´ı como su utilizaci´on para la generaci´on de redes de co-expresi´on de genes. Publicaciones asociadas: •“Inferring gene coexpression networks with Biclustering based on Scatter Search”. Juan A. Nepomuceno et al. 11th International Conference on Intelligent Systems Design and Applications (ISDA 2011). C´ordoba, Spain, 2011, 1091 -1096. •“Inferring gene co-expression networks with Biclustering based on linear correlations among genes”. Juan A. Nepomuceno et al. P´oster en Benelux Bioinformatics Conference (BBC 2011). CRP Sant´e Luxemburgo. Una primera aproximaci´on a un algoritmo de biclustering que integre informaci´on biol´ogica como criterio de b´usqueda. •“GoldBinch: a scatter search-based biclustering of gene expression data algorithm that integrates biological knowledge with functional annotations”. Juan A. Nepomuceno et al. P´oster en XII Symposium on Bioinformatics 2014. Sevilla, Spain. 1.5. Estructura de la memoria 11 1.5. Estructura de la memoria La memoria de la tesis se organiza por cap´ıtulos de la siguiente manera. En el cap´ıtulo II se presenta el contexto de la tesis. Se introduce el dogma central de la Biolog´ıa Molecular, la revoluci´on de los datos ´omicos y qu´e se entiende por Bioinform´atica en la actualidad. As´ı mismo, se proporciona un glosario de t´erminos con los conceptos de Biolog´ıa necesarios para entender el marco de trabajo. El estado del arte se compone de tres apartados, los cap´ıtulos III y IV dedicados a los datos de expresi´on g´enica y al estado del arte de biclustering respectivamente, as´ı como unos apuntes sobre trabajos que integran informaci´on biol´ogica en el cap´ıtulo V. En el cap´ıtulo III se presenta la tecnolog´ıa de microarray y se muestra c´omo es el flujo de trabajo normal con estos datos. Este cap´ıtulo tiene como objetivo la exposici´on de la dificultad de trabajo con este tipo de datos as´ı como la experiencia adquirida en su manejo. La idea central del cap´ıtulo es contextualizar el biclustering como una t´ecnica de an´alisis de datos de expresi´on g´enica a alto nivel. En el cap´ıtulo IV se presentan el problema del biclustering as´ı como un resumen exhaustivo de los principales algoritmos desarrollados estos ´ultimos a˜nos. El cap´ıtulo V contiene unos peque˜nos apuntes sobre t´ecnicas en las que se integra informaci´on biol´ogica en su funcionamiento. As´ı mismo, se apuntan varios trabajos sobre medidas de similitud entre genes basadas en la informaci´on almacenada en la ontolog´ıa de genes GO. En el cap´ıtulo VI se explica el motor de b´usqueda de los algoritmos que se presentan en la tesis. Se basa en una metaheur´ıstica de b´usqueda dispersa adaptada al problema del biclustering. Se explica en detalle su funcionamiento, as´ı como los distintos procedimientos internos y su adaptaci´on al problema. En el cap´ıtulo VII se presentan las dos propuestas SSCorr y BISS que utilizan la correlaci´on lineal como criterio para la b´usqueda de biclusters. SScorr es una primera aproximaci´on que encuentra patrones de desplazamiento y escalado. BISS modifica a SSCorr de manera que incluye tambi´en patrones de activaci´on-inhibici´on. Estos patrones reflejan genes que tengan un patr´on de expresi´on complementario, es decir, la inhibici´on implica la activaci´on de otro gen. En el cap´ıtulo VIII se presenta la propuesta GoldBinch, que incorpora informaci´on biol´ogica como criterio de b´usqueda de biclusters. Adem´as de la matriz de expresi´on, se incorpora como datos de entrada un fichero de anotaciones directa que asocia a cada gen un t´ermino con un significado biol´ogico. Por ejemplo, cada gen se asocia con un conjunto de t´erminos GO. 12 1. Introducci´on De esta forma se incorpora, a trav´es de una medida de similitud funcional entre genes, informaci´on biol´ogica almacenada en repositorios p´ublicos como GO o Kyoto Encyclopedia of Genes and Genomes (KEEG). En este cap´ıtulo se exponen tambi´en las modificaciones necesarias en la b´usqueda dispersa relativas a la incorporaci´on de este criterio de b´usqueda. Los cap´ıtulos IX, X y XI muestran los experimentos realizados y los resultados obtenidos con las propuestas anteriores. En el cap´ıtulo IX se expone la experimentaci´on llevada a cabo con la propuesta SSCorr. Dicha experimentaci´on sigue las pautas est´andares de los art´ıculos de biclustering. En el cap´ıtulo X, por contra, se hace especial ´enfasis en el contexto biol´ogico del problema. La validaci´on de los resultados se lleva a cabo teniendo en cuenta todas las ramas de la ontolog´ıa GO as´ı como refinando el concepto de bicluster enriquecido. Es decir, se validan los resultados teniendo especialmente en cuenta el contexto del problema. As´ı mismo, se incluye comparativas con algoritmos recientes de biclustering basados tambi´en en la correlaci´on y que no se hab´ıan estudiado en la experimentaci´on del cap´ıtulo anterior. En el cap´ıtulo XI se presenta el estudio experimental realizado con la propuesta GoldBinch. Los experimentos se han realizado con un doble objetivo: verificar que la integraci´on de informaci´on biol´ogica mejora los resultados del proceso de biclustering y, por otro lado, comparar las dos posibilidades de integraci´on contempladas en GoldBinch. Los resultados han sido estudiados en funci´on del enriquecimiento de los biclusters obtenidos. Con vistas a mostrar las diferencias entre las dos medidas de integraci´on biol´ogica, tambi´en se ha considerado la naturaleza de dicho enriquecimiento, en concreto el n´umero de t´erminos GO asociados a cada bicluster enriquecido. As´ı mismo, y partiendo de esta misma motivaci´on, se a˜nade un estudio cualitativo de algunos biclusters de manera que se observe claramente las diferencias entre las dos medidas de integraci´on. La experimentaci´on llevada a cabo tambi´en incluye una comparativa con los algoritmos cl´asicos de biclustering. Finalmente, en el cap´ıtulo XII se exponen las conclusiones la tesis, as´ı como las futuras l´ıneas de investigaci´on que el trabajo presentado invita a explorar. Cap´ıtulo 2 Sobre Bioinform´atica en el siglo XXI La consecuencia de todos estos progresos es que en el centro mismo de la Biolog´ıa y la Medicina ha surgido una nueva ciencia a la que podr´ıamos llamar criptograf´ıa del ADN. Hemos interceptado un mensaje muy sofisticado que reviste una importancia crucial para el futuro de la especie humana. Est´a escrito en un c´odigo extra˜no y aparentemente indescifrable, enga˜nosamente en su uso de tan s´olo cuatro letras, pero lo bastante complejo como para que sean necesarias varias d´ecadas antes de que una combinaci´on de ingenio, investigaci´on de laboratorio y un complicado an´alisis por medio de las m´as potentes supercomputadoras acaben por desvelar todos los secretos del c´odigo. Pero ¡qu´e fant´astica aventura! El lenguaje de la Vida: el ADN y la Revoluci´on de la Medicina Personalizada. Francis Collins (p´ag. 36) 2.1. Introducci´on Recientemente aparec´ıa un art´ıculo en prensa1sobre la creatividad. En este art´ıculo se expon´ıan una serie de citas sobre c´omo surg´ıan las ideas y se abr´ıa la reflexi´on con un ejemplo concreto: la experiencia de un concierto en Estocolmo en el que, seg´un el autor, se hab´ıa conseguido una experiencia musical trascendente. El int´erprete era un virtuoso del viol´ın perteneciente a la escuela de violinistas de San Petersburgo, fundada en 1868 por Leopoldo Auer, que tocaba una obra de Bach de 1720 compuesta para viol´ın y lo 1http://cultura.elpais.com/cultura/2014/11/19/babelia/1416418422_239455. html 13 20 2. Bioinform´atica especifican qu´e amino´acido es necesario en cada paso de la elaboraci´on de la prote´ına. ARN (´acido ribonucleico): mol´ecula parecida al ADN. A diferencia de ´este, el ARN tiene una sola hebra, que est´a compuesta por un az´ucar distinto (la ribosa) y grupos fosfatos alternados. A cada mol´ecula de az´ucar se une una de las siguientes cuatro bases: A (adenina), U (uracilo), C (citosina) o G (guanina). En la c´elula existen varios tipos de ARN: ARN mensajero, ARN ribos´omico y ARN de transferencia. Recientemente se ha descubierto que algunos ARN intervienen en la regulaci´on de la expresi´on g´enica. ARNm o mensajero: molde para la s´ıntesis de prote´ınas en los ribosomas del citoplasma. Cada juego de tres bases, llamado cod´on, especifica un amino´acido en la secuencia que comprende la prote´ına. La secuencia de la cadena ´unica del ARNm est´a basada en la secuencia de una cadena complementaria de ADN. Amino´acido: grupo de veinte mol´eculas peque˜nas distintas que se unen formando cadenas largas o polip´eptidos. Una prote´ına est´a constituida por uno o m´as polip´eptido. La secuencia de amino´acidos hace que el polip´eptido se pliegue de una forma determinada que es biol´ogicamente activa. Las secuencias de amino´acidos de las prote´ınas est´an codificadas en los genes. Prote´ına: una mol´ecula compuesta por una o m´as cadenas de amino´acidos. La secuencia de ´estos es una traducci´on de la secuencia de ADN del gen que codifica la prote´ına. Las prote´ınas desempe˜nan una amplia gama de actividades vitales en la c´elula: estructurales (citoesqueleto), mec´anicas (m´usculo), bioqu´ımicas (enzimas) y de se˜nalizaci´on celular (hormonas). Las prote´ınas tambi´en son una parte esencial de la dieta. ADN no codificador: ADN que no codifica amino´acidos. La mayor´ıa del ADN no codificador se encuentra entre genes en los cromosomas y su funci´on es desconocida. Otras secuencias de ADN no codificadoras son los intrones, que se encuentran dentro de los genes. Algunos segmentos de ADN no codificador intervienen en la regulaci´on de la expresi´on g´enica. Citoplasma: l´ıquido gelatinoso del interior de la c´elula. Est´a compuesto por agua, sales y varias mol´eculas org´anicas. Algunos org´anulos intracelulares, como el n´ucleo y las mitoc´ondrias, est´an envueltos en membranas que los separan del citoplasma. 2.5. Rudimentos de Biolog´ıa 21 Genoma: conjunto completo de instrucciones gen´eticas de una c´elula. En los humanos, el genoma est´a formado por 23 pares de cromosomas que se encuentran en el n´ucleo m´as un peque˜no cromosoma en las mitocondrias de la c´elula. Estos cromosomas contienen en conjunto aproximadamente 3.100 millones de bases. Car´acter polig´enico: car´acter, o caracter´ıstica, cuyo fenotipo est´a influido por m´as de un gen. Lo caracteres que exhiben una distribuci´on continua, como la estatura o el color de la piel, son polig´enicos. La herencia de los genes polig´enicos no obedece los t´ıpicos cocientes fenot´ıpicos de la herencia mendeliana, aunque cada uno de los genes que contribuyen a definir un rasgo se hereda del modo que describi´o Mendel. Muchos caracteres polig´enicos tambi´en est´an influidos por el ambiente y reciben el nombre de multifactoriales. Gen supresor de tumores: Gen cuya funci´on normal consiste en dirigir la producci´on de una prote´ına que forma parte del sistema que frena la divisi´on celular. La prote´ına supresora de tumores mantiene la divisi´on celular bajo control; sin embargo, cuando muta y no puede realizar bien su trabajo, puede desencadenarse un crecimiento celular incontrolado que contribuye al desarrollo del c´ancer. Oncog´en: Gen mutado que puede hacer que las c´elulas normales se conviertan en c´elulas cancerosas. En su forma normal, sin mutaci´on, reciben el nombre de protooncogenes, y participan en la regulaci´on de la divisi´on celular. Los oncogenes act´uan como el acelerador de un coche, empujando las c´elulas a dividirse. Mutaci´on: alteraci´on estructural permanente en el ADN. En la mayor´ıa de los casos pueden no tener ning´un efecto o causar da˜no, pero en ocasiones una mutaci´on puede mejorar la probabilidad de supervivencia de un organismo. Las mutaciones pueden originarse en errores de copia del ADN, exposici´on a radiaciones ionizantes, exposici´on a sustancias qu´ımicas mut´agenas o infecci´on por virus. Las mutaciones en la l´ınea germinal son las que se producen en el ´ovulo o espermatozoide, y son transmitidas a la descendencia. Las mutaciones som´aticas, en cambio, se producen en las c´elulas del cuerpo y no se transmiten. Prognosis: La evoluci´on probable o prevista de una enfermedad. Diagnosis: La identificaci´on de la naturaleza y causa de un determinado trasntorno. 22 2. Bioinform´atica Fenotipo: Manifestaci´on visible del genotipo. Caracter´ısticas observables de un determinado organismo. Genotipo: Informaci´on gen´etica de un determinado organismo. Se deben diferenciar y no confundir los t´erminos gen´etico, g´enico y gen´omico. Gen´etico: relativo a la gen´etica, es decir, relacionado con la herencia G´enico: relativo a los genes. Gen´omico: relativo al genoma, es decir, genes, prote´ınas y todo lo relacionado con la gen´omica. Parte II Estado del arte 23 Cap´ıtulo 3 Datos de expresi´on g´enica ...una cosa es saber de f´ısica de una forma abstracta y otra muy distinta lidiar con problemas directamente relacionados con datos experimentales, como los que proven´ıan de la nueva tecnolog´ıa que se estaba desarrollando en Los ´ Alamos. Aventuras de un matem´atico. Memorias de Stanislam M. Ulam (p´ag. 160). 3.1. Introducci´on Todas las c´elulas de nuestro cuerpo tienen en su n´ucleo el mismo ADN sin embargo existe una gran variedad tanto morfol´ogica como funcionalmente entre ellas. Se considera el dogma central de la Biolog´ıa Molecular a la explicaci´on tradicional del proceso mediante el cual la informaci´on almacenada en las hebras de ADN da lugar a una prote´ına o producto funcional. B´asicamente se puede resumir diciendo que el ADN da lugar al ARN mediante el proceso de transcripci´on y ´este, mediante el proceso de translaci´on, origina los amino´acidos que, mediante plegados y composici´on de las cadenas que forman, construyen las prote´ınas. Las prote´ınas son las unidades funcionales que est´an implicadas en las distintas funciones biol´ogicas que tienen lugar en nuestro organismo. Se llama expresi´on de un gen al proceso completo mediante el cual un gen da lugar a un producto funcional. Por lo tanto, se puede decir que mediante la transcripci´on de un trozo de ADN se origina una cadena de ARN que da lugar a una cadena de amino´acidos mediante el proceso de translaci´on. La translaci´on se lleva a cabo mediante los ribosomas, en el citoplasma de la c´elula, y las prote´ınas se forman al plegarse las cadenas de amino´acidos producidas seg´un las propiedades f´ısico-qu´ımicas del entorno. La figura muestra un esquema del dogma central de la Biolog´ıa 25 26 3. Datos Molecular. ADN ARN Aminoácidos/Proteínas Transcripción Translación gen producto funcional “Dogma central de la Biología Molecular” Figura 3.1: Dogma dentral de la Biolog´ıa Molecular. Los genes son fragmentos de ADN que act´uan como unidades f´ısicas y funcionales de la herencia y cuando se activan codifican una prote´ına. Sin embargo su activaci´on depende de una serie de circunstancias. Es decir, la regulaci´on de la expresi´on de un gen viene determinada mediante una serie de condiciones que aportan la informaci´on necesaria para que dicho gen se active. Se llama regulaci´on g´enica al proceso que origina que un gen se active o no. La mayor parte de los procesos de regulaci´on g´enica tienen lugar durante el proceso de transcripci´on y las condiciones que los originan reciben el nombre de factores de transcripci´on. El estudio de dichas condiciones es fundamental para entender la mayor´ıa de los procesos biol´ogicos, enfermedades, etc, de origen gen´etico. El esquema descrito en la figura es un simplificaci´on. El dogma central de la Biolog´ıa Molecular representa la visi´on cl´asica seg´un la cual un gen da lugar a una prote´ına. En la actualidad se sabe que en la mayor´ıa de los casos no es tan simple y que en general un grupo de genes actuando conjuntamente regulan que una determinada funci´on se determine o no, es decir que varios genes codifican una o varias prote´ınas. Las situaciones en las que un gen codifica un producto funcional constituye la excepci´on en lugar de la regla. Esta visi´on, que podemos llamar de tipo hol´ıstico o de sistemas, es la m´as aceptada en la actualidad. Bajo esta perspectiva se habla de caracteres polig´enicos omultifuncionales en contraposici´on a la situaci´on en la que un s´olo gen determina una determinada funcionalidad. Como ya hemos comentado los genes son fragmentos de ADN que se disponen de forma que constituyen las unidades funcionales de herencia. En el caso de los humanos tenemos por ejemplo aproximadamente 20.000 genes que codifican prote´ınas. El resto del ADN tiene informaci´on que no codifica prote´ınas y que hasta ahora recib´ıa el nombre de ADN basura. Es decir, tan s´olo serv´ıa como separador de los trozos de ADN, los genes, que s´ı codifican prote´ınas. Recientemente se ha descubierto que estas ampl´ıas regiones del 3.2. Datos de microarrays 27 ADN, la mayor parte, no cumple una funci´on testimonial sino que interviene directamente en los procesos reguladores de genes. El papel de las regiones de ADN, no codificantes o basura, juega un papel fundamental en el proceso de expresi´on g´enica. En cualquier caso los factores ambientales son primordiales para estudiar cu´ando un gen, o un grupo de genes, se activan y codifican un grupo de prote´ınas que determinan una funci´on biol´ogica. 3.2. Datos de microarrays Las tecnolog´ıas de alto rendimiento, o high throughput technologies, permiten medir el nivel de expresi´on de cientos de genes simult´aneamente. El uso del t´ermino microarray suele llevar a confusi´on porque suele ser utilizado indistintamente tanto para la tecnolog´ıa, como para los experimentos que se realizan mediante ella as´ı como los datos generados. B´asicamente se puede decir que es una tecnolog´ıa que permite generar conjuntos de datos que miden el nivel de expresi´on de un grupo genes bajo estudio. Figura 3.2: Plataforma de microarray. La tecnolog´ıa de microarray permite generar chips o rejillas con miles de spots o celdillas en los que se encuentran cadenas de nucle´otidos de los 28 3. Datos que se puede medir su nivel de abundancia o transcripci´on. Existen varios tipos de microarrays, de tecnolog´ıas de microarrays, de un canal o dos, etc. B´asicamente, y de manera muy general, la idea consiste en preparar cada hueco con una hebra de ADN o probe set que identificamos con un gen. En la realidad una muestra contiene miles de hebras iguales. Una vez preparada la rejilla con una serie de huecos o spots del microarray, se toma la muestra del experimento que se quiere estudiar, se ti˜ne con una sustancia y se vierte sobre dicha rejilla. Se dice que se hibrida hueco a hueco. Por complementariedad de ADN se unen las hebras de cada hueco con las de la muestra en estudio. De esta forma cada hueco tiene una concentraci´on de hebras de ADN que se puede medir seg´un la intensidad del color que se ha generado. Se procesa dicha intensidad y se le asigna un valor num´erico. Adem´as de la dificultad de tipo t´ecnico, se a˜nade un procesado en profundidad de los datos generados: correcciones de errores, procesamiento de im´agenes, etc. Todas esas t´ecnicas es lo que se conoce como An´alisis de Microarrays a bajo nivel. Se conoce como plataforma de microarray a la arquitectura concreta del experimento que se ha realizado. Hay varios tipos de plataformas: DNA microarrays,Affymetrix, etc. Cuando se usa el t´ermino experimento de microarray se refiere a los distintos estudios experimentales que se han desarrollado para una misma plataforma. Generalmente en un mismo experimento hay involucradas varios chips o rejillas. La figura 3.2 muestra un esquema de c´omo se genera una rejilla o chip de ADN. La reuni´on final de todos los chips es el resultado final del experimento y se suele denominar de manera general como datos de microarray. El conjunto de datos generado, compuesto por el nivel de expresi´on de los genes estudiados a los largo de cada chip, constituye la matriz de expresi´on. Las filas de la matriz de expresi´on son los patrones de expresi´on de los genes y las columnas los perfiles de expresi´on de cada condici´on. De esta forma, una columna completa se corresponde con todos los valores de expresi´on de los genes para un mismo chip o rejilla. Al unir todos los chips se forma una matriz en la que cada fila mide c´omo var´ıa la expresi´on de los genes. Cada elemento de la matriz de expresi´on representa el nivel de expresi´on de un gen bajo una determinada condici´on experimental1. La hip´otesis fundamental asociada a los estudios con datos de expresi´on g´enica nos dice que si dos genes tienen perfiles de expresi´on similares entonces comparten una misma funcionalidad o intervienen en un mismo proceso biol´ogico. Es decir, genes co-expresados implica genes co-regulados. De esta 1DNA Microarray Methodology - Flash Animation: http://www.bio.davidson.edu/genomics/chip/chip.html 3.3. Proceso de trabajo 29 forma la tecnolog´ıa de microarray es un herramienta muy ´util no s´olo para la investigaci´on en biolog´ıa molecular sino tambi´en en estudios cl´ınicos. 3.3. Proceso de trabajo La figura 3.3 muestra c´omo es el flujo de trabajo est´andar cuando se trabaja con datos de expresi´on obtenidos mediante la tecnolog´ıa de microarray. Una hip´otesis de trabajo genera una pregunta biol´ogica sobre, por ejemplo, un determinado proceso de respuesta de unos pacientes ante una enfermedad, etc. Se elabora un dise˜no experimental para tratar de responder a dicha pregunta, por ejemplo datos de estudio y de control, tras lo que se prepara el experimento de microarray. Se eligen una serie de placas o rejillas, se lleva a cabo la extracci´on del ARN de las muestras que se van a estudiar y se hibridan o combinan las muestras en las placas. El an´alisis de la intensidad de color que se ha producido en las im´agenes generadas permite obtener un valor num´erico para cada celdilla. Estos datos num´ericos generados deben ser sometidos a un control de calidad o de normalizaci´on, mediante los que se eliminan duplicados, se estandarizan todos los valores y se re´une toda la informaci´on. La matriz obtenida mediante el proceso anterior debe ser preprocesada para eliminar genes duplicados, realizar el tratamiento de los valores perdidos, el proceso de etiquetado o anotaci´on de los genes, etc, tras lo cual se obtiene la matriz de expresi´on sobre la que se puede llevar a cabo el an´alisis de alto nivel o de miner´ıa sobre los datos. B´asicamente se pueden realizar estudios de Miner´ıa de Datos, elaboraci´on de modelos predictivos o clasificadores, exploraci´on de los datos o aplicar t´ecnicas de clustering as´ı como estudios de anotaci´on funcional de genes cuyo objetivo es su clasificaci´on. En general tras el estudio se realiza un contraste con la informaci´on ya existente almacenada en bases de datos con informaci´on biol´ogica, como por ejemplo la ontolog´ıa de genes GO, en lo que se conoce como proceso de enriquecimiento de genes de tal manera que se puedan establecer unas conclusiones robustas a la pregunta planteada. 36 4. Biclustering experimentales que son objeto de estudio. La elecci´on de dichas muestras dependen de la hip´otesis biol´ogica que se estudia, generalmente son condiciones temporales en un ciclo celular, muestras de pacientes, etc. El inter´es radica en determinar qu´e muestras implican una funci´on biol´ogica que vendr´a determinada por un grupo de genes coexpresados. Por ello el objetivo no es agrupar genes con un comportamiento similar bajo todas las condiciones sino tan s´olo bajo un subconjunto de las mismas. De esta forma se discriminar´a y se identificar´a c´omo influyen y bajo qu´e condiciones un grupo de genes se co-expresa y cuales no. Se asume como hip´otesis que un grupo de genes co-expresados se co-regulan y por tanto comparten una misma funcionalidad biol´ogica. Por tanto, debido a la naturaleza de los datos, la t´ecnica de biclustering es m´as adecuada que el clustering tradicional que agrupa bajo todas las condiciones experimentales. Por otro lado, a diferencia con lo que ocurre en la mayor´ıa de algoritmos de clustering, las soluciones encontradas por un algoritmo de biclustering admiten solapamiento entre ellas, es decir, que un mismo gen puede pertenecer a la vez a varios grupos. Intuitivamente se puede visualizar como que las submatrices obtenidas como resultado no tienen por qu´e ser disjuntas. Desde un punto de vista biol´ogico este hecho es importante debido a que un mismo gen o grupo de genes puede actuar en varios procesos y funcionar as´ı como catalizador o inhibidor de los mismos. El solapamiento entre genes, en el sentido de un mismo gen interviniendo en varios procesos, es un hecho fundamental para el descubrimiento de biomarcadores en datos de expresi´on g´enica. En la actualidad existe una gran variedad de algoritmos de biclustering que pueden ser clasificados de multitud de formas: seg´un la t´ecnica algor´ıtmica en la que se basan, seg´un el tipo de resultados que encuentran, etc. El saber qu´e algoritmo de biclustering es el m´as adecuado en cada momento es una tarea dif´ıcil de resolver, as´ı como la elecci´on de qu´e parte de los resultados son relevantes para el problema que se estudia, etc. En funci´on de qu´e algoritmo se utilice se encontrar´a un tipo de patrones, un n´umero de soluciones muy variables en n´umero o en tama˜no, un tiempo de ejecuci´on variable, etc. En general los resultados de un algoritmo de biclustering deben de ser analizados a su vez para ver c´omo extraer informaci´on de ellos. Se requiere un conocimiento en profundidad del problema en cuesti´on que se est´e estudiando para poder sacar partido de la informaci´on que se obtiene con este tipo de t´ecnicas. Uno de las grandes preguntas abiertas es c´omo comparar distintos algoritmos y seg´un qu´e criterio. En cada art´ıculo se puede encontrar distintos tipos de an´alisis siendo el m´as aceptado el que se basa en informaci´on suministrada por expertos. En concreto por la informaci´on 4.2. Definiciones 37 almacenada en ontolog´ıas como (GO). Recientemente se han publicado trabajos en los que los algoritmos de biclustering se aplican a otro tipo de datos biol´ogicos, que fusionan informaci´on de varias fuentes de datos o que se centran en su aplicaci´on m´as que en los algoritmos en s´ı [79, 33]. 4.2. Definiciones Se define un microarray como una matriz de n´umeros reales donde las filas representan a los genes y las columnas a las condiciones experimentales. En el conjunto de datos los genes son los ejemplos o instancias y las condiciones experimentales o muestras son los atributos o clases. Se trabajar´a generalmente con conjuntos de datos no etiquetados en el sentido que no hay una etiqueta previa para cada instancia o gen. En cualquier caso al ser el biclustering una t´ecnica no supervisada el etiquetado en el conjunto de datos no es relevante. Definici´ on 1 (Microarray) Formalmente un microarray se puede definir como una 3-tupla M= (G, C, f)donde G={g1, . . . , gn}es el conjunto de genes, C={c1, . . . , cm}es el conjunto de condiciones y f:G×C−→ Res la funci´on que asocia a cada par (gi, cj)un valor real. M=   m1,1. . . m1,m . . .. . .. . . mn,1. . . mn,m    Un problema de clustering consiste en realizar una partici´on del espacio de datos siguiendo un determinado criterio, es decir, las soluciones son disjuntas entre si y su uni´on es el total. Se satisface una condici´on de homogenediad de las soluciones, o similitud entre los objetos de un mismo cluster, y de separaci´on entre ellas o distancia entre clusters. Esta doble condici´on motiva que las t´ecnicas de clustering se pueden agrupar en dos tipos: de tipo aglomerativo o de divisi´on. Partiendo de una soluci´on a la que se le agregan otras o partiendo del conjunto de datos al completo al que se establecen fronteras entre las distintas partes. En el contexto de los datos de microarray un algoritmo de clustering agrupa un conjunto de genes que tengan un comportamiento similar a lo largo de todas las condiciones de la matriz de expresi´on. 38 4. Biclustering Definici´ on 2 (Soluci´on de un problema de Clustering) Dado un microarray M, las soluciones de una t´ecnica de clustering es un conjunto S=Sn i=1 Sital que se verifica: Sn i=1 Si=M SiTSj= ø,∀i, j ∈N Aunque recientememte algunos algoritmos de cl´ustering sobre redes admiten resultados solapados, la mayor´ıa de los algoritmos de clustering no permiten solapamientos entre los resultados, es decir, en el caso de datos de expresi´on un mismo gen no puede pertenecer a dos clusters. Este hecho, junto con la imposibilidad de diferenciar qu´e subconjunto de condiciones son las relevantes para la activaci´on o no de un grupo de genes, motiva la definici´on del biclustering. Un algoritmo de biclustering agrupa un conjunto de genes que presentan un comportamiento similar a lo largo de un subconjunto determinado de condiciones de la matriz de expresi´on. Intuitivamente se puede decir que se buscan submatrices de genes coexpresados bajo unas determinadas condiciones. Se trata de realizar una b´usqueda de patrones locales seg´un un criterio preestablecido. Las soluciones o biclusters no constituyen una partici´on del espacio y admiten solapamiento, es decir, se satisface el criterio de homogeneidad de soluciones pero no el de separaci´on de las mismas. Adem´as, se admiten soluciones solapadas y no se establece una partici´on del conjunto de datos. Definici´ on 3 (Soluci´on de un problema de Biclustering) Dado un microarray M, las soluciones de una t´ecnica de biclustering es un conjunto B=Sn i=1 Bital que se verifica: Sn i=1 Bi6=M Existe i, j ∈Ntal que BiTBj6= ø Definici´ on 4 (biclusters) Dado el conjunto de soluciones de una t´ecnica de biclustering B=Sn i=1 Bi, se llama bicluster a cada elemento de dicho conjunto Bi. Dado un microarray M= (G, C, f), cada bicl´uster se define como una 3-tupla B= (I, J, f)tal que I⊆G,J⊆Cyfla funci´on que asocia a cada t´ermino del microarray un valor real.    b1,1. . . b1,j . . .. . .. . . bi,1. . . bi,j    4.2. Definiciones 39 4.2.1. NP-completitud Intuitivamente diremos que un problema es NP-completo si no se puede resolver de ninguna manera en un tiempo “razonable”, entendiendo tiempo como n´umero de pasos de computaci´on. Los problemas NP-completos son problemas que se plantean como problemas de decisi´on, que se pueden responder de manera afirmativa o negativamente, y se usan como un mecanismo para establecer la complejidad computacional del problema que se est´e estudiando. Si se puede establecer una relaci´on entre el problema de estudio y alguno de los problemas conocidos como NP-completos, se puede afirmar que no puede existir un algoritmo exacto que resuelva nuestro problema. Es decir, tan s´olo podremos construir algoritmos que den una soluci´on aproximada pero nunca la soluci´on exacta o ´unica del problema. En su formulaci´on est´andar el problema del biclustering es un problema NP-completo. Antes de su irrupci´on en el campo del an´alisis de datos de expresi´on g´enica, fue estudiado en primero lugar por Morgan y Sonquist [67], y con posterioridad por Hartigan [44] y por Mirkin [63]. Su NP-completitud se estudia a trav´es de su reducci´on a un problema cl´asico de grafos y combinatoria como es el problema del clique. La matriz de expresi´on se puede trasformar en un grafo bipartito de tal forma que por un lado los genes se transforman en una familia de nodos y por otro, las condiciones en otra familia de nodos. Las aristas que unen genes con condiciones llevan asociado un peso que ser´a el valor de expresi´on de cada elemento de la matriz. De esta forma encontrar biclusters en la matriz de expresi´on se transforma en buscar bicliques de tama˜no m´aximo en el grafo construido. Dadas dos familias de nodos, un biclique es un tipo de grafo bipartito donde cada v´ertice conecta un v´ertice de la primera familia con un v´ertice de la segunda de tal forma que se constituye un clique. Es decir, un grafo completo o aquel en el que todos los v´ertices son dos a dos adyacentes. El problema del clique es un problema cl´asico de combinatoria que se sabe que es NP-completo. Dicho problema trata de responder si es posible o no, dado un grafo y un tama˜no en concreto, encontrar un grafo completo de dicho tama˜no en el grafo. De esta forma la NP-completitud se establece reduciendo el problema del biclustering al problema del biclique. En el trabajo presentado en [4] se estudian las distintas formulaciones del problema del biclustering y se demuestra la NP-completitud a trav´es del problema del etiquetado de un grafo. Se define el problema del biclustering asociado al etiquetado de un grafo como: “dado un grafo bipartito Gy un n´umero entero k, determinar si Gtiene un conjunto de grafos bipartitos completos, o biclusters, de al menos tama˜no k” y se establce su 40 4. Biclustering NP-completitud. 4.2.2. Patrones Los distintos algoritmos de biclusterting definen heur´ısticas que buscan determinados patrones cuya definici´on trata de capturar informaci´on biologica relevante. En el trabajo presentado en [60] se establece una clasificaci´on de estos patrones, que posteriormente es ampliada en [34]. Bicl´uster con valores constantes Son aquellos biclusters que tienen todos los valores iguales, por lo que sus elementos se pueden describir de la forma bi,j =µ, siendo µel valor constante para todos sus elementos. En general este tipo de biclusters no se encuentran en los datos debido a la presencia de ruido, por lo que su definici´on se modifica de tal manera que bi,j =µ+i,j siendo en este caso µla media de los valores del bicluster y i,j el error o diferencia de cada valor respecto a la media en cada valor. Bicl´uster con valores constantes por filas o columnas Son aquellos biclusters que presentan valores constantes o bien por filas o por columnas. Cada fila, o columna, tiene un mismo valor que se repite. Si la matriz de datos se preprocesa normalizando seg´un la media de cada fila, o columna, ser´ıan biclusters con valores constantes. Cada elemento se puede representar como: bi,j =µ+αi, constante por filas, de manera aditiva. bi,j =µ×αi, constante por filas, de manera multipliativa. bi,j =µ+βj, constante por columnas, de manera aditiva. bi,j =µ×βj, constante por columnas, de manera multiplicativa. Intuitivamente son aquellos biclusters que presentan patrones planos que son paralelos unos con otros. 4.2. Definiciones 41 10 12 14 16 18 20 22 24 26 1234 Condiciones Valor de expresión Figura 4.1: Bicluster con valores coherentes. Bicl´uster con valores coherentes Son aquellos biclusters que no tienen un valor constante por fila o columna porque cada valor recibe una contribuci´on por fila y por columna. Se pueden representar como: bi,j =µ+αi+βj siendo αiel ajuste por filas y βjel ajuste por columnas. El siguiente ejemplo muestra un bicl´uster que toma como valor base 5 y recibe una modificaci´on seg´un en qu´e fila y columna se encuentre.      12 14 16 18 14 16 18 20 16 18 20 22 18 20 22 24      =     5+5+2 5+5+4 5+5+6 5+5+8 5+7+2 5+7+4 5+7+6 5+7+8 5+9+2 5+9+4 5+9+6 5+9+8 5 + 11 + 2 5 + 11 + 4 5 + 11 + 6 5 + 11 + 8      La figura 4.1 muestra la representaci´on gr´afica del bicl´uster donde cada columna representa una l´ınea del dibujo. Puede observarse claramente que son patrones paralelos aunque no planos, como ocurr´ıa en el caso anterior. Bicl´uster con evoluciones coherentes Los patrones con evoluciones coherentes son aquellos que capturan la idea de un mismo patr´on de activaci´on o inhibici´on entre todos los genes. Es decir, que todos los genes siguen una misma tendencia. Los genes crecen o decrecen a lo largo de las condiciones experimentales de la misma manera. 42 4. Biclustering Se dice que siguen un patr´on de desplazamiento si todos los genes siguen el mismo comportamiento con la misma intensidad y de escalado si lo hacen con intensidades equivalentes. Un grupo de genes de un bicl´uster sigue un patr´on de desplazamiento cuando su valor bi,j var´ıa en la adici´on de una constante βi. An´alogamente, un bicluster sigue un patr´on de escalado cuando sus valores bi,j var´ıan en la multiplicaci´on de una constante αi. Formalmente, siguen la f´ormula: bi,j =πj+βi, patr´on de desplazamiento. bi,j =πj×αi, patr´on de escalado. Un ejemplo de un bicl´uster siguiendo patrones de desplazamiento es:      30 10 5 15 33 13 5 15 40 20 15 25 50 30 25 35      =     30 + 0 10 + 0 5 + 0 15 + 0 30 + 3 10 + 3 5 + 3 15 + 3 30 + 10 10 + 10 5 + 10 15 + 10 30 + 20 10 + 20 5 + 20 15 + 20      Un ejemplo de un bicl´uster siguiendo patrones de escalado es:      48 80 16 96 24 40 8 48 18 30 6 36 12 20 4 24      =     6×8 10 ×8 2 ×8 12 ×8 6×4 10 ×4 2 ×4 12 ×4 6×3 10 ×3 2 ×3 12 ×3 6×2 10 ×2 2 ×2 12 ×2      Los biclusters anteriores se representan en las figuras 4.2 y 4.3. La primera figura (Fig. 4.2) representa el bicl´uster anterior con patrones de desplazamiento. Estos patrones muestran genes con la misma forma y la misma pendiente. Los valores iniciales son diferentes para cada gen pero la forma de todos es la misma. En la figura 4.3 se representa el bicl´uster anterior con patrones de escalado. En este caso, los genes tienen la misma forma pero las pendientes no son las mismas. Los cambios entre cada gen son m´as marcados en este segundo caso. Bicluster con evoluciones inversas coherentes Aquellas situaciones en las que un grupo de genes se activan o expresan cuando un determinado gen, o un grupo, se desactivan son interesantes desde un punto de vista biol´ogico. Este tipo de comportamientos son comunes 4.3. Principales algoritmos de Biclustering 43 0 10 20 30 40 50 60 1 2 3 4 Condiciones Valor de expresión Figura 4.2: Bicluster con patrones de desplazamiento. 0 20 40 60 80 100 120 1 2 3 4 Condiciones Valor de expresión Figura 4.3: Bicluster con patrones de escalado. en muchas rutas metab´olicas como se muestra en [83] y en [36] y se ha estudiado con detalle en el trabajo presentado en [94] donde se les llama patrones de inhibici´on-activaci´on. Se pueden considerar un caso particular de los patrones con evoluciones coherentes, en los que el factor de escalado divide en lugar de multiplicar, y el factor desplazamiento resta en lugar de sumar. La figura 4.4 muestra un bicl´uster formado por tres genes en el que uno de ellos act´ua como inverso de los otros dos. Es decir, presenta un comportamiento inverso a los otros dos. 4.3. Principales algoritmos de Biclustering Se pueden encontrar en la literatura una considerable cantidad de m´etodos de biclustering que se diferencian unos de otros seg´un la t´ecnica algor´ıtmica en la que se basan, el tipo de resultado que obtienen, los mecanismos de validaci´on que llevan a cabo, etc. La clasificaci´on de estos no es un problema sencillo pues se pueden establecer diferentes criterios de ta- 44 4. Biclustering 0 100 200 300 400 500 600 700 800 1 2 3 4 Valor de expresión Condiciones Figura 4.4: Bicluster con patrones de inhibici´on-activaci´on. xonom´ıa y en funci´on de ellos hacer varias familias. De hecho, uno de los grandes problemas en biclustering consiste en establecer cu´al es el mejor algoritmo a utilizar para un an´alisis de datos en concreto. Debido a la estructura del problema, comentada previamente, no existe una metodolog´ıa intr´ınseca de comparaci´on entre las soluciones, a diferencia de c´omo si ocurre en Clustering: distancias entre grupos, estructura de la partici´on, etc. Las comparativas que se establecen en la mayor´ıa de art´ıculos se basan en conocimiento experto del an´alisis de datos realizado, siendo el an´alisis de enriquecimiento biol´ogico la metodolog´ıa de comparaci´on m´as aceptada. Por todo ello, a la hora de elegir qu´e algoritmo utilizar tiene m´as importancia la disponibilidad del software, o el tiempo de ejecuci´on, que otro tipo de consideraciones m´as formales. 4.3.1. Algoritmos cl´asicos Bajo la denominaci´on Algoritmos Cl´asicos enmarcamos una serie de algoritmos de biclustering que suelen ser utilizados en las comparativas de los art´ıculos. Estos algoritmos son frecuentemente usados debido a que fueron establecidos por su uso como marco de trabajo y sobre todo a la f´acil disponibilidad de su c´odigo. El algoritmo de Cheng y Church (ChCh) [24] es considerado como el trabajo fundacional dado que introduce la necesidad de la b´usqueda de submatrices en datos de expresi´on g´enica para la extracci´on de informaci´on biol´ogica relevante. As´ı mismo, muestra la no adecuaci´on a estos datos del Clustering tradicional. Es un algoritmo voraz determin´ıstico que busca aquellos biclusters que minimicen el valor de una medida llamada Mean Squared Residue (MSR), o Residuo Cuadr´atico Medio (eq. 4.1). El proceso comienza con la matriz completa del microarray quitando filas y columnas de forma 4.3. Principales algoritmos de Biclustering 45 que se genera un bicluster y se eval´ua el valor de su residuo. Si este valor es menor que un cierto umbral establecido como par´ametro entonces se a˜naden aquellas filas y columnas que no aumenten dicho valor. Una vez encontrado el bicluster, los valores que encuentra son cambiados en el microarray por valores aleatorios y se repite el proceso de b´usqueda tantas veces como biclusters se desee encontrar. Se debe introducir como par´ametro de entrada tanto el umbral de b´usqueda del residuo como el n´umero de biclusters que se desea como resultado. Si IyJson el conjunto de filas (genes) y columnas (condiciones) de un bicluster, la medida MSR se define de la siguiente manera: MSR =1 |I||J|X i∈I,j∈J (aij −aiJ −aIj +aIJ )2(4.1) donde aij es el valor del elemento que ocupa la fila iy la columna j (valor de expresi´on del gen i bajo la condici´on j), aiJ es la media de todos los elementos que ocupan la fila i,aIj es la media de los que ocupan la columna j y aIJ es la media del bicluster al completo. El algoritmo FLOC [91] es una mejora que permite obtener los biclusters de manera simult´anea durante el proceso y que permite manejar los valores perdidos o ausentes en el microarray. El algoritmo ISA [12], Iterative Signature Algorithm, es un algoritmo voraz no determinista que busca biclusters que verifiquen que el valor medio de cada columna est´e por debajo de un cierto umbral establecido para las columnas y, an´alogamente, el valor medio de cada fila est´e por debajo de un umbral establecido para las filas. El proceso parte de un bicluster construido aleatoriamente que act´ua como semilla y se a˜naden y quitan filas y columnas hasta que se alcanza convergencia. El proceso se repite con distintas semillas y de esta forma se obtienen distintos biclusters. El algoritmo OPSM [11], Order-preservering submatrix problem, es un algoritmo voraz determinista que busca biclusters que preservan una determinada ordenaci´on entre filas y columnas. La idea subyacente en el modelo de ordenaci´on es encontrar submatrices cuyas filas sigan una misma tendencia de crecimiento o decrecimiento y por lo tanto conserven la ordenaci´on. Se puede probar que dicho modelo captura los patrones m´as usuales como valores constantes, de desplazamiento o de escalado. Se introduce as´ı mismo una correcci´on basada en una probabilidad para relajar las condiciones de dicho modelo y contemplar peque˜nas variaciones, posibles errores en los datos, etc. El algoritmo trabaja iterativamente construyendo biclusters parciales los cuales se van incrementando en tama˜no. S´olo se conservan los mejores biclusters construidos en cada paso de manera que la repetici´on del proceso 52 4. Biclustering umbral. Los trabajos presentados en [43] y [39] siguen de manera independiente un enfoque parecido. Se caracterizan los principales patrones como hiperplanos en espacios de alta dimensionalidad. Es decir, se considera el espacio generado por todas las condiciones y se trata de buscar variedades lineales en ese espacio. Este enfoque de tipo geom´etrico conlleva el uso de t´ecnicas cl´asicas generalmente utilizadas en otro tipo de campos, como por ejemplo las t´ecnicas de procesamiento de im´agenes, aplicando de esta forma el algoritmo de detecci´on de l´ıneas de la transformada de Hough. El art´ıculo presentado en [43] es el primero que usa por primera vez este enfoque, sin embargo [39] usando ideas parecidas presenta un estudio experimental m´as riguroso y que sigue un enfoque m´as cercano al problema biol´ogico. Algunos algoritmos de biclustering requieren una discretizaci´on de los datos, siendo este paso de vital importancia seg´un qu´e tipo de resultados se deseen obtener. El algoritmo de BiMAX presentado en [77] es el principal representante de este grupo de algoritmos. Este algoritmo se encuentra disponible entre los algoritmos de la herramienta software presentada en [10], lo que suele considerarse referente entre aquellos algoritmos que requieren discretizaci´on previa. Requiere un alto coste computacional de c´alculo y otros algoritmos como [81] o [51] trabajan tambi´en con datos discretos y mejoran su coste computacional. Los algoritmos eCCC-biclustering yCCC-biclustering, presentados en los art´ıculos [58] y [59] respectivamente, trabajan con datos discretos pero se especializan en datos de expresi´on temporales. Es decir, las columnas o condiciones de la matriz de expresi´on deben respetar el orden en el que se encuentran puesto que representan datos de tipo temporal. En estos art´ıculos por ejemplo los datos son momentos del ciclo celular de la levadura. De esta manera la complejidad computacional del problema del biclustering se reduce pasando a ser un problema computacionalmente tratable, no es NP-completo. Gracias a la discretizaci´on de los datos, y la restricci´on de columnas continuas en los resultados, se pueden aplicar t´ecnicas de tratamientos de cadenas. Ambos algoritmos se basan en el conocido algoritmo de Ukonnen de b´usquedas de cadenas similares que se aplica de manera local iterativamente. La diferencia entre ambos algoritmos, presentados por los mismos autores, consiste en la tolerancia a errores en los patrones encontrados. Se considera positivo admitir ciertos errores en la identificaci´on de las cadenas y de esta manera se pueden corregir errores cometidos en el paso de discretizaci´on. 4.4. Metodolog´ıa de comparaci´on y validaci´on 53 4.4. Metodolog´ıa de comparaci´on y validaci´on Debido a la gran cantidad de algoritmos de biclustering que se pueden encontrar estos ´ultimos a˜nos en la literatura, es de gran importancia abordar el problema de la comparaci´on entre los mismos y los mecanismos para determinar qu´e algoritmo es el m´as adecuado seg´un la naturaleza de los datos que se manejen. Los principales surveys presentes en la literatura [60, 86, 20] no abordan el estudio comparativo entre los distintos algoritmos sino tan s´olo su clasificaci´on. Se pueden clasificar los distintos algoritmos seg´un la t´ecnica de b´usqueda y seg´un los patrones que encuentra. El problema del biclustering es un problema de aprendizaje no supervisado, por lo tanto la manera de determinar si un algoritmo obtiene buenos resultados consiste en recurrir a conocimiento externo al problema. Por lo tanto, se debe tener un conocimiento profundo de los datos de estudio y se trata de determinar la calidad de los resultados obtenidos. El art´ıculo [77] plantea una comparaci´on entre algoritmos en funci´on del porcentaje de biclusters enriquecidos que cada algoritmo devuelva. Se dice que un bicl´uster est´a enriquecido si es estad´ısticamente significativo respecto a un conjunto de genes de referencia. Se toma como referencia la ontolog´ıa de genes GO [5] y se trata de determinar si el grupo de genes de un bicl´uster est´a presente en un t´ermino de dicha ontolog´ıa. Para ello se realiza un contraste de hip´otesis, normalmente el test de Fisher, que como se repite respecto a todos los t´erminos GO presentes en las anotaciones se lleva a cabo un contraste m´ultiple de hip´otesis. Este test m´ultiple se debe corregir mediante otro proceso estad´ıstico, normalmente el m´etodo de Bonferroni. Como cada algoritmo obtiene un n´umero distinto de resultados la comparativa se establece en funci´on del porcentaje de biclusters enriquecidos. Hay que tener en cuenta que estos estudios experimentales suelen presentar problemas de varios tipos: c´omo son los ficheros de anotaciones de t´erminos GO utilizados, como se determina que un grupo de genes est´e presente o no en un t´ermino, de nomenclatura de genes, etc. En biclustering es m´as complicado que en clustering la definici´on de unas medidas de validaci´on en funci´on de la estructura de los resultados. T´engase en cuenta que se puede medir la homogeneidad de los resultados pero no la separaci´on de los mismos dado que no la cumplen. Los criterios de homogeneidad se establecen en funci´on de una medida de tipo estad´ıstico, generalmente el residuo o la correlaci´on, y se analizan los resultados de esta manera. De manera alternativa podemos encontrar en muchos art´ıculos un m´etodo de comparaci´on entre algoritmos basados en datos sint´eticos [32]. Se genera una matriz de manera artificial y se almacena dentro de ella un 54 4. Biclustering conjunto de biclusters que se estimen buenos. Se estudian y se comparan los distintos algoritmos entre s´ı seg´un su capacidad de detectar estos biclusters. Se suele utilizar el ´ındice de Jaccard [32]. El problema que presenta un enfoque basado en datos sint´eticos es que la distribuci´on de los datos debe ajustarse lo m´aximo a la realidad. Es decir, no pueden estar resaltados los biclusters que se buscan debido a que los valores que los rodean son excesivamente diferentes en rango, tendencia, etc. De esta forma se dar´ıa un sobreajuste entre los resultados a buscar y el mecanismo de b´usqueda del algoritmo y la validaci´on no ser´ıa realista. Por otro lado, determinar qu´e significa que un bicl´uster sea o no bueno introduce tambi´en de manera inevitable un sobreajuste en la validaci´on. Algunos trabajos establecen la comparativa entre algoritmos abriendo el espectro de la validaci´on de los genes [52], trabajando por ejemplo con redes de prote´ınas y no s´olo con GO, o utilizando ´ındices internos de car´acter descriptivo y t´ecnicas de visualizaci´on de datos [82]. 4.5. Nuevas tendencias Existen gran cantidad de algoritmos de biclustering como hemos podido ver en este cap´ıtulo. La comparaci´on entre ellos, y determinar qu´e algoritmo ofrece un mejor rendimiento para unos datos y un problema en concreto, no es una tarea f´acil. De hecho se puede considerar todav´ıa un problema abierto en este campo. Actualmente se considera que son m´as interesantes las aplicaciones, e integraci´on del biclustering dentro de estudios m´as generales, que el desarrollo de un algoritmo en concreto que compita con los dem´as en tiempo, precisi´on o sensibilidad. No obstante el desarrollo de nuevas medidas de calidad, para una mejor detecci´on de los patrones que se buscan, y el desarrollo de algoritmos, sigue siendo campos de investigaci´on relevantes. As´ı por ejemplo hay estudios sobre el funcionamiento de nuevas medidas, como la informaci´on mutua propia de la teor´ıa de la informaci´on, en el problema de la detecci´on de biclusters [42]. Otros trabajos, como [46], mejoran t´ecnicas cl´asicas de biclustering mejorando su tolerancia a ruido, escabilidad o flexibilidad. En este caso se mejora el algoritmo de OPSM mediante t´ecnicas de tratamiento de local de cadenas. Se conoce como tuber´ıas de t´ecnicas o pipelines al encadenamiento de distintas t´ecnicas para la resoluci´on de un problema. De esta manera un algoritmo de biclustering se convierte en una pieza que se integra en un esquema algor´ıtmico m´as general. Por ejemplo, en [22] se aborda un problema de clasificaci´on en el que juega un papel relevante el biclustering. Se define el concepto de metabicl´uster que se utiliza como pieza fundamental en la 4.5. Nuevas tendencias 55 clasificaci´on de datos. Este trabajo es un ejemplo interesante de aplicaci´on de biclustering en el marco de un problema general de desarrollo de modelos de prognosis de enfermedades. As´ı mismo, en [56] el biclustering se enmarca en un problema de an´alisis de datos de espectrometr´ıa de masas. En [47] se integra el biclustering en un marco de descubrimiento de m´odulos reguladores en el que se utilizan datos de expresi´on g´enica y de secuenciaci´on, junto con datos auxiliares de tipo filogen´eticos. En [26] se utiliza el biclustering para mejorar un m´etodo de detecci´on de subredes de prote´ınas que sirven como marcadores para desarrollar modelos de prognosis en c´ancer. En general, se debe tener en cuenta que el problema de detecci´on de m´odulos de una red es un problema de b´usqueda que utiliza ideas similares a los algoritmos de biclustering. En el marco de las redes de genes interesa m´odulos que no sean disjuntos entre s´ı y, por otro lado, el inter´es radica en la b´usqueda de patrones locales m´as que en la descripci´on de la red en su conjunto [90]. Estas ideas constituyen una oportunidad de trasladar las ideas propias del biclustering al problema de b´usqueda de m´odulos de una red con el objetivo de definir nuevos marcadores. An´alogamente, las ideas propias del biclustering se pueden trasladar al estudio de otros tipos de datos como por ejemplo el estudio de datos de microRNA [73]. Se trata de asociar cadenas de microRNAs con sus genes objetivos, o target genes, por lo que tras un procesamiento inicial de los datos de entrada se puede generar una matriz que enfrente microRNA y genes candidatos, teniendo como objetivo agrupar cadenas de microRNAs con comportamiento similar para un grupo de genes. Finalmente, la integraci´on entre distintas fuentes de datos es uno de las tendencias actuales en Bioinform´atica [7]. La proliferaci´on de repositorios p´ublicos de f´acil acceso, as´ı como proyectos como GO, KEGG, etc, facilitan la fusi´on de distintas fuentes de datos. Siguiendo estas ideas se puede realizar el estudio de c´omo afectan a los algoritmos de biclustering conocidos la integraci´on de informaci´on adicional proveniente de otro tipo de datos. De esta manera se consigue introducir un sesgo en la b´usqueda y se utiliza informaci´on extra que ayude a encontrar los biclusters. 56 4. Biclustering Cap´ıtulo 5 Apuntes sobre integraci´on de informaci´on biol´ogica Es misi´on de la ciencia traspasar las fronteras del conocimiento, indagar m´as all´a y ampliar los l´ımites del saber humano, a˜nadiendo m´as datos que nos permitan comprender el complejo mundo en que estamos inmersos. Explorando los genes. Del Big-Bang a la nueva Biolog´ıa. Nicol´as Jouve (p´ag. 265). 5.1. Introducci´on En el contexto del biclustering se suelen usar repostorios biol´ogicos p´ublicos como the Gene Ontology project (GO) o Kyoto Encyclopedia of Genes and Genomes (KEGG) para tareas de validaci´on y comparaci´on entre los resultados de distintos algoritmos. En el caso de GO, por ejemplo, se suele usar el enriquecimiento de genes como criterio para elaborar rankings de comparaci´on entre algoritmos. Dados los biclusters obtenidos por cada algoritmo, se estudia el porcentaje de ellos que son estad´ısticamente significativos en alguno de los t´erminos de la ontolog´ıa. Es decir, si existe un subgrupo de genes de ese bicl´uster que est´an relacionados con alg´un t´ermino GO. Seg´un ese porcentaje se establce el ranking entre los resultados obtenidos por los distintos algoritmos [77]. GO es una ontolog´ıa con una estructura jer´arquica con tres ramas o dominios: BP o procesos biol´ogicos, CC o componentes celulares y MF o funciones moleculares. Cada t´ermino de la ontolog´ıa tiene asociado un grupo de genes, que son anotados seg´un la informaci´on obtenida experimentalmente, mediante an´alisis inform´aticos, etc. Los t´erminos m´as bajos en la jerarqu´ıa son m´as espec´ıficos que los m´as altos, que engloban 57 58 5. Integraci´on de informaci´on biol´ogica a mayor n´umero de genes bajo una descripci´on m´as general. Los ficheros de anotaciones de genes relacionan t´erminos de GO con el conjunto de genes que est´an relacionados o anotados para dicho t´ermino. Este tipo de ficheros son los que generalmente se usan en las labores de validaci´on y comparaci´on de los resultados de los algoritmos de biclustering. Toda la informaci´on almacenada en estos repositorios se utiliza por lo tanto a posteriori del proceso de b´usqueda propio del biclustering. Por otro lado, en biclustering, al igual que en el resto de t´ecnicas de an´alisis de datos de expresi´on g´enica, se asume que si un grupo de genes est´an co-expresados entonces comparten una determinada funcionalidad com´un. Esta hip´otesis de partida ha sido criticada por algunos autores que ponen en cuesti´on la completitud de los datos. Se argumenta que pueden existir grupos de genes que se co-expresen en simult´aneo, para una misma condici´on, como resultado de procesos paralelos pero independientes y no por ello tienen por qu´e compartir una misma funcionalidad o proceso biol´ogico [18]. Es decir, la informaci´on que se pueda extraer de los datos de expresi´on nos da una gu´ıa de investigaci´on, o una pista, pero no es concluyente. En otras palabras, genes co-expresados pueden ser genes co-regulados pero se necesita informaci´on extra para llegar a la conclusi´on. Este tipo de ideas motivan el uso de informaci´on complementaria para un an´alisis m´as profundo de los datos de expresi´on g´enica, no ya como herramienta de validaci´on a posteriori, sino insertando toda la informaci´on en las mismas t´ecnicas o algoritmos. En general la integraci´on de la informaci´on biol´ogica proviniente de distintas fuentes de datos es uno de los retos y l´ıneas de trabajo m´as prometedoras actualmente en Bioinform´atica [7]. 5.2. Integraci´on de informaci´on biol´ogica En el campo del biclustering no se ha iniciado el desarrollo de algoritmos h´ıbridos que integren informaci´on a priori. Sin embargo, en clustering se pueden encontrar ya algunas propuestas que integran informaci´on biol´ogica en el proceso de b´usqueda. Por ejemplo, el algoritmo presentado en [87] se basa en el algoritmo de clustering del K-means e integra informaci´on de GO mediante fichero de anotaciones directa. Se define una distancia que se basa en la idea de co-expresi´on y similitud funcional entre los genes. En clasificaci´on, por ejemplo, el algoritmo presentado en [8], que clasifica grupos de genes, integra una medida basada en GO como parte del flujo de trabajo para llevar a cabo dicha clasificaci´on. En concreto se usa la correlaci´on de Pearson para medir la co-expresi´on entre los genes y, por otro lado la medida basada en GO para definir un concepto de distancia. Dicha distancia se usa 5.2. Integraci´on de informaci´on biol´ogica 59 para construir grupos de genes para los que se elabora un ranking de genes candidatos. En el campo de la selecci´on de atributos el m´etodo presentado en [57] integra informaci´on proveniente de KEGG en lugar de GO. El algoritmo es un algoritmo evolutivo que gracias a la informaci´on de KEGG mejora los resultados de los algoritmos cl´asicos de selecci´on de atributos. En general se pueden encontrar otros trabajos que integran informaci´on proveniente de distintas fuentes de datos, no s´olo GO o KEGG, para mejorar el rendimiento. Por ejemplo, en el trabajo presentado en [55] se fusiona informaci´on de la interacci´on de redes de prote´ınas, datos de tipo gen´omico e informaci´on extra´ıda de la literatura (literature mining) de manera simult´anea. El algoritmo COALESCE [47] busca m´odulos de regulaci´on de genes usando datos de expresi´on g´enica junto con datos de secuenciaci´on de ADN. El algoritmo propuesto en [26] usa redes de interacci´on de prote´ınas y datos de expresi´on g´enica para descubrir biomarcadores relacionados con diversos tipos de c´ancer. Dichos biomarcadores son grupos de genes que adem´as de estar co-expresados tienen una alta conectividad en las redes de prote´ınas. M´as recientemente, y en el campo del biclustering, aunque aplicado a datos de microRNA en lugar de a datos de co-expresi´on, el algoritmo presentado en [73] usa en uno de sus pasos una medida basada en GO para elaborar un ranking entre los biclusters que encuentra. 5.2.1. Medidas de similutud funcional entre genes basadas en GO Se pueden definir medidas de distancias entre genes seg´un la informaci´on sobre dichos genes almacenada en GO. Existen multitud de medidas de similitud sem´antica para comparar t´erminos de GO donde los genes est´an anotados. Estas medidas no miden la distancia entre dos genes sino entre los propios t´erminos de la ontolog´ıa y a trav´es de estos se puede establecer la medida entre los genes. Estas medidas se pueden clasificar b´asicamente en dos grupos: medidas basadas en la topolog´ıa de la ontolog´ıa, o edge-based measures, y medidas basadas en la informaci´on almacenada dicha ontolog´ıa, o las information content (IC)-based measures. El primer grupo asume que la especifidad de un t´ermino se puede inferir directamente de su profundidad en el grafo de GO, se basa en la topolog´ıa del grafo de GO. El segundo grupo por otro lado se basa en la frecuencia de aparici´on de un t´ermino en dicho grafo m´as que en el lugar en el que se encuentra. En general un mismo gen suele estar anotado en m´as de un t´ermino GO por lo que, si el objetivo es establecer distancias entre genes, es m´as adecuado usar medidas de similitud que comparen grupos de t´erminos GO 60 5. Integraci´on de informaci´on biol´ogica en lugar de t´erminos individuales entre s´ı. En la referencia [72] se presenta una comparaci´on entre estas medidas y se concluye que SimGIC es la que obtiene mejor resultado. Esta medida se usa para computar la similitud entre dos genes usando el contenido de informaci´on (information content o IC) asociado con cada t´ermino GO asociado a cada gen. Para poder computar el IC se necesita no s´olo los ficheros de anotaciones extra´ıdos de GO sino tambi´en su estructura de grafo (que se puede obtener como un fichero con la extensi´on .obo). Otras medidas de similitud se basan en la construcci´on de matrices binarias que recogen la estructura de GO. Estas matrices tiene los genes como filas y los t´erminos GO como columnas y cada elemento indica si un gen est´a o no anotado en un t´ermino GO. Estas medidas se inspiran en ideas propias de teor´ıa de la informaci´on. La medida presentada en [65] se puede clasificar como una medida de similitud de sem´antica pero no necesita ni un preprocesamiento previo, para construir una matriz, ni un fichero diferente del fichero de anotaciones con la estructura del grafo de GO. Esta medida se basa en el solapamiento entre los t´erminos GO asociados a dos genes y de esa forma se mide la similitud entre ellos. Para esta medida es esencial la manera en la que el fichero de anotaciones, que relaciona genes y sus t´erminos GO asociados, est´e construido. Cuando el fichero de anotaciones tiene en cuenta un t´ermino y todos sus t´erminos padre en la ontolog´ıa, se consigue reflejar la estructura jer´arquica de la ontolog´ıa. Parte III Propuestas 61 68 6. B´usqueda Dispersa y permite leer rigurosamente c´omo funciona el proceso. Se puede observar con claridad que el algoritmo es un esquema de b´usqueda secuencial de biclusters en el sentido que un mismo proceso se repite un n´umero de veces, una por cada bicluster que se quiera encontrar. El bucle general, l´ınea 2 a la 22, se repite tantas veces como indique el par´ametro de entrada n´umero de biclusters buscados. Entre las l´ıneas 8 y 18 se describe el bucle principal del esquema de b´usqueda dispersa, que se encarga de reconstruir el conjunto de referencia y que anteriormente hemos comentado que en los esquemas cl´asicos se suele repetir veinte veces. Dentro de este bucle se encuentra el bucle de estabilidad, l´ıneas 9 a la 14, en el que evoluciona el conjunto de referencia hasta que alcanza la estabilidad, como hemos descrito anteriormente. Se puede observar en las l´ıneas 19 y 20 c´omo se almacena en el conjunto de resultados el mejor bicluster del conjunto de referencia resultante del esquema de b´usqueda dispersa (l´ınea 3 a la 18). Es importante observar que la poblaci´on inicial tan s´olo act´ua como arranque del proceso pero tan s´olo sirve como apoyo del mismo, l´ıneas 3 a la 6. La intensificaci´on de la b´usqueda se consigue en el bucle de estabilidad, l´ıneas 9 a la 14, mientras que la diversificaci´on de la misma se logra principalmente cuando se construye o reconstruye el conjunto de referencia, l´ıneas 5 y 15. Las l´ıneas 6 y 16 son fundamentales para que la poblaci´on inicial se vaya actualizando y aporte informaci´on nueva en los sucesivos pasos del proceso. 6.3. B´usqueda Dispersa: m´etodos y detalles Describimos a continuaci´on los diferentes m´etodos que hemos descrito tanto en la figura 6.1 como en el pseudoc´odigo del algoritmo con m´as detalle (ver Algoritmo 1). 6.4. Codificaci´on de las soluciones Se puede describir un bicluster enumerando los genes o filas de la matriz del microarray que lo constituyen junto con sus columnas o condiciones correspondientes. Con tan s´olo esa descripci´on se puede construir dicho microarray. Siguiendo esta idea, y bas´andonos en trabajos previos, se ha codificado cada bicluster como una cadena de ceros y unos. Con m´as detalle, si un bicluster Bes una matriz Mcompuesta de n≤Nfilas o genes y l≤Lcolumnas o condiciones, se codifica como una cadena binaria de tama˜no N+Ldonde los Nprimeros bits codifican los genes y los Lsegundos las condiciones. La figura 6.2 muestra un peque˜no ejemplo. 6.4. Codificaci´on de las soluciones 69 Matriz de expresión codificación del bicluster matriz de expresión del bicluster bicluster Figura 6.2: Microarray y bicluster {G3,G5,G6—C2,C3}con su codificaci´on. 6.4.1. M´etodo de diversificaci´on El m´etodo de la diversificaci´on se encarga de la construcci´on de la poblaci´on inicial de las soluciones de forma que estas sean lo m´as dispersas o diferentes entre s´ı. De esta manera la poblaci´on inicial de soluciones consigue describir mejor el espacio de soluciones que un mero conjunto de soluciones aleatorias. Se trata de trabajar soluciones que describan de la mejor manera posible el espacio de soluciones. Se ha seguido un m´etodo para generar biclusters lo m´as dispersos posibles entre s´ı, es decir, lo m´as lejanos seg´un el concepto de distancia utilizado. Debido a la codificaci´on binaria de soluciones, se emplea la distancia Hamming que mide el grado de similitud entre cadenas de 0s y 1s. Dicho m´etodo se basa en la generaci´on de cadenas de ceros y unos lo m´as diversas, o diferentes entre si, descrito en [61]. Este m´etodo se considerada cl´asico en los esquemas basados en b´usquedas dispersas que utilizan codificaciones binarias. Se generan por separado la subcadena para los genes y la subcadena para las condiciones. Se toma como semilla una cadena binaria xde ceros y unos en la que xi, con i= 1, . . . , n ynel n´umero de bits, representa el valor o bit que hay en cada posici´on. Se genera una nueva cadena binaria x0de tal manera que cada nuevo bit es generado mediante la regla: x0 1+kh = 1 −x1+kh for k= 0,1,2,3,...,bn/hc(6.1) siendo bn/hcel entero m´as grande mayor o igual que n/h yhes el entero menor que n/5, los valores que se salen del rango simplemente no provocan ning´un nuevo bit a tener en cuenta. El resto de bits de la cadena de x0 70 6. B´usqueda Dispersa permanecen iguales al valor que tuvieran en x. Despu´es de haberse generado todas las posibles soluciones, si hacen falta m´as soluciones basta repetir el proceso con una nueva semilla. Se suele tomar como nueva semilla la ´ultima cadena generada con anterioridad. Es importante tener en cuenta que la codificaci´on elegida para el problema lleva asociada impl´ıcitamente la definici´on de una m´etrica. Esta m´etrica o distancia definir´a la topolog´ıa del espacio de soluciones o de b´usqueda. As´ı el significado de soluciones dispersas o alejadas entre s´ı est´a ligado a esta distancia. Como hemos comentado anteriormente, se ha considerado como distancia la distancia Hamming que se define como el n´umero de cambios necesarios para transformar una cadena de bits en otra. Es decir, dadas dos cadenas binarias, la distancia Hammning entre ambas indica lo parecidas o distintas que son entre s´ı. Por ejemplo, la distancia Hamming entre 1011101 y 1001001 es 2 pues con tan s´olo dos cambios de bits se puede generar una teniendo en cuenta la otra. 6.5. Construcci´on y reconstrucci´on del conjunto de referencia El conjunto de referencia lo constituye un peque˜no grupo de soluciones cuya evoluci´on ser´a la gu´ıa del proceso en la b´usqueda del ´optimo. Estas soluciones tienen que ser lo mejor posible tanto desde punto de vista de la intensificaci´on de la b´usqueda como de la diversidad de la misma. Se entiende como intensificaci´on en el proceso de b´usqueda como la convergencia hacia el ´optimo, de manera que el proceso se acelera cuando se acerca a la soluci´on. Se entiende diversidad como la capacidad del proceso de explorar la mayor parte de regiones del espacio de b´usqueda. Ambas deben mantener un equilibrio porque por un lado el proceso debe acercarse al ´optimo con mayor rapidez pero sin dejar de explorar otras regiones del espacio en las que pudieran encontrase mejores soluciones. Un proceso evolutivo desequilibrado puede o bien no encontrar soluciones ´optimas, porque es demasiado diverso, o bien caer en ´optimos locales porque encuentra la mejor soluci´on posible pero restringida a una regi´on muy limitada del espacio de b´usqueda. Cuando se construye o se reconstruye el conjunto de referencia se tienen en cuenta dos grupos de soluciones: las que aportan intensificaci´on a la b´usqueda y las que aportan diversidad. La primera vez que se construye el conjunto de referencia, l´ınea 5 del algoritmo ??, se introduce un primer grupo de soluciones que son las mejores 6.6. M´etodo de generaci´on de nuevas soluciones 71 de la poblaci´on inicial, desde el punto de vista de su peso, y un segundo grupo, elegidas de la poblaci´on inicial, que son lo m´as dispersas posible respecto a las primeras. Es decir, si el tama˜no del conjunto de referencia es 10 (tama˜no est´andar en los esquemas cl´asicos de b´usqueda dispersa) se eligen las 5 mejores de la poblaci´on y aquellas 5 que sean lo m´as diferentes, dispersas o lejanas de la poblaci´on, en el sentido de la distancia Hamming. Las siguientes veces que se reconstruye el conjunto de referencia se realiza un proceso an´alogo, l´ınea 15 del algoritmo 1. Se consideran para el nuevo conjunto de referencia las mejores soluciones del conjunto de referencia previo, si el tama˜no es el est´andar se eligen las 5 mejores soluciones de las 10 que hay, y por otro lado, se consideran las 5 soluciones m´as dispersas de la poblaci´on inicial respecto de las previamente consideradas. Es importante tener en cuenta que cuando se eligen las soluciones de la poblaci´on inicial deben eliminarse de la misma. Caso contrario el proceso no funcionar´ıa correctamente desde el punto de vista de la diversidad. 6.6. M´etodo de generaci´on de nuevas soluciones padre 1 1 01101 1 0 11100 0 1 11100 1 hijo padre 2 máscara de cruce 1 00100 1 Figura 6.3: Operador de cruce uniforme. A partir de las soluciones existentes en el conjunto de referencia, se pueden definir distintos mecanismos de generaci´on de nuevas soluciones, o m´etodos de generaci´on de nuevas soluciones, seg´un c´omo sea la codificaci´on de las soluciones [61]. Debido a la codificaci´on binaria de los biclusters, y a los estudios previos realizados, utilizamos el operador de cruce uniforme generalmente utilizado en los algoritmos gen´eticos. Se pueden utilizar otros operadores m´as sofisticados que aceleren el proceso, de hecho las principales mejoras en los esquemas de b´usqueda dispersa tienen lugar en el refinamiento en la generaci´on de nuevas soluciones. 72 6. B´usqueda Dispersa Dadas dos soluciones, se genera una nueva soluci´on mediante el operador de cruce uniforme. Se generan todas las posibles parejas teniendo en cuenta las soluciones existentes en el conjunto de referencia. Por lo tanto, se generan S∗(S−1)/2 nuevas soluciones siendo Sel tama˜no del conjunto de referencia. El operador de cruce uniforme genera aleatoriamente una m´ascara y la soluci´on generada se compone de los valores de una de las soluciones originales cuando hay un 1 en la m´ascara y de la otra soluci´on cuando hay un 0, v´ease la figura 6.3. 6.7. M´etodo de combinaci´on y actualizaci´on del conjunto de referencia Se combinan todas las soluciones generando de esta maneras nuevas soluciones que son mejoradas mediante el m´etodo de la mejora. Entre las soluciones existentes en el conjunto de referencia y todas las generadas se eligen las mejores soluciones seg´un el valor de la funci´on objetivo. De esta manera se actualiza el conjunto de referencia y se intensifica la b´usqueda. Si el conjunto de referencia generado difiere del anterior, es decir, el m´etodo de la combinaci´on ha sido capaz de generar mejores soluciones, entonces el proceso contin´ua, caso contrario se alcanza la estabilidad del conjunto de referencia y contin´ua una nueva iteraci´on de la b´usqueda dispersa. 6.8. M´etodo de la mejora El m´etodo de la mejora consiste en una b´usqueda local que dada una soluci´on genera una nueva soluci´on con un mejor valor de la funci´on objetivo. De esta manera se acelera la convergencia del proceso, ya que se trabajan con las mejores soluciones posibles del espacio durante el proceso de b´usqueda. La b´usqueda local puede depender o no de la sem´antica de la funci´on objetivo que se utilice en concreto. Si se liga a la funci´on objetivo, se puede asegurar un funcionamiento r´apido y efectivo en todos los casos. Se utiliza el conocimiento concreto del problema para alcanzar un ´optimo local cercano a la funci´on con la que se trabaje. Otra opci´on consiste en la definici´on de una b´usqueda local “ciega” mediante una serie de permutaciones y, de esta forma, se desliga la funci´on objetivo del problema en cuesti´on del proceso completo de b´usqueda. En cualquier caso es necesario el m´etodo de la mejora como acelerador de la convergencia y garant´ıa del correcto funcionamiento del proceso completo. Cap´ıtulo 7 Criterio de b´usqueda basado en correlaci´on Recuerdo una noche en que regres´e tarde de Londres. En aquellos tiempos, como medida de econom´ıa, apagaban a medianoche el alumbrado urbano. Contemple el firmamento, atravesado por la V´ıa L´actea, como nunca lo hab´ıa visto. No habr´a faroles en mi isla desierta, as´ı que ver´e bien las estrellas. Agujeros negros y peque˜nos universos y otros ensayos. Stephen Hawking (p´ag. 113) 7.1. Introducci´on En este cap´ıtulo se presentan dos propuestas de un algoritmo de biclustering basado en un esquema de b´usqueda dispersa y cuya funci´on objetivo est´a basada en el uso de correlaciones lineales. Se utiliza una medida de correlaci´on lineal como medida de calidad para evaluar genes co-expresados y se integra como parte de la funci´on de peso de la metaheur´ıstica. Ambas propuestas usan el esquema de b´usqueda dispersa expuesto en el cap´ıtulo anterior y difieren, b´asicamente, en la capacidad de encontrar o no patrones de activaci´on-inhibici´on. Dichos patrones se corresponden con grupos de genes correlacionados negativamente, es decir, genes que presentan una misma tendencia de crecimiento-decrecimiento. 7.2. Propuesta SSCorr: correlaciones lineales I Veamos c´omo se define la funci´on objetivo y el m´etodo de la mejora de la primera propuesta de biclustering basado en correlaciones lineales usando 73 74 7. B´usqueda basada en correlaci´on un esquema de b´usqueda dispersa. 7.2.1. Evaluaci´on de biclusters: funci´on objetivo Dos genes muestran entre s´ı un patr´on de desplazamiento y escalado si verifican la siguiente expresi´on: gY=αgX+β α, β ∈R(7.1) Es decir, ambos genes dependen linealmente el uno del otro. Se puede elegir su coeficiente de correlaci´on lineal para medir su grado de interdependencia. El coeficiente de correlaci´on entre dos variables XyYse define como: ρ(X, Y ) = cov(X, Y ) σXσY =Pn i(xi−x)(yi−y) nσXσY (7.2) donde cov(X, Y ) es la covarianza entre las variables XeY,xyyson la media de los valores de dichas variables y σXyσYsus desviaciones est´andar. Dado un bicluster Bcompuesto por Ngenes, B= [g1, . . . , gN], la correlaci´on media de B,ρ(B), se define de la siguiente manera: ρ(B) = 1 N 2 N−1 X i=1 N X j=i+1 ρ(gi, gj) (7.3) donde ρ(gi, gj) es el coeficiente de correlaci´on entre el gen iy el gen j. S´olo se deben tener en cuenta N 2elementos dada la simetr´ıa del coeficiente de correlaci´on, es decir ρ(gi, gj) = ρ(gj, gi). La figura 7.1 muestra dos biclusters, uno con genes con un r´egimen distinto de expresi´on entre ellos (figura a la izquierda), es decir no siguen un mismo patr´on de comportamiento, y otro en el que se puede observar que siguen un patr´on perfecto de desplazamiento y escalado (figura a la derecha). El bicl´uster de la derecha, donde se puede observar que todos los genes crecen y decrecen de una misma forma, patr´on de desplazamiento, aunque con distinta intensidad, patr´on de escalado, tiene una correlaci´on media igual a 1. En el caso de la figura a la izquierda, donde no se observa ning´un patr´on de comportamiento com´un, la correlaci´on media es casi cero, en concreto 0,003. Se consideran por tanto biclusters de calidad a aquellos que tengan una correlaci´on media cercana a uno y caso contrario se considerar´an biclusters de poca calidad. Como consecuencia de esta idea, la funci´on objetivo que se emplea en el proceso de optimizaci´on es la siguiente: 7.2. Propuesta SSCorr: correlaciones lineales I 75 1 1.5 2 2.5 3 3.5 4 50 100 150 200 250 Condiciones Valor de expresión genes con correlación baja 1 1.5 2 2.5 3 3.5 4 50 100 150 200 250 Condiciones Valor de expresión genes con correlación alta Figura 7.1: A la izquierda un bicluster formado por genes que no siguen un mismo patr´on de expresi´on. A derecha otro bicluster con patrones de desplazamiento y escalado. f(B) = (1 −ρ(B)) + σρ+M11 nG+M21 nC (7.4) donde nG ynC son los n´umeros de genes y condiciones del bicl´uster Brespectivamente, M1yM2son par´ametros de control del volumen del bicl´uster y σρes la desviaci´on est´andar de los valores ρ(gi, gj) de (7.3). La desviaci´on est´andar se incluye en la funci´on objetivo para evitar casos en los que el bicl´uster tenga un valor alto para la correlaci´on media pero a la vez est´e formado por pares de genes poco correlacionados entre s´ı. Es decir, para controlar que los biclusters est´en formados por patrones de genes lo m´as homog´eneos posibles. Por otro lado, se debe tener en cuenta que se ha considerado (1 −ρ(B)) puesto que estamos resolviendo un problema de minimizaci´on. Los mejores biclusters ser´an, por lo tanto, aquellos que tengan un valor para la funci´on objetivo lo m´as cercano a cero posible. La correlaci´on que se ha utilizado es la correlaci´on de Pearson. Se debe tener en cuenta que la optimizaci´on es resistente a posibles ruidos (outliers) en los datos debido a que se inserta en un proceso de optimizaci´on donde se eval´uan multitud de posibles soluciones. Se pueden usar otras definiciones de la correlaci´on pero implica un mayor coste computacional para cada evaluaci´on de la funci´on objetivo. 7.2.2. M´etodo de la mejora Como se ha comentado en el cap´ıtulo anterior la b´usqueda dispersa incorpora un mecanismo de mejora de las soluciones generadas de manera que se acelere el proceso de b´usqueda. Se mejora el valor de su funci´on objetivo, 76 7. B´usqueda basada en correlaci´on mediante una b´usqueda local en el entorno de cada soluci´on, y se intercambia la soluci´on existente por la nueva y de esta manera se introduce m´as calidad en la optimizaci´on. En general se suelen usar como b´usquedas locales “mecanismos ciegos”, basados en permutaciones de las cadenas que modifican las soluciones, de manera que sean procesos independientes del significado de la funci´on objetivo. Sin embargo, si se puede definir un algoritmo que dependa de la sem´antica de la funci´on objetivo y optimice localmente cada soluci´on, se suele llevar a cabo porque el proceso acelera su convergencia de manera considerable. 1 1.5 2 2.5 3 3.5 4 50 100 150 200 250 Condiciones Valor de expresión bicluster antes del Método de la Mejora 1 1.5 2 2.5 3 3.5 4 50 100 150 200 250 Condiciones Valor de expresión bicluster después del Método de la Mejora Figura 7.2: Un biclusters antes (izquierda) y despu´es (derecha) de ser sometido al m´etodo de la mejora. La funci´on objetivo del caso que nos ocupa (ecuaci´on 7.4) busca genes correlacionados positivamente que, como hemos comentado, reflejan comportamientos de desplazamiento y escalado. Se puede definir como mecanismo de mejora para cada bicl´uster un mecanismo que elimine aquellos genes que no est´en correlacionados positivamente. La figura 7.2 muestra un bicl´uster compuesto por cuatro genes: tres altamente correlacionados positivamente y otro que tiene correlaci´on negativa con los tres anteriores. La correlaci´on media de dicho bicl´uster es de 0,0083 pero tras la mejora efectuada, que consiste en eliminar el gen correlacionado negativamente, obtenemos un bicl´uster con correlaci´on media igual a 1. Aunque el volumen haya disminuido la correlaci´on media ha mejorado en este caso y la funci´on objetivo, en su conjunto, mejora su valor. Se debe tener en cuenta que el mecanismo optimiza tan s´olo uno de los t´erminos de la funci´on objetivo, la correlaci´on media, empeorando el t´ermino correspondiente al n´umero de genes del bicluster. Si un bicl´uster se somete al m´etodo de la mejora pero no mejora el valor de la funci´on objetivo, aunque haya mejorado su correlaci´on media, 7.3. Propuesta BISS: correlaciones lineales II 77 simplemente no se intercambiar´a por el nuevo bicl´uster construido. A continuaci´on se presenta el pseudoc´odigo del algoritmo del m´etodo de la mejora expuesto anteriormente. Algorithm 2 M´ etodo de la mejora para SSCorr INPUT Bicluster B= [g1,...,gN] OUTPUT Bicluster B0⊆Btal que ρ(gi, gj)≥0∀gi, gj∈B0 begin i←1, B0← {gi},R← {} while (i < N)do j←i+ 1 while (j≤N)do if (ρ(gi, gj)>0) then if (gj6∈ R)then B0←B0∪ {gj} end if else R←R∪ {gj} end if j←j+ 1 end while i←i+ 1 end while end 7.3. Propuesta BISS: correlaciones lineales II Veamos c´omo se define la funci´on objetivo y el m´etodo de la mejora de la segunda propuesta de biclustering basado en correlaciones lineales usando un esquema de b´usqueda dispersa. 7.3.1. Evaluaci´on de biclusters: funci´on objetivo Los patrones de desplazamiento y escalado reflejan la mayor´ıa de los procesos biol´ogicos en los que la activaci´on de un gen implica la activaci´on adicional de otros genes. Hemos visto que se puede utilizar la correlaci´on lineal como forma de medir esta co-expresi´on m´ultiple de genes en los datos de expresi´on. Sin embargo en la primera propuesta realizada en el apartado anterior no se contemplan los patrones de activaci´on-inhibici´on. Estos patrones consisten en que la desactivaci´on de un gen marca la se˜nal para la activaci´on de otros e implica que estos genes tengan un r´egimen de expresi´on complementario. Cuando uno se expresa el otro se inhibe y viceversa. Este 84 8. B´usqueda basada en integraci´on Es decir, el valor de f3es el mismo para dos biclusters que tengan el mismo conjunto de genes pero distintas condiciones. Este t´ermino mide la relevancia biol´ogica de un bicl´uster, respecto de la informaci´on codificada en el fichero de anotaciones, pero no c´omo son los patrones que lo describen, para lo que es necesario el t´ermino basado en la correlaci´on. A continuaci´on se presentan dos funciones (secciones 8.2.2 y 8.2.2), que usan el fichero de anotaciones como base para calcular la relevancia biol´ogica de los biclusters, y que se utilizan para definir el t´ermino f3. Medida FracGO A continuaci´on se define una medida basada en el enriquecimiento de genes [13] como mecanismo para medir la relevancia biol´ogica de los biclusters. La idea se basa en medir la proporci´on de genes de un bicl´uster que est´an asociados a t´erminos GO enriquecidos, denotaremos a esta medida como FracGO. El proceso de c´alculo tiene lugar de la siguiente manera. Se consideran t´erminos GO enriquecidos a aquellos que est´en sobre-representados con p-value ajustado por debajo de un determinado umbral, conocido como umbral de significancia y que usualmente se suele elegir como 0,05. Para ellos se calcula el p-value ajustado para cada t´ermino GO en el fichero de anotaciones respecto al grupo de genes del bicl´uster. El universo de genes es el conjunto completo de genes presentes en la matriz de expresi´on. Se utiliza el test de Fisher para determinar si los t´erminos est´as estad´ısticamente sobrerepresentados y el test de Bonferroni para el c´alculo del ajuste del p-value con tantas comparaciones como hip´otesis se testean, que se corresponden con el n´umero de t´erminos presentes en el fichero de anotaciones. De esta forma se define FracGO como: FracGO(B) = (0ifJ = 0 1 J·NPJ i=1 xiifJ ≥1(8.5) donde Jes el n´umero de t´erminos GO enriquecidos, en concreto aquellos que tengan un p-value ajustado por debajo de 0,05, Nel n´umero de genes en el bicl´uster y xies el n´umero de genes del bicl´uster que est´an presentes en el t´ermino GO idel fichero de anotaciones. N´otese que FracGO es igual a 1 si todos los genes del bicl´uster est´an asociados con todos los t´erminos GO enriquecidos (xi=N,∀i={1, ..., J}) y 0 cuando no hay ning´un t´ermino GO enriquecido asociado. Se puede concluir que FracGO vale 1 cuando los biclusters son biol´ogicamente relevante y 0 en caso contrario. En este caso, el t´ermino f3se define directamente como: 8.2. Propuesta GoldBinch: integraci´on de informaci´on biol´ogica85 f3(B)=1−FracGO(B) (8.6) El bicl´uster Bse considera como un bicl´uster bueno si f3es igual a 0 y malo si su valor es igual a 1. Medida SimNTO En la literatura existen varias medidas basadas en la similitud seg´un GO entre pares de genes. Estas medidas miden el grado de semejanza entre dos genes seg´un la informaci´on presente de estos en GO. La medida simNTO se basa en el solapamiento de t´erminos definido en [65] y tan s´olo utiliza como entrada el fichero de anotaciones directas. Esta medida es m´as r´apida y simple que otras medidas de similitud GO, basadas en el contenido de informaci´on, o information content (IC), que necesitan de manera adicional la estructura del grafo de GO. SimNTO captura la estructura del grafo de GO a trav´es de la manera que se construye el fichero de anotaciones, en concreto si ´este propaga las anotaciones de los t´erminos hasta la raiz de la ontolog´ıa de GO, es decir, teniendo en cuenta todos los t´erminos padre de cada t´ermino. Se propone en este apartado una medida para evaluar bicl´usters basada en simNTO. Esta medida se basa en la media de los valores de simNTO de los pares genes que componen el bicluster. Es decir, SimNTO(B) = 1 N 2 N−1 X i=1 N X j=i+1 simNTO(gi, gj) (8.7) donde Nes el n´umero de genes del bicl´uster BysimNTO la medida del solapamiento normalizada propuesta en [65]. En particular, simNTO mide el solapamiento entre dos genes g1yg2respecto de los t´erminos GO de la siguiente manera: simNTO(g1, g2) = |annotg1∩annotg2| min(|annotg1|,|annotg2|)(8.8) donde annotgies el conjunto de t´erminos GO asociados al gen giy| · | el n´umero de elementos del conjunto. Es importante comentar que el fichero de anotaciones debe estar construido propagando las anotaciones hasta los t´erminos superiores de la jerarqu´ıa de GO. Por lo tanto, annotgise define considerando el conjunto de todas las anotaciones directas del gen giy las asociadas a sus t´erminos padre en la ontolog´ıa, excluyendo la raiz de la misma. Es decir, el fichero de anotaciones debe capturar la estructura jer´arquica de GO. N´otese que la medida simNT O toma valores entre 0 y 1. Dos genes 86 8. B´usqueda basada en integraci´on que compartan las mismas anotaciones, y por lo tanto son similares en la ontolog´ıa, tienen un valor igual a 1, en caso contrario su valor ser´a 0. Por otro lado, si alguno de los genes del bicl´uster no tiene informaci´on en el fichero de anotaciones, es decir annotges el conjunto vac´ıo, se define su valor de simNTO directamente como cero. La funci´on f3se define como: f3(B) = 1 −SimNT O(B) (8.9) Se puede apreciar que f3(B) = 0 cuando Best´e formado por genes similares seg´un la informaci´on de GO. En este caso se dice que Bes un bicl´uster de calidad seg´un la informaci´on de GO. 8.2.3. Descripci´on del algoritmo Generation Method Improvement Method Build Reference Set Solution Combination Method RESULTS Initial Population P Main Loop Initialization Stop if no more new solutions RefSet Improvement Method Subset Generation Method OUTPUT (biclusters) iteration = numberIter number of iterations < numberIter Reference Set Update INPUT-3 numBi INPUT-2 (gene annotation file) INPUT-1 (microarray expression matrix) number of biclusters < numBi STOP Figura 8.1: Esquema del algoritmo de biclustering propuesto basado en un esquema de b´usqueda dispersa. El algoritmo propuesto se basa en la adaptaci´on de un esquema de b´usqueda dispersa para la optimizaci´on de la funci´on objetivo propuesta (ecuaci´on 8.1). Debido a que el objetivo es el estudio de varias medidas de integraci´on biol´ogica dentro de la funci´on objetivo, es importante definir un esquema de b´usqueda que sea totalmente independiente de la funci´on objetivo. Este hecho motiva un m´etodo de la mejora “ciego”, en el sentido de ser 8.2. Propuesta GoldBinch: integraci´on de informaci´on biol´ogica87 independiente de la funci´on objetivo. Dicho m´etodo se basa en la generaci´on de nuevas soluciones en un entorno de vecindad de la soluci´on dada y su evaluaci´on buscando una soluci´on mejor. La figura 8.1 muestra el esquema de funcionamiento del algoritmo. Se puede observar que la principal novedad en el esquema propuesto son los argumentos de entrada, constituidos por la matriz de expresi´on y por el fichero de anotaciones para los genes. As´ı mismo una de las principales diferencias con los esquemas de b´usqueda dispersas en biclustering vistos con anterioridad lo constituye el m´etodo de la mejora. 8.2.4. M´etodo de la mejora El m´etodo de la mejora elegido es una b´usqueda local “ciega” en el sentido que es independiente de la sem´antica de la funci´on objetivo. En general este tipo de b´usquedas locales son menos eficientes a la hora de mejorar localmente soluciones, en comparaci´on con aquellas definidas “ad-hoc” o ligadas a la funci´on objetivo que se emplee, como por ejemplo en el cap´ıtulo anterior, pero permiten intercambiar distintas funciones y poder comparar el rendimiento de cada una. El objetivo es proporcionar una b´usqueda local que permita acelerar la convergencia del proceso de b´usqueda y, por otro lado, que sea v´alida para cualquier funci´on objetivo que se utilice. De esta forma la funci´on objetivo puede aceptar varias configuraciones, o medidas para integrar la informaci´on biol´ogica, sin tener que realizar ning´un cambio en el esquema de b´usqueda. El m´etodo de la mejora dise˜nado consiste en seleccionar aquel bicl´uster con mejor valor para la funci´on objetivo entre los biclusters cercanos al dado como entrada. Dado un bicl´uster/soluci´on se toma su codificaci´on binaria y se generan un conjunto de soluciones cercanas, en el sentido de la distancia Hamming, de entre las cuales se selecciona la mejor. Si no hay ninguna mejor permanece como salida el mismo bicl´uster utilizado como entrada. T´engase en cuenta que la distancia Hamming mide el grado de similitud entre dos cadenas, por lo que peque˜nas permutaciones en una cadena binaria dan otra cadena cercana seg´un esta distancia. La figura 8.2 muestra un ejemplo de c´omo se generan las soluciones cercanas a la dada. Cada bit de la cadena original es analizado, si su valor es 0 permanece igual pero si su valor es 1 se aplica una de los siguientes casos, de manera que se generen distintas soluciones seg´un cada caso: Caso 1: El bit a la derecha cambia su valor a 1 y el bit actual permanece igual. 88 8. B´usqueda basada en integraci´on 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 0 0 1 0 0 1 01 1 0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 1 0 0 case 1 case 2 case 3 case 4 case 1 case 2 case 3 case 4 G (genes) C (condiciones) ENTRADA: B=GxC (bicluster original) G1 G2 G3 G4 C4 C3 C2 C1 B1= G1xC1 B3= G1xC B2= G3xC3 B4= GxC1 B5= G2xC2 B6= G2xC B7= GxC2 B8= G3xC B9= GxC3 B10= G4xC4 B11= G4xC B12= GxC4 SALIDA: el bicluster con mejor peso de la fnción objetivo de {B, B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12} Figura 8.2: Un peque˜no ejemplo que ilustra el m´etodo de la mejora. Caso 2: El bit a la derecha cambia su valor a 1 y el bit actual cambia a 0. Caso 3: El bit a izquierda cambia a 1 y el bit actual permanece igual. Caso 4: El bit a izquierda cambia a 1 y el bit actual cambia a 0. Aplicando esta regla se generan doce nuevas soluciones aplicando el m´etodo, v´ease la figura 8.2. Si no se genera ning´un nuevo bicl´uster con un valor mejor para su funci´on objetivo, la salida del m´etodo de la mejora es el bicl´uster original. Parte IV Resultados 89 Cap´ıtulo 9 SScorr: resultados Lo m´as importante es tener pasi´on. No se trata de lo que digan los dem´as que es mejor para ti, hay que escuchar lo que te dicta el coraz´on, los instintos. Si de verdad te apasiona algo, encontrar´as la manera de hacerlo. Pero sin pasi´on, es in´util. National Geographic junio 2013. Zona de riesgo, entrevista a Gerlinde Kaltenbrunner, alpinista austriaca 9.1. Introducci´on En este cap´ıtulo presentamos los experimentos realizados con el algoritmo propuesto en la secci´on 7.2 del cap´ıtulo VII. El objetivo del estudio experimental que se presenta a continuaci´on es mostrar la calidad de los biclusters obtenidos. Se han elegido para los experimentos tres conjuntos de datos o data sets. El primero (Yeast) fue utilizado en el trabajo presentado en [25], est´a relacionado con el ciclo celular de la levadura, Saccharomyces cerevisiae, y tiene 2,884 genes y 17 condiciones, . El segundo conjunto de datos (Lymphoma) presenta un estudio en Homo sapiens sobre un tipo concreto de c´ancer, linfomas o tumores s´olidos hematol´ogicos, tiene los datos de expresi´on de 4026 genes bajo 96 condiciones experimentales y fue generado en [3]. Estos dos conjuntos de datos fueron los utilizados en el art´ıculo [24] y han sido frecuentemente utilizados en gran variedad de art´ıculos de biclustering [29, 66, 75]. En este trabajo fue donde se realiz´o su preprocesamiento. El tercer conjunto de datos (GaschYeast) procede de un estudio de la levadura, Saccharomyces cerevisiae, realizado en [40]. Est´a compuesto por 2993 genes y 173 condiciones experimentales. Se ha usado la versi´on del mismo proporcionada por los datos suplementarios de [77]. 91 92 9. SScorr Id bi. Genes Cond. Volumen ρ(B)σ(B) MSR Varianza de los genes biYeastN15 7 10 70 0.95 0.56 59.2 882.8 biYeastN21 11 9 99 0.92 0.47 205.2 1190.5 biYeastN24 9 9 81 0.92 0.45 142.9 1344.8 biYeastN40 13 8 104 0.89 0.45 368.2 2185.4 biYeast 22.27 6.46 133.1 0.90 0.48 321.0 1508.7 biLymphomaN1 14 14 196 0.92 0.43 3719.2 29180.0 biLymphomaN11 17 7 119 0.92 0.50 1607.9 10317.6 biLymphomaN15 21 10 210 0.86 0.43 1818.4 8351.2 biLymphomaN54 9 14 126 0.82 0.45 1292.6 6108.0 biLymphoma 10.81 11.53 123.7 0.85 0.45 2593.3 11643.07 bi1-GaschYeastN1 13 25 325 0.96 0.42 0.08 1.51 bi1-GaschYeastN10 12 22 264 0.95 0.48 0.06 1.19 bi1-GaschYeastN11 41 17 697 0.93 0.34 0.15 1.67 bi1-GaschYeastN25 19 10 190 0.93 0.43 0.19 0.89 bi1-GaschYeast 16.36 14.08 237.6 0.89 0.43 0.32 1.50 bi2-GaschYeastN1 54 39 2106 0.82 0.32 0.22 1.00 bi2-GaschYeastN4 43 32 1376 0.84 0.45 0.18 1.02 bi2-GaschYeastN9 48 24 1152 0.87 0.41 0.17 1.18 bi2-GaschYeastN27 33 28 924 0.84 0.39 0.13 0.72 bi2-GaschYeast 46.69 27.69 1269.4 0.72 0.34 0.38 1.02 Tabla 9.1: Informaci´on sobre los biclusters encontrados por el algoritmo SSCorr Los par´ametros internos del algoritmo propuesto se han elegido de la siguiente forma: el esquema de b´usqueda dispersa tiene 20 como el n´umero m´aximo de iteraciones, 10 el tama˜no del conjunto de referencia, 200 para el n´umero de soluciones de la poblaci´on inicial y 100 para el n´umero de biclusters que se obtienen en cada ejecuci´on. M1yM2son par´ametros de la funci´on objetivo que gu´ıan la b´usqueda para obtener biclusters de un tama˜no determinado. Se utilizan valores altos para M1yM2si se quieren obtener biclusters de tama˜no grande. Los resultados para el dataset de Yeast y de Lymphoma se han obtenido con valores de M1= 1 y M2= 1. Los resultados para GaschYeast se han obtenido para valores de M1= 1 y M2= 1 y para M1= 10 y M2= 10 para as´ı mostrar la influencia de estos par´ametros en el volumen de los biclusters. 9.2. Resultados La tabla 9.1 muestra la informaci´on de cuatro biclusters seleccionados entre los obtenidos de la ejecuci´on del algoritmo SSCorr, as´ı como el valor medio para los 100 biclusters obtenidos (en negrita). Para cada bicl´uster se muestra su identificador, el n´umero de genes y de condiciones, su volumen, el 9.2. Resultados 93 1 2 3 4 5 6 7 8 9 10 400 450 500 550 Condiciones Valor de expresión biYeastN15 123456789 0 50 100 150 200 250 300 Condiciones Valor de expresión biYeastN21 1 2 3 4 5 6 7 8 9 100 200 300 400 Condiciones Valor de expresión biYeastN24 1 2 3 4 5 6 7 8 0 50 100 150 200 250 300 Condiciones Valor de expresión biYeastN40 Figura 9.1: Resultados para el dataset Yeast valor medio de la correlaci´on ρ(B) y la desviaci´on est´andar σ(B), as´ı como el valor del residuo cuadr´atico MSR como de la varianza del valor de los genes con el objetivo de poder establecer comparaciones con otros algoritmos. La varianza de los genes mide la variabilidad en el valor de expresi´on de cada gen. Las figuras 9.1 y 9.2 muestran cuatro biclusters de los datos Yeast y Lymphoma cuya informaci´on se refleja en la tabla 9.1. Las figuras 9.3 y 9.4 muestran por otro lado biclusters de los datos GaschYeast. Los biclusters bi1-GaschYeastN1,bi1-GaschYeastN10,bi1-GaschYeastN11 ybi1GaschYeastN25 de la figura 9.3 se han obtenido con valores M1= 1 y M2= 1, mientras que los biclusters bi2-GaschYeastN1,bi2-GaschYeastN4, bi2-GaschYeastN9 ybi2-GaschYeastN27 de la figura 9.4 lo han sido con los valores M1= 10 y M2= 10. N´otese que cuanto mayores son los valores de los par´ametros el volumen de los biclusters. La elecci´on de los par´ametros M1=M2= 1 se debe a poder obtener biclusters con un n´umero peque˜no de genes y que de esta forma tengan una representaci´on gr´afica m´as clara para apreciar con m´as claridad los patrones que subyacen. Sin embargo, si el objetivo es encontrar biclusters compuestos por genes que compartan el mismo atributo GO, es m´as adecuado obtener un n´umero m´as alto de genes. Por lo tanto, los par´ametros M1=M2= 10 se han elegido con este objetivo, obtener biclusters compuestos por un n´umero alto de genes. 100 9. SScorr SScorr11 SScorr1010 CCC-Bi CCC-Bi (100 biclusters) 0 20 40 60 80 100 Porcentaje de biclusters enriquecidos % Yeast p=0.001% p=0.005% p=0.01% p=0.05% p=0.1% p=0.5% p=1% p=5% Figura 9.7: Comparaci´on entre el algoritmo propuesto y el algoritmo CCC-Bi para el dataset GaschYeast 9.5. Estudio biol´ogico El estudio anterior de enriquecimiento se ha realizado con la herramienta presentada en [2] y, como ya hemos comentado, la informaci´on obtenida se muestra en las figuras 9.1, 9.2 y 9.3 y en la tabla 9.1. En este apartado vamos a hacer el estudio de concreto de varios biclusters para ver los procesos biol´ogicos con los que est´an relacionados. El an´alisis de biYeastN15 identifica el proceso GO (GO: 0006412) con un p-value 5,81e−006. Dicho t´ermino est´a relacionado con la traducci´on, mediante la que el ARNm da lugar a los amino´acidos en el ribosoma. El bicl´uster est´a compuesto por cinco genes que se co-expresan bajo siete condiciones experimentales. Otro ejemplo es el bicl´uster biLymphomaN1 que identifica al t´ermino GO (GO:0016887) conocido como ATPase activity con un p-value de 0,0069. Este proceso se relaciona con las reacciones catal´ıticas que producen el ATP. Para el caso de los datos de GaschYeast se puede localizar el t´ermino (GO:0006412) relacionado con la translaci´on con hasta ocho de los biclusters encontrados. Sin embargo, son m´as interesantes los resultados obtenidos para el bicl´uster bi1GaschYeastN11, que localiza el t´ermino GO (GO:0042254) llamado ribosome biogenesis and assembly, con un p-value de 1,38e−007 y que est´a relacionado con los ribosomas y la s´ıntesis de prote´ınas. Cap´ıtulo 10 BISS: resultados Hasta un descubrimiento tan aparentemente directo como el de un f´osil a menudo es resultado de la formulaci´on de una hip´otesis encubierta pues, de otra manera, ¿por qu´e hab´ıa de mirar alguien unos restos f´osiles dos veces y acaso llev´arselos para investigarlos despu´es m´as detalladamente?. Consejos a un joven cient´ıfico. P.B. Medawar (p´ag. 104) 10.1. Introducci´on En este cap´ıtulo presentamos el estudio experimental relativo a la propuesta presentada en la secci´on 7.3 del cap´ıtulo VII. En la secci´on 10.2 se describen los conjuntos de datos que se utilizan en estos experimentos. En la secci´on 10.3 se lleva a cabo el estudio experimental para la configuraci´on de par´ametros del algoritmo. Los resultados obtenidos se presentan en la secci´on 10.4. En concreto, un estudio comparativo con los principales algoritmos de biclustering usados com´unmente en la literatura como marco de referencia se muestran en la secci´on 10.4.1. Por otro lado, en la secci´on 10.4.2 se muestra la comparaci´on con otros dos algoritmos que tambi´en utilizan la correlaci´on como funci´on de mecanismo de b´usqueda. As´ı mismo, se presenta un estudio biol´ogico cualitativo de los resultados obtenidos en la secci´on 10.4.3. 10.2. Descripci´on de los datos Se han utilizado tres conjuntos de datos para los experimentos realizados, dos de la levadura Saccharomyces cerevisiae y uno de Homo sapiens relacionado con la enfermedad del alzheimer. La levadura se suele utilizar 101 102 10. BISS como organismo modelo en muchos estudios y en consecuencia se puede encontrar mucha informaci´on relacionada en los repositorios (lo que facilita los problemas relacionados con la validaci´on de la informaci´on, nomenclaturas de genes, etc). Uno de los datos de la levadura, lo notaremos como GaschYeast, y el de Homo sapiens, lo notaremos como Alzheimer, se han descargado como parte del material suplementario de las referencias [77] y [78] respectivamente. Los datos de GaschYeast est´an formados por 2993 genes y 173 muestras y los del Alzheimer por 1663 genes y 33 condiciones. Los otros datos de la levadura se han descargado del repositorio Gene Expression Omnibus (GEO)1, en concreto el registro GDS1116 generado en el estudio llevado a cabo en la referencia [17]. Son datos temporales compuestos por 7084 genes y 131 condiciones. El preprocesamiento de estos datos de la levadura se ha llevado a cabo usando GEPAS2usando las opciones por defecto. En el caso de los valores perdidos en los perfiles de expresi´on de los genes, han sido sustituidos con la media de dicho perfil, es decir, la fila de la matriz en la que se encuentran, y en aquellos casos en los que exist´ıa m´as de un 80 % de valores perdidos, esa fila se ha eliminado de los datos. Tras este procesamiento la matriz de expresi´on est´a constituida por 6229 genes y 131 condiciones experimentales. Es decir, aproximadamente el 12 % de los genes son filtrados en el tratamiento. 10.3. Configuraci´on de par´ametros BISS M= 1 M= 10 M= 20 M= 40 genes 11.0 281.4 386.5 415.1 condiciones 12.7 34.4 34.1 34.0 tama˜no 138.0 10057.7 13244.8 13929.8 ρ|·|(B) 0.89 0.30 0.23 0.21 Tabla 10.1: Resultados obtenidos por BISS con distintos valores del par´ametro M. En esta secci´on se va a estudiar c´omo afecta el par´ametro que controla el volumen en la funci´on objetivo (ecuaci´on 7.6) al rendimiento del algoritmo. Se ejecuta BISS con los datos de GDS1116 con distintos valores del par´ame1http://www.ncbi.nlm.nih.gov/geo/ 2http://www.gepas.org/ 10.3. Configuraci´on de par´ametros 103 0 10 20 30 40 50 60 70 80 90 100 Biclusters enriquecidos (%) M=1 M=10 M=20 M=40 Figura 10.1: Porcentaje de biclusters enriquecidos obtenidos con BISS con diferentes valores del par´ametro. tro y se comparan los resultados obtenidos. El estudio es an´alogo para los otros conjuntos de datos y los resultados son similares. Los valores elegidos para el estudio del par´ametro son 1, 10, 20 and 40. La tabla 10.1 muestra el valor medio de los 100 biclusters obtenidos para el n´umero de genes, condiciones y volumen de los biclusters, junto con la correlaci´on media (ecuaci´on 7.5). Se puede observar como un valor bajo en el par´ametro implica un tama˜no peque˜no en los biclusters, en concreto un n´umero bajo de genes. El n´umero de genes aumenta cuando el par´ametro tambi´en lo hace de 10 a 40, sin embargo el n´umero de condiciones permanece constante. Se puede tambi´en observar que un valor bajo para el par´ametro implica biclusters con valores de la correlaci´on cercanos a 1 y por lo tanto compuesto por genes altamente correlacionados entre s´ı tanto negativa como positivamente. Esta situaci´on en cambio implica biclusters con un tama˜no muy peque˜no, como cab´ıa esperar, por lo que seg´un sea el tama˜no deseado se deber´a elegir el valor del par´ametro. La figura 10.1 muestra la relevancia biol´ogica de los resultados obtenidos mediante el an´alisis del enriquecimiento de los biclusters respecto GO para los distintos valores del par´ametro M. El porcentaje de biclusters enriquecidos se ha estudiado usando las tres ramas de GO: BP, MF y CC, la figura muestra la media de los resultados obtenido para las tres. Generalmente se 104 10. BISS 0 10 20 30 40 50 60 70 80 90 100 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Porcentaje de biclusters mejorados Correlación mínima Figura 10.2: Porcentaje de biclusters enriquecidos seg´un el valor de la funci´on objetivo. suele usar un nivel de significancia del 90 % (e= 0,1 %) o 95 % (e= 0,05 %), es decir, un bicl´uster se dice que est´a enriquecido si su p-value ajustado asociado a un t´ermino es menor que 0,1 o 0,05 respectivamente. Se puede observar en la figura que, para un nivel de significancia del 95 % el porcentaje de biclusters enriquecidos para M= 1 es mayor que para M= 10 (31,34 % frente 21,34 %). Sin embargo, para un nivel de significancia del 90 %, los valores para ambos par´ametros son mucho m´as similares (34,67 % y 29,34 %). Se puede concluir observando la tabla 10.1 y la figura 10.1 que un valor alto para la correlaci´on implica mayor relevancia biol´ogica, como era de esperar. Por lo tanto, el valor adecuado para el par´ametro es un valor entre M= 1 y M= 10 y, de esta forma, se consigue el equilibrio entre tama˜no y calidad. En consecuencia se ha elegido para la experimentaci´on un valor del par´ametro M= 5. El umbral de la correlaci´on que se utiliza en el m´etodo de la mejora se ajusta autom´aticamente (m´etodo presentado en 7.3.2). No obstante, la figura 10.2 muestra c´omo interviene su valor en el m´etodo de la mejora. En la figura se puede ver el porcentaje de biclusters que mejoran cada valor del umbral. Con un umbral de 0,3 o 0,4 pr´acticamente todos los biclusters, el 99 % mejoran su valor, por lo que ser´ıa la mejor elecci´on para dicho umbral. 10.4. Resultados 105 10.4. Resultados En esta secci´on se comparan los resultados obtenidos por BISS con los obtenidos por otros algoritmos de la literatura. Primero se presenta una comparaci´on con un grupo de algoritmos considerados como cl´asicos, presentes en la herramienta BiCAT [10]: ChCh [24], ISA [12] y OPSM [11], y, por otro lado, con dos algoritmos tambi´en basados en la correlaci´on BCCA [14] y BICLIC [93]. La configuraci´on de los par´ametros para BISS es de 5 como factor de penalizaci´on y 100 el n´umero de biclusters que se obtienen. Se debe tener en cuenta que cada bicl´uster se encuentra mediante un proceso de b´usqueda dispersa independiente y que, por lo tanto, cuanto mayor sea el n´umero de resultados mejor se controlar´a la naturaleza aleatoria propia de toda metaheur´ıstica de tipo evolutivo. 10.4.1. Comparaci´on con algoritmos cl´asicos Los algoritmos ChCh [24], ISA [12] y OPSM [11], presentes en la herramienta BiCAT [10], se han ejecutado sobre los datos utilizando los par´ametros por defecto o recomendados por los autores. El algoritmo xMotifs [68] tambi´en est´a presente en BiCAT pero no se ha podido aplicar a los datos del experimento debido al gran n´umero de condiciones de las matrices. xMotifs s´olo se puede aplicar a matrices de expresi´on con menos de 64 condiciones. La tabla 10.2 muestra los diferentes rasgos de los biclusters obtenidos por BISS, ChCh, ISA y OPSM para los conjuntos de datos GDS1116, GaschYeast y Alzheimer. En particular, la tabla muestra la media del n´umero de genes, condiciones y tama˜no de los biclusters, junto con el tama˜no del m´as peque˜no y el mayor, as´ı como la media del valor de la correlaci´on y el n´umero de pares de genes correlacionados negativamente. Los valores de ρ|·|(B) yρ(B) son los valores de la correlaci´on media considerando el valor absoluto (ecuaci´on 7.5) y sin considerarlo. Si la diferencia entre ambos valores es peque˜na significa que hay pocos genes con correlaci´on negativa entre ellos, en caso contrario se tratar´a de biclusters en los que dos genes presenten patrones de activaci´on-inhibici´on. Se puede observar que OPSM no captura correlaciones negativas para GaschYeast y Alzheimer, sin embargo s´ı para GDS1116. En este caso, obs´ervese que los valores entre la correlaci´on con valor absoluto y sin valor absoluto son cercanos entre s´ı (0,95 y 0,89), lo cual quiere decir que la correlaci´on negativa entre pares de genes tiene un valor muy peque˜no. En el caso de ISA se puede observar que tanto para GDS1116 como para GaschYeast, el n´umero de pares de genes correlacionados negati- 106 10. BISS vamente es peque˜no. Por tanto, los valores de la correlaci´on con y sin valor absoluto son bastante cercanos entre s´ı (0,74 y 0,63, 0,60 y 0,52, respectivamente). En el caso del conjunto de datos de Alzheimer ISA obtiene tres biclusters con un valor alto para la correlaci´on negativa pero s´olo tienen dos condiciones, por lo que se pueden considerar como triviales y sin informaci´on relevante. Estas observaciones muestran que tanto OPSM como ISA no son adecuados para la b´usqueda de patrones de activaci´on-inhibici´on. Por otro lado, se puede observar en la tabla la gran variabilidad entre los resultados que cada algoritmo aporta. La figura 10.3 muestra m´as claramente la diversidad entre los tama˜nos de los biclusters obtenidos con BISS, ChCh, ISA y OPSM para el conjunto de datos de GDS1116. Cada punto representa un bicl´uster, donde los ejes xe yrepresentan genes y condiciones respectivamente. OPSM tiene 5 biclusters con m´as de 400 genes, y muy pocas condiciones, de 2 a 6, que no aparecen en la figura. Se puede observar que los biclusters de BISS (cuadrados) se agrupan en dos grupos: uno con un n´umero alto de genes y otros con menos de 50 genes. Adem´as todos los biclusters obtenidos por BISS tienen m´as condiciones que los obtenidos por ChCh, ISA u OPSM. Se puede tambi´en observar que los biclusters de ISA (c´ırculos) y los de ChCh (diamantes) tienen menos de 10 condiciones, aunque los de ISA tienen todos m´as de 50 genes. La figura 10.4 presenta el porcentaje de biclusters enriquecidos en uno o m´as t´erminos GO para BISS, ChCh, ISA y OPSM para los conjuntos de datos de GDS1116 y GashYeast. Este porcentaje se ha calculado para las tres ramas de GO (BP, CC y MF) y para los umbrales de significancia m´as usados, 0,05 % y 0,1 %. Se puede observar que BISS obtiene mejores resultados que ISA para los datos de GaschYeast y mejor que ChCh para ambos conjuntos de datos en las tres ramas de GO y para ambos umbrales. Sin embargo, los resultados de ISA y OPSM son mejores que los de BISS para GDS1116. No obstante, ambos algoritmos obtienen un n´umero muy bajo de genes correlacionados negativamente. Aquellos biclusters compuestos por un n´umero muy alto de genes tienen mayor probabilidad de tener subgrupos de genes que sean significativos en t´erminos GO. La influencia del tama˜no de los biclusters en las comparaciones entre algoritmos ha sido estudiada en la literatura [14, 77, 32]. Generalmente, para evitar el efecto del tama˜no de los biclusters, se suelen filtrar aquellos compuestos por un n´umero muy alto de genes. Siguiendo la experimentaci´on llevada a cabo en [14], se ha considerado 50 como el n´umero m´aximo de genes por bicl´uster y en funci´on de ello se han filtrado los resultados. La figura 10.5 muestra el porcentaje de biclusters enriquecidos despu´es 10.4. Resultados 107 del proceso de filtrado. Se debe tener en cuenta que todos los biclusters de ISA para GDS1116 desaparecen al filtrase los resultados ya que todos los biclusters ten´ıan m´as de 50 genes. Se puede apreciar que BISS obtiene m´as biclusters enriquecidos que ISA para GaschYeast y m´as que ChCh para ambos conjuntos de datos en las tres ramas de GO. Por otro lado, BISS mejora los resultados de OPSM para GDS1116 y obtiene resultados similares en el caso de GaschYeast. 0 5 10 15 20 25 30 35 40 45 50 0 50 100 150 200 250 300 350 400 Número de condiciones Número de genes BISS CHCH ISA OPSM Figura 10.3: Tama˜no de los biclusters obtenidos con los algoritmos BISS, ChCh, ISA y OPSM con los datos de GDS1116. 108 10. BISS num. num. num. min. media max. ρ|·|(B)ρ(B) pares de genes bicluster genes condiciones tama˜no tama˜no tama˜no corr. neg. GDS1116 BISS 100 90.4 21.5 (22x13) 2370.29 (300x45) 0.65 0.21 4806.4 ChCh 100 19.0 4.68 (3x5) 66.9 (136x3) 0.49 0.00 266.9 ISA 60 182.1 5.5 (129x2) 1023.5 (280x8) 0.74 0.63 1489.42 OPSM 14 678.1 9.0 (2x21) 2207.1 (4186x2) 0.95 0.89 290033.4 GaschYeast BISS 100 96.2 26.2 (20x18) 2680.4 (292x45) 0.75 0.35 3839.7 ChCh 100 70.6 19.1 (45x9) 1407.1 (222x90) 0.3 0.0 1986.9 ISA 66 76.3 8.7 (11x11) 645.7 (136x10) 0.60 0.52 366.9 OPSM 12 95.6 12.5 (4x18) 849.8 (387x7) 0.98 0.98 0.0 Alzheimer BISS 100 48.7 15.1 (36x10) 741.8 (62x18) 0.83 0.16 488.7 ChCh 100 13.4 6.7 (3x7) 170.55 (152x33) 0.54 0.09 34.2 ISA 3 51.67 2.0 (43x2) 103.3 (56x2) 1.0 0.1 609.67 OPSM 13 246.5 9.8 (12x13) 925.0 (809x3) 0.96 0.96 0.0 Tabla 10.2: Resultados obtenidos por BISS y por los algoritmos cl´asicos, ChCh, ISA y OPSM para los datos de GDS1116, GaschYeast y Alzheimer. 10.4. Resultados 109 BISS CHCH ISA OPSM BISS CHCH ISA OPSM BISS CHCH ISA OPSM 0 10 20 30 40 50 60 70 80 90 100 GDS1116 yeast Porcentaje de biclusters enriquecidos 0.05% 0.1% BP CC MF BISS CHCH ISA OPSM BISS CHCH ISA OPSM BISS CHCH ISA OPSM 0 10 20 30 40 50 60 70 80 90 100 GaschYeast Porcentaje de biclusters enriquecidos 0.05% 0.1% BP CC MF Figura 10.4: Porcentaje de biclusters enriquecidos obtenidos por BISS, ChCh, ISA and OPSM para las ramas de GO BP, CC y MF con los datos de GDS1116 y GaschYeast. 116 10. BISS BISS BCCA-yes BICLIC BISS BCCA-yes BICLIC BISS BCCA-yes BICLIC 0 10 20 30 40 50 60 70 80 90 100 Porcentaje de biclusters altamente enriquecidos GDS1116 yeast 0.05% 0.1% BP CC MF BISS BCCA-yes BICLIC BISS BCCA-yes BICLIC BISS BCCA-yes BICLIC 0 10 20 30 40 50 60 70 80 90 100 Porcentaje de biclusters altamente enriquecidos GaschYeast 0.05% 0.1% BP CC MF Figura 10.8: Porcentaje de biclusters altamente enriquecidos obtenidos por BISS, BCCA-not, BCCA-yes y BICLIC para las ramas BP, CC y MF con los datos GDS1116 y GaschYeast. 10.4.3. Estudio de la significancia biol´ogica de los biclusters En esta secci´on se presenta un estudio biol´ogico cualitativo de algunos de los biclusters obtenidos por BISS. La figura 10.9 muestra la representaci´on gr´afica de un bicl´uster com- 10.4. Resultados 117 puesto por 35 genes y 13 condiciones obtenidos por BISS para los datos del Alzheimer. Observando la figura se pueden observar patrones de desplazamiento y escalado adem´as de patrones de activaci´on-inhibici´on. En concreto, se han representado dos genes correlacionados positivamente usando l´ıneas discontinuas y un tercer gen con correlaci´on negativa respecto a los dos genes anteriores representado usando l´ınea negra. 2 4 6 8 10 12 3 4 5 6 7 8 9 Condiciones experimentales Valor de expresión Datos de Alzheimer Bicluster 62 Figura 10.9: Representaci´on de un bicluster obtenido por BISS con los datos de Alzheimer. La tabla 10.4 muestra el estudio biol´ogico de varios biclusters de BISS obtenidos para los datos de GDS1116 y GaschYeast. Se ha utilizado la herramienta web FuncAssociate3para generar la informaci´on que se refleja en la tabla. En concreto, el tama˜no de los biclusters, el n´umero de genes del bicl´uster asociados con el t´ermino GO correspondiente, el n´umero de genes en dicho t´ermino, el valor p-value ajustado y la descripci´on del t´ermino GO para los dos primeros t´erminos GO asociados. Se puede observar que el bicl´uster #1 tiene 22 y 12 genes en los t´erminos GO:0022626 y GO:0022627 respectivamente, estando formados dichos t´erminos por 163 y 64 genes. Estos t´erminos GO pertenecen a la rama CC y est´an relacionados con la funcionalidad de los ribosomas. El bicl´uster #70 tiene 4 genes asociados con los t´erminos GO:0000722 y GO:0003678. Para los datos de GaschYeast, los biclusters #1 y #62 tienen aproximadamente la mitad de sus genes relacionados en los t´erminos GO:0034660 y GO:0034470. 3http://llama.mshri.on.ca/funcassociate/ 118 10. BISS bicluster genes del bi. genes en p-value t´ermino GO & descripci´on tama˜no en t´ermino GO t´ermino GO GDS1116 bicluster #1 (38,22) 22 163 <0,001 GO:0022626 cytosolic ribosome 12 64 <0,001 GO:0022627 cytosolic small ribosomal subunit bicluster #70 (24,19) 4 19 <0,001 GO:0000722 telomere maintenance via recombination 4 36 0,003 GO:0003678 DNA helicase activity GaschYeast bicluster #1 (51,30) 12 64 <0,001 GO:0022627 cytosolic small ribosomal subunit 23 163 <0,001 GO:0022626 cytosolic ribosome bicluster #62 (44,20) 21 483 <0,001 GO:0034660 ncRNA metabolic process 19 426 <0,001 GO:0034470 ncRNA processing Tabla 10.4: Significancia biol´ogica de varios biclusters obtenidos por BISS para los datos de GDS1116 y GaschYeast. Cap´ıtulo 11 GoldBinch: resultados La noble ciencia de la genealog´ıa pierde esplendor por la extrema imperfecci´on de sus archivos. El origen de las especies. Charles Darwin (p´ag. 774) 11.1. Introducci´on En este cap´ıtulo presentamos el estudio experimental relativo a la integraci´on de informaci´on biol´ogica presentada en el cap´ıtulo VIII. El objetivo que nos marcamos en la experimentaci´on presentada es el an´alisis de c´omo afecta en el rendimiento de un algoritmo de biclustering la integraci´on de informaci´on biol´ogica. Se comparan principalmente los resultados obtenidos con las medidas FracGO y SimNTO para la integraci´on de informaci´on. Los resultados tambi´en se comparan con un grupo de algoritmos de biclustering considerados como cl´asicos, ChCh [24], ISA [12], OPSM [11] y xMotifs [68], y que suelen ser usados como marco de trabajo en la literatura. La metodolog´ıa de comparaci´on se basa en la propuesta en la referencia [77], basada en el estudio del porcentaje de biclusters enriquecidos, y que se usa com´unmente en la literatura. 11.2. Datos Para los experimentos realizados se han utilizado dos conjuntos de datos de la levadura descargados del repositorio GEO [31] con identificadores GDS1116 y GDS2914. El primero est´a compuesto por 7085 perfiles de expresi´on y 131 muestras. Estos datos fueron generados en un estudio sobre la variabilidad gen´etica en la evoluci´on de poblaciones de levadura obtenidas mediante el cruce de cepas de dos tipos distintos. El segundo conjunto 119 120 11. GoldBinch de datos est´a formado por 15488 perfiles de expresi´on y 36 muestras y se trata de datos de tipo temporal relacionados con el ciclo de la levadura de muestras tratadas con dosis altas o bajas de cafe´ına. Estos datos en crudo se han tratado con la herramienta web Babelomics [62] siguiendo el mismo preprocesamiento para ambos conjuntos de datos. Se han filtrado aquellos perfiles de expresi´on con m´as de un 30 % de valores nulos as´ı como, por otro lado, se han cambiado por la media de los valores del perfil de expresi´on correspondiente el resto de valores nulos que permanec´ıan en los datos. Aquellos perfiles que aparecen repetidos varias veces para un mismo gen han sido fusionado mediante la media de sus valores. Tras este procesamiento de los datos en crudo, la matriz de expresi´on de GDS1116 est´a compuesta de 882 genes y 131 condiciones y, por otro lado, GDS2914 por 975 genes y 36 condiciones. La informaci´on biol´ogica se proporciona a trav´es de un fichero de anotaciones directas de los t´erminos GO obtenidos para la rama de BP de GO. Este tipo de fichero relaciona cada gen con el conjunto de t´erminos GO en los que interviene. Se puede generar de varias formas seg´un se pongan m´as o menos restricciones a GO. En este trabajo se ha tenido en cuenta la estructura de ´arbol de GO y los ficheros de anotaciones se han construido propagando las anotaciones hasta los t´erminos altos de la ontolog´ıa. Estos ficheros de anotaciones se han generado usando Babelomics con las opciones por defecto para este tipo de tareas. El fichero de anotaciones para los datos GDS1116 tiene informaci´on sobre anotaciones para 632 de los 882 genes de la matriz de expresi´on. Este fichero contiene 245 t´erminos GO diferentes y el n´umero medio de t´erminos GO por gen es de 10,6. Por otro lado, para GDS2914 de los 975 genes de su matriz de expresi´on, el fichero de anotaciones generado contiene informaci´on para 658 genes, contiene 256 t´erminos GO y el n´umero medio de t´erminos por gen es igual a 10,1. 11.3. Resultados Se presenta a continuaci´on los resultados obtenidos con el objetivo de mostrar que la integraci´on de informaci´on mejora el rendimiento y se consiguen encontrar biclusters de mayor calidad. Los resultados se han obtenido usando las distintas configuraciones de la funci´on objetivo propuestas en el cap´ıtulo VIII. Se estudian estos resultados seg´un el tama˜no de los biclusters obtenidos, el porcentaje de enriquecimiento as´ı como el solapamiento. As´ı mismo, se presentan tambi´en los resultados obtenidos usando otras fuentes de informaci´on diferentes a GO, como KEGG e Interpro, y usando otras medidas de similitud funcional tambi´en basadas en la similitud entre pares 11.3. Resultados 121 Configuraci´on Numero Biclusters funci´on de (M1,M2,M3) enriquecidos ( %) objetivo biclusters BP MF CC 1-SimNTO 10 (2,1,1) 100 100 100 1-SimNTO 50 (2,1,1) 100 98 100 1-SimNTO 100 (2,1,1) 99 97 97 1-FracGO 10 (2,1,1) 100 70 50 1-FracGO 50 (2,1,1) 100 72 64 1-FracGO 100 (2,1,1) 100 73 67 0 10 (2,1,0) 85 82 88 0 50 (2,1,0) 82 72 84 0 100 (2,1,0) 85 82 88 Tabla 11.1: Porcentaje de biclusters enriquecidos obtenidos por el algoritmo GoldBinch para diferentes valores del n´umero de biclusters. de genes. Cada ejecuci´on del algoritmo encuentra 100 biclusters. La tabla 11.1 presenta el porcentaje de biclusters enriquecidos obtenidos por el algoritmo con distintos valores para el par´ametro de entrada que determina el n´umero de biclusters que se desean obtener (10, 50, y 100). Se puede observar que el porcentaje de biclusters enriquecidos no depende de esta elecci´on y por lo tanto no es un par´ametro que afecte al estudio. Se debe tener en cuenta que el algoritmo obtiene cada bicl´uster de manera independiente a trav´es de un procedimiento no determinista, es por ello que se elige un valor suficientemente grande para el n´umero de biclusters que se encuentran, concretamente el valor de 100. 122 11. GoldBinch Funci´on objetivo Biclusters T´erminos GO Datos Medida Par´ametros Tama˜no enriquecidos ( %) por biclus. Tiempo f3(M1,M2,M3) BP MF CC (BP) (segundos) (2, 1, 1) (11.6 ×15.6) 99 97 97 5.74 28.65 1-SimNTO (2, 1, 2) (8.7 ×15.2) 87 75 84 3.67 15.78 (2, 2, 1) (10.1 ×5.1) 95 83 89 4.5 24.03 GDS1116 (2, 1, 1) (181.6 ×19.4) 100 73 67 1 5410.98 1-FracGO (2, 1, 2) (193.9 ×19.3) 100 79 79 1 5546.12 (2, 2, 1) (109.2 ×3) 100 47 52 1 5682.65 (2, 1, 0) (23.5 ×14.7) 85 82 88 2.16 38.29 0 (2, 2, 0) (46.8 ×3.2) 25 17 21 0.4 11.51 (2, 1, 1) (10.9 ×10.9) 87 33 33 5.45 27.76 1-SimNTO (2, 1, 2) (8.0 ×10.2) 65 24 33 2.94 15.67 (2, 2, 1) (9.5 ×3.3) 87 25 30 5.39 22.18 GDS2914 (2, 1, 1) (180.6 ×15.1) 100 97 94 1.01 5420.84 1-FracGO (2, 1, 2) (193.2 ×15.8) 100 98 94 1 5920.09 (2, 2, 1) (102.8 ×3) 100 72 67 1 6311.43 (2, 1, 0) (24.1 ×9.0) 2 5 6 0.02 13.14 0 (2, 2, 0) (37.1 ×3.1) 13 15 17 0.19 7.16 Tabla 11.2: Resultados obtenidos con distintas configuraciones de la funci´on objetivo para los dos conjuntos de datos GDS1116 y GDS2914. Cada columna muestra una ejecuci´on que obtiene 100 biclusters. 11.3. Resultados 123 Biclusters T´erminos GO Datos Algoritmo N´umero Tama˜no enriquecidos ( %) por bicluster of biclusters BP MF CC (BP) ChCh 100 (21.9 ×18.4) 10 8 13 0.30 GDS1116 ISA 11 (50.7 ×6.5) 72.7 72.7 72.7 6.45 OPSM 16 (128.1 ×10.4) 75 81.2 75 20.06 xMotifs - - - - - - ChCh 100 (17.2 ×8.8) 4 4 2 0.04 GDS2914 ISA 5 (28.6 ×2) 20 20 0 0.60 OPSM 11 (164.4 ×7.2) 45.45 36.4 36.4 28.64 xMotifs 999 (61.2 ×5) 64.76 31.5 52.15 1.13 Tabla 11.3: Resultados obtenidos por los algoritmos cl´asicos ChCh, ISA, OPSM y xMotifs para los dos conjuntos de datos GDS1116 y GDS2914. 124 11. GoldBinch La tabla 11.2 resume la informaci´on de los biclusters obtenidos usando diferentes configuraciones de la funci´on objetivo para los conjuntos de datos GDS1116 y GDS2914. La columna Medida indica si la funci´on objetivo tiene en cuenta la integraci´on de la informaci´on a trav´es de la medida SimNTO (Eq. 8.9) o FracGO (Eq. 8.6) o si no se lleva a cabo integraci´on de informaci´on (f3= 0 en Eq. 8.1). La columna Par´ametros representa el peso correspondiente a cada t´ermino de la funci´on objetivo. Es importante destacar que todos los t´erminos var´ıan entre 0 y 1. El par´ametro M1relacionado con el tama˜no de los biclusters se fija a 2 para evitar encontrar biclusters con un n´umero trivial de genes o condiciones[69], de esta manera se evita encontrar biclusters compuestos por ejemplo por tan s´olo dos genes o condiciones. Las configuraciones de la funci´on objetivo estudiadas son las siguientes: (M2= 1, M3= 1) que le da el mismo peso al t´ermino relativo a la correlaci´on que al de la integraci´on biol´ogica, (M2= 2, M3= 1) donde tiene m´as importancia el t´ermino de la correlaci´on entre los genes que el relativo a la integraci´on y, por ´ultimo, (M2= 1, M3= 2) donde la situaci´on es justo la contraria. En el caso que no se lleve a cabo la integraci´on de informaci´on biol´ogica se tiene que M3= 0 y por lo tanto tan s´olo hay dos casos de estudio seg´un la importancia del t´ermino relativo a la correlaci´on M2= 1 o M2= 2. Se debe tener en cuenta que M1no puede ser igual a cero para evitar biclusters triviales [69]. Por otro lado, si M2= 0 el n´umero de condiciones no se podr´ıa controlar y se estar´ıa llevando a cabo un algoritmo de clustering pues se consideran todas las condiciones en cada bicl´uster. El resto de columnas de la tabla 11.2, Tama˜no,Biclusters enriquecidos ( %),T´erminos GO por bicluster yTiempo, muestran respectivamente el valor medio del n´umero de genes y condiciones de los 100 biclusters obtenidos, el porcentaje de biclusters enriquecidos, la media de t´erminos GO por bicl´uster y el tiempo medio para obtener cada bicl´uster. Generalmente el estudio del enriquecimiento de los biclusters se realiza respecto al t´ermino de BP de GO [77] [32]. Sin embargo en este estudio la significancia biol´ogica tambi´en se estudia usando las otras dos ramas de GO: MF y CC. Haya que tener en cuenta que el n´umero medio de t´erminos GO por bicl´uster se establece teniendo en cuenta todos los biclusters, no s´olo aquellos que est´an enriquecidos. El algoritmo GoldBinch se ha comparado con una familia de algoritmo de biclustering considerados como cl´asicos. Estos algoritmos son en concreto ChCh [24], ISA [12], OPSM [11] y xMotifs [68], disponibles a trav´es de la herramienta BiCAT [10], y que se suelen usar como marco de referencia en la literatura de biclustering [77]. La tabla 11.3 presenta el n´umero de 11.3. Resultados 125 biclusters, el tama˜no medio de los mismos, la media del porcentaje de biclusters enriquecidos seg´un las ramas de BP, MF y CC de GO, as´ı como el n´umero de t´erminos GO por bicl´uster seg´un BP, para ambos conjuntos de datos GDS1116 y GDS2914. T´engase en cuenta que tan s´olo se presentan resultados de xMotfs para los datos de GDS2914 porque el algoritmo s´olo se puede ejecutar para matrices que tengan menos de 64 columnas. Las figuras 11.1 y 11.2 muestran el porcentaje de biclusters enriquecidos presentados en la tablas 11.2 y 11.3 para los dos conjuntos de datos, GDS1116 y GDS2914, respectivamente. Las barras de color negro representan BP, las grises MF y las blancas CC. Se debe tener en cuenta que 211, 212 y 221 representan (M1= 2, M2= 1, M3= 1), (M1= 2, M2= 1, M3= 2) y (M1= 2, M2= 2, M3= 1) respectivamente. 0 10 20 30 40 50 60 70 80 90 100 211 212 221 211 212 221 210 220 ChCh ISA OPSM GDS1116 BP MF CC 1-SimNTO 1-FracGO 0 Figura 11.1: Porcentaje de biclusters enriquecidos para GDS1116. Las figuras 11.3, 11.4 y 11.5 muestran el tama˜no de los biclusters obtenidos para GDS1116 cuando se usan diferntes configuraciones de pesos propuestas. Cada punto representa un bicl´uster donde el n´umero de genes est´a representado en el eje xy el n´umero de las condiciones en el eje y. Esta misma informaci´on se puede observar en la tabla 11.4 que muestra la media, la varianza, los valores m´aximos y m´ınimos del n´umero de genes y condiciones. 132 11. GoldBinch CC. T´engase en cuenta que SimNTO se basa en un criterio distinto al del enriquecimiento de genes. Para los datos GDS2914, se puede observar que tanto SimNTO como FracGO mejoran los resultados en todos los casos a la configuraci´on de la funci´on objetivo cuando no hay integraci´on biol´ogica (f3= 0). Para los datos de GDS1116, se puede observar en la figura 11.1 que la configuraci´on de par´ametros 211 para SimNTO mejora a las configuraciones 210 y 220. Por otro lado, para FracGO los resultados para 212 son un poco mejor que los de 210 para MF y CC pero est´an en el mismo rango de valores (v´ease la l´ınea horizontal al 79 % en la figura). Por otro lado, el porcentaje de biclusters enriquecidos usando tanto FracGO como SimNTO mejora los resultados de los algoritmos cl´asicos de biclustering. Para GDS1116, se puede observar en la figura 11.1 que SimNTO obtiene mejores resultados que ChCh, ISA y OPSM. Por otro lado, todas las configuraciones de FracGO mejoran a ChCh y para 212 los resultados est´an el mismo rango de valores que ISA y OPSM para MF y CC (v´ease la l´ınea horizontal en la figura al 79 %). Para GDS2914, la figura 11.2 muestra claramente que SimNTO mejora a ChCh, ISA, OPSM y xMotifs para BP y FracGO mejora a todos los algoritmos para BP, MF y CC. Para OPSM se obtiene un valor alto para el n´umero medio de t´erminos GO por bicl´uster (20.06 y 28.64 para GDS1116 y GDS2914 respectivamente). Este hecho se debe a que los biclusters de OPSM est´an compuestos por un n´umero muy alto de genes. El porcentaje de biclusters enriquecidos para SimNTO es mayor cuando se le da ´enfasis al t´ermino de la correlaci´on (configuraci´on 221) que cuando se enfatiza el t´ermino de la integraci´on (configuraci´on 212) (v´ease los c´ırculos en las figuras 11.1 y 11.2). Este hecho se debe a que la medida SimNTO no se basa en la idea del enriquecimiento de genes sino en el solapamiento de t´erminos GO entre los t´erminos asociados a cada gen. La mejor configuraci´on para SimNTO es 211, es decir, la misma importancia para M2que para M3. Por lo tanto, se puede concluir que la mejor opci´on para la configuraci´on de la funci´on objetivo es buscar un equilibrio entre el t´ermino relativo a la correlaci´on y el relativo a la integraci´on biol´ogica. Las comparativas basadas en el enriquecimiento de los genes pasan por alto las condiciones que componen los biclusters. Estas comparativas deben ser ampliadas observando los tama˜nos de los biclusters para descartar situaciones en las que los resultados obtenidos sean triviales y tienen informaci´on relevante. Por ejemplo, un bicl´uster compuesto por un n´umero alto de genes, que muestren enriquecimiento GO, pero que s´olo est´e compuesto por dos condiciones, no aporta informaci´on relevante de un comportamiento subyacente, tan s´olo muestra que ese conjunto de genes se expresan en dos 11.4. Discusi´on de los resultados 133 condiciones. Se puede observar teniendo en cuenta las figuras 11.3 and 11.4 y la tabla 11.2, que el tama˜no de los biclusters es igual cuando el t´ermino de integraci´on es igual o m´as relevante que el t´ermino de la correlaci´on (par´ametros M2=M3= 1 o M2= 1 y M3= 2, respectivamente). Sin embargo, en la figura 11.5 se puede observar que el tama˜no decrece cuando se prima el termino de la correlaci´on (par´ametros M2= 2 y M3= 1). En particular, tan s´olo 5 condiciones para SimNTO como valor medio y colapsa a 3 para FracGO y el caso en el que no hay integraci´on. Por otro lado, se debe observar que los biclusters de FracGO tienen en general un n´umero m´as alto de genes que los de SimNTO. A pesar de que el porcentaje de biclusters enriquecidos es del 100 % con FracGO para BP, el valor medio de t´erminos GO por bicl´uster es de tan s´olo 1 (v´ease tabla 11.2). La medida FracGO busca genes que compartan un mismo t´ermino GO, por esta raz´on FracGO encuentra biclusters con tan s´olo un t´ermino GO que probablemente ser´a un t´ermino gen´erico en los niveles superiores de GO. Por el contrario, el n´umero medio de atributos GO para SimNTO es de 5,74, 3,67 y 4,5 para GDS1116 y, por otro lado, de 5,45, 2,94 y 5,39 para GDS2914. Por lo tanto, los biclusters obtenidos con SimNTO se componen por grupos de genes relacionados con un n´umero mayor de t´erminos GO que los obtenidos por FracGO, lo que implica que aportan informaci´on biol´ogica m´as relevante. En la tabla 11.2 se puede observar que el coste computacional de FracGO es m´as alto que el de SimNTO. Este hecho es l´ogico teniendo en cuenta su definici´on. Para cada conjunto de genes se tiene que calcular por cada t´ermino GO del fichero de anotaciones el p-value asociado. Adem´as, se debe evaluar multitud de soluciones/biclusters durante el proceso de b´usqueda (generaci´on de la poblaci´on inicial, mejora, estabilidad del conjunto de referencia, etc), es decir, cientos o incluso miles de posibles soluciones. Hay que tener en cuenta que cuanto menos t´erminos haya en los ficheros de anotaciones m´as r´apido ser´a el tiempo de ejecuci´on para la medida FracGO. Los ficheros de anotaciones se pueden generar de multitud de forma, sin embargo la medida SimNTO requiere una serie de restricciones. En concreto, esta medida requiere que el fichero de anotaciones sea una ontolog´ıa, como en el caso de GO, y que el fichero de anotaciones tenga en cuenta dicha ontolog´ıa al completo y no s´olo una parte. FracGO en cambio acepta cualquier tipo de fichero de anotaciones sea fruto o no de una ontolog´ıa o, en el caso de que lo sea, acepta informaciones parciales de la misma, es decir, la informaci´on parcial entre dos niveles dados de esa ontolog´ıa. La tabla 11.5 muestra un ejemplo en el que se puede utilizar la medida FracGO pero no SimNTO. En la tabla 11.6 se puede observar que el n´umero de genes anotados en 134 11. GoldBinch GO para ambos conjuntos de datos es sensiblemente superior a los anotados en KEGG o InterPro. Se puede observar en las tablas 11.2 y 11.5 c´omo influyen el n´umero de genes anotados y el n´umero de anotaciones por gen en los resultados obtenidos por FracGO. Cuando menor es el n´umero de genes anotados, es decir menos informaci´on se tiene, peores son los resultados. 11.4. Discusi´on de los resultados 135 Anotaciones Par´ametros Biclusters T´erminos GO Datos funcionales (M1,M2,M3) Tama˜no enriquecidos ( %) por biclus. Tiempo de BP MF CC (BP) (segundos) (2, 1, 1) (73.4 ×18.1) 13 26 34 0.20 165.4 KEGG (2, 1, 2) (79.6 ×17.8) 13 26 27 0.21 175.6 (2, 2, 1) (49.8 ×3.1) 7 11 8 0.07 145.3 GDS1116 (2, 1, 1) (14.4 ×16.2) 71 80 71 1.81 3613.3 InterPro (2, 1, 2) (30.4 ×17.0) 60 78 52 3.32 2380.3 (2, 2, 1) (43.3 ×3.3) 24 21 22 0.52 2243.8 (2, 1, 1) (69.4 ×13.3) 18 49 30 0.33 116.0 KEGG (2, 1, 2) (77.1 ×14.2) 24 46 23 0.48 126.6 (2, 2, 1) (42.6 ×3.0) 12 15 11 0.12 100.6 GDS2914 (2, 1, 1) (17.5 ×9.1) 20 19 6 0.41 1795.3 InterPro (2, 1, 2) (15.5 ×9.6) 26 23 15 0.99 1825.8 (2, 2, 1) (39.2 ×3.1) 25 18 16 0.33 1850.6 Tabla 11.5: Resultados obtenidos con la la medida FracGO usando rutas KEGG e Interpro con los conjuntos de datos GDS1116 y GDS2914. Cada columna muestra una ejecuci´on que obtiene 100 biclusters. 136 11. GoldBinch Datos Tama˜no Fuente N´umero de N´umero de Media term. anotaci´on funcional genes t´erminos por gen GO (BP domains) 632 245 10.6 KEGG pathways 239 53 1.8 GDS1116 (882 ×131) InterPro 575 699 2.5 GO (MF domains) 634 135 5.5 GO (CC domains) 703 44 3.1 GO (BP domains) 658 256 10.1 KEGG pathways 190 65 1.9 GDS2914 (975 ×36) InterPro 556 653 2.2 GO (MF domains) 615 127 4.9 GO (CC domains) 740 46 3.2 Tabla 11.6: Anotaciones funcionales para GO, rutas KEEG e InterPro para los conjuntos de datos GDS1116 y GDS2914. 11.4. Discusi´on de los resultados 137 La tabla 11.7 muestra los resultados de otras medidas GO basadas en pares de genes distintas a SimNTO. SimGIC y SimUI integran la informaci´on biol´ogica en el algoritmo usando la misma idea que SimNTO, la similitud GO entre pares de genes, pero su funcionamiento difiere del de SimNTO. Se puede observar que los biclusters obtenidos por SimNTO tienen un n´umero de t´erminos GO por biclusters m´as alto que SimGIC y SimUI. Por otro lado, SimNTO obtiene un porcentaje m´as alto de biclusters enriquecidos que SimGIC y SimUI. Se puede por tanto concluir que SimNTO obtiene mejores resultados que SimGIC y SimUI. Se debe tener en cuenta adem´as que el coste computacional de SimNTO es menor debido a su naturaleza, ya que la estructura de GO la tiene en cuenta a trav´es del fichero de anotaciones sin tener que consultar un fichero adicional con la misma. 138 11. GoldBinch Funci´on objetivo Biclusters T´erminos GO Datos Medida Par´ametros Tama˜no enriquecidos ( %) por biclus. Tiempo f3(M1,M2,M3) BP MF CC (BP) (segundos) (2, 1, 1) (11.2 ×15.6) 100 100 99 4.5 1409.4 1-SimGIC (2, 1, 2) (9.0 ×20.0) 100 100 100 2.0 419.0 GDS1116 (2, 2, 1) (19.6 ×4.2) 51 48 53 1.1 887.1 (2, 1, 1) (10.6 ×15.6) 98 97 98 4.1 584.3 1-SimUI (2, 1, 2) (8.71 ×16.9) 94 90 93 3.1 275.5 (2, 2, 1) (10.2 ×4.6) 62 66 65 1.5 509.5 (2, 1, 1) (23.0 ×9.1) 2 4 7 0.03 1572.2 1-SimGIC (2, 1, 2) (14.8 ×8.8.x) 36 17 18 1.6 993.1 GDS2914 (2, 2, 1) (34.4 ×3.1) 10 8 9 0.1 993.1 (2, 1, 1) (17.0 ×9.2) 11 5 11 0.2 348.2 1-SimUI (2, 1, 2) (8.4 ×9.8) 64 48 47 1.7 348.2 (2, 2, 1) (18.7 ×3.1) 21 8 19 0.6 536.4 Tabla 11.7: Resultados obtenidos usando otras medidas de GO basadas en pares de genes para la integraci´on de informaci´on biol´ogica. Cada columna representa una ejecuci´on que obtiene 100 biclusters. 11.5. Evaluaci´on biol´ogica cualitativa 139 En resumen, y teniendo en cuenta el coste computacional para la medida FracGO, la opci´on de SimNTO es la m´as adecuada para la integraci´on de informaci´on cuando se usa la ontolog´ıa GO teniendo en cuenta toda su estructura. De hecho los biclusters que se obtienen con FracGO en estos casos estar´an compuestos por genes que comparten tan s´olo un t´ermino GO muy general en la ontolog´ıa. Sin embargo, si la informaci´on de la ontolog´ıa es tan s´olo parcial, de manera que se tenga en cuenta tan s´olo la informaci´on entre varios subniveles intermedios de la misma, o se utiliza como informaci´on ficheros de anotaciones generados por otras fuentes de informaci´on como KEGG o InterPro, la ´unica opci´on en estos casos es FracGO. 11.5. Evaluaci´on biol´ogica cualitativa El enriquecimiento de genes es el criterio com´unmente utilizado en la literatura de biclustering como marco de comparaci´on entre algortimos ([77], [32]). En la secci´on anterior hemos analizado los resultados obtenidos por el algoritmo utilizando las configuraciones basadas en SimNTO y FracGO. Se ha visto que los biclusters obtenidos con FracGO est´an formados por grupos de genes que tan s´olo son significativos en un t´ermino GO (v´ease la tabla 11.2) que, si es uno de los t´erminos m´as altos en la jerarqu´ıa de GO, puede aportar informaci´on no relevante. En esta secci´on se trata de analizar no ya que el algoritmo obtenga informaci´on biol´ogica sino de qu´e tipo de informaci´on se trata y si es relevante o no. A continuaci´on vamos a tratar de confirmar la hip´otesis de que los biclusters de FracGO capturan informaci´on no relevante, por ser informaci´on de t´erminos GO muy generales, mientras que SimNTO si captura informaci´on relevante. A continuaci´on se realiza un evaluaci´on biol´ogica de tipo cualitativo usando las ideas usadas en la referencia [73]. Este estudio se basa en la significancia estad´ıstica de un grupo de genes en una determinada ruta usando Reactome [45] como referencia. Se han estudiado los cinco primeros biclusters seg´un el valor de su funci´on objetivo para los datos GDS1116. En concreto, los cinco primeros biclusters para las configuraciones 211 y 212 para SimNTO y FracGO, as´ı como los cinco primeros biclusters para la configuraci´on 210 para Corr. T´engase en cuenta que los biclusters de las configuraciones 221, para FracGO y SimNTO, y los biclusters para la configuraci´on 220 para Corr tienen un n´umero muy bajo de condiciones y no son interesantes de estudiar. Los cinco biclusters de SimNTO para 211 y 212 presentan mapeo de rutas, es decir, est´an compuestos por genes presentes en rutas metab´olicas representadas en Reactome. En cambio, tan s´olo dos biclusters de los cinco de Corr, para 220, presentan mapeo de rutas y no se encuentra ninguna in- 140 11. GoldBinch formaci´on para FracGO ni para la configuraci´on 211 ni para 212. Las tablas 11.8 y 11.9 muestran el an´alisis de este mapeo de rutas usando Reactome para los biclusters tercero y quinto de SimNTO con las configuraciones 211 y 212 respectivamente. La tabla 11.10 muestra la informaci´on del cuarto bicluster de Corr para 220. Cada columna de la tabla muestra el identificador de la ruta o pathway. En el cap´ıtulo de datos suplementarios se suministra la informaci´on de todas las tablas generadas para todos los biclusters. 11.5. Evaluaci´on biol´ogica cualitativa 141 Identificador pathway Nombre pathway FDR 247749 Eukaryotic Translation Elongation 0,001 260795 Translation 0,001 232946 GTP hydrolysis and joining of the 60S ribosomal subunit 0,001 217188 Formation of a pool of free 40S subunits 0,001 257612 Eukaryotic Translation Termination 0,001 257951 Peptide chain elongation 0,001 188965 SRP-dependent cotranslational protein targeting to membrane 0,001 189183 Nonsense Mediated Decay (NMD) independent of the Exon Junction Complex (EJC) 0,001 189048 Nonsense-Mediated Decay (NMD) 0,001 189050 Nonsense Mediated Decay (NMD) enhanced by the Exon Junction Complex (EJC) 0,001 252688 L13a-mediated translational silencing of Ceruloplasmin expression 0,002 251703 Cap-dependent Translation Initiation 0,002 230274 Eukaryotic Translation Initiation 0,002 257608 Formation of the ternary complex, and subsequently, the 43S complex 0,040 233365 Metabolism of proteins 0,040 248935 Ribosomal scanning and start codon recognition 0,050 Tabla 11.8: Resultado del an´alisis usando Reactome para el bicl´uster 3 obtenido con SimNTO y con la configuraci´on 211.