Biclustering sobre datos de expresión génicajanepo/doc/TESIS-presentacion-janepo.v2.pdf · 1. Introducción 2. Estado del arte 3. Propuestas y resultados 1) SScorr 2) BISS 3) GoldBinch

Biclustering sobre datos de expresión génica

Candidato : Juan A. Nepomuceno Chamorro

Directores : Alicia Troncoso Lora

Jesús S. Aguilar Ruiz

Disertación tesis doctoral. Sevilla, 21de julio de 2015

Candidato: Juan A. Nepomuceno ChamorroDpto. Lenguajes y Sistemas Informáticos

Universidad de Sevilla

Directores: Alicia Troncoso Lora

Jesús S. Aguilar RuizÁrea de Lenguajes y Sistemas Informáticos

Universidad Pablo de Olavide

Minería de Datos

Computación Evolutiva

Bioinformática

2

Inicio

Guía

1. Introducción

2. Estado del arte

3. Propuestas y resultados

1) SScorr

2) BISS

3) GoldBinch

4. Conclusiones y plan de futuro

5. Contribuciones

Introducción Estado del arte Propuestas y resultados Conclusiones Contribuciones3

Guía

1. Introducción

2. Estado del arte


1) SScorr

2) BISS

3) GoldBinch


5. Contribuciones


Problema - contexto

Dogma central de la biología molecular

� Visión actual: holística o de sistemas

Introducción Estado del arte Propuestas y resultados Conclusiones Contribuciones

ADN ARN Aminoácidos/Proteínas

Transcripción Translación

gen producto funcional

“Dogma central de la Biología Molecular”

5

Problema - contexto

� Ciencias ómicas

� Bioinformática y descubrimiento de biomarcadores


(datos de expresión)

6

Problema – Datos

Datos de expresión génica:

� tecnología de microarray (transcriptómica)


Problema – Datos


� datos de microarray


genes

condiciones experimentales (muestras)

valor de expresión del gen Gx bajo la condición Cy

8

Problema – Datos


� mediante otras tecnologías: vía RT-PCR, RNA-seq


Problema - Planteamiento

Flujo de trabajo



Flujo de trabajo



Flujo de trabajo

� Acceso a los datos:� Repositorios públicos: NCBI – GEO datasets

� Procesamiento de los datos: Babelomics

� Nomenclatura y anotaciones de genes

� Análisis (Biclustering)

� Interpretación o análisis funcional: � GO (Gene Ontology)


Guía

1. Introducción

2. Estado del arte


1) SScorr

2) BISS

3) GoldBinch


5. Contribuciones


Biclustering - definciones

Biclustering (capítulo 4, pág. 39)

� Aprendizaje no supervisado

� Importancia con datos de expresión

� Búsqueda de patrones locales

� Problema NP-completo (~ “clique”)
























� Clustering “tradicional” vs. Biclustering

� Objetivos

� Patrones

� Solapamiento*

� Estructura de soluciones


a)

b)

a)

b)

Clustering: genes Biclustering: genes/condiciones

18




4 clusters

c1

c2

c3

c4(zona celeste)




3 biclusters

b1

b2

b3

4 clusters

c1

solape

c2

c3

c4(zona celeste)


Ejemplo de bicluster:

Introducción Estado del arte Propuestas y resultados Conclusiones Contribucionesg

ene

s

condiciones o muestrasbicluster

21

(perfil de expresión bicluster)


Patrones: con evoluciones coherentes

� de desplazamiento



Patrones: con evoluciones coherentes

� de escalado


Biclustering - algoritmos

� Gran variedad de algoritmos

� Taxonomía según� Técnica empleada

� Patrones que encuentra

� Criterio de evaluación

� Dificultades

� Comparación entre algoritmos

� Disponibilidad de código (Tabla Software* pág. 61)



� Algoritmo “fundacional” Cheng-Church (ChCh)

� Medida MSR como medida de calidad

� Otros algoritmos clásicos/referencia:

� FLOC

� ISA

�OPSM

� xMotifs

� Samba



� Algoritmos basados en metaheurísticas

� MSR como medida de calidad

� Diversas técnicas (SEBI)

� Basados en las correlación

� BCCA

� BICLIC

� Otros:

� Plaid Model, Spectral, BiMAX, …

� Datos temporales: eCCC y CCC-biclustering


Integración de información

Apuntes sobre integración (capítulo 5, pág. 63)

� Anotación de genes

� Información sobre genes:

� GO (Gene Ontology): ontología de genes

� Tres ramas: BP, MF, CC

� KEGG, InterPro

� Medidas sobre GO� IC-measures

� Edge-based measures


Guía

1. Introducción

2. Estado del arte


1) SScorr

2) BISS

3) GoldBinch


5. Contribuciones


Motivación

� La medida MSR presenta defectos a la hora de capturar biclusters con patrones de escalado

� Aguilar, J.S. Shifting and scaling patterns from gene expression data. Bioinformatics, 21(20):3840--3845 2005.

� Algoritmo basado en una metaheurística

� Independencia: motor de búsqueda y criterio evaluación

� Búsqueda dispersa o Scatter Search: Fred Glover


Búsqueda dispersa

Búsqueda dispersa (capítulo 6, pág. 69)

� Metaheurística basada en poblaciones

� Evolución de un conjunto representativo de soluciones

� Intesificación (mejora la calidad de soluciones)

� Método de la Mejora

� Actualización conjunto de referencia

� Diversificación (evita mínimos locales)

� Método de diversificación

� Reconstrucción del conjunto de referencia


Búsqueda dispersaIntroducción Estado del arte Propuestas y resultados Conclusiones Contribuciones31



Búsqueda dispersaIntroducción Estado del arte Propuestas y resultados Conclusiones Contribuciones

intensificación

diversificación

34

Búsqueda dispersa

Búsqueda dispersa

� Codificación de soluciones

� Método de diversificación

� Construcción y reconstrucción de RefSet

� Generación soluciones

� Combinación

�Método de la Mejora


Guía

1. Introducción

2. Estado del arte


1) SScorr

2) BISS

3) GoldBinch


5. Contribuciones


1) SScorr

Correlaciones lineales I (capítulo 7, pág. 82)


Correlación media 0.003 Correlación media 1

37

1) SScorr

� Función objetivo

� Método de la mejora:

� Búsqueda local

� Elimina genes con correlación negativa

� Mejora término de la correlación


volumen

desviación estándar

1) SScorr

� Método de la mejora:


Correlación media 0.0083 Correlación media 1

39

1) SScorr

� Experimentación (capítulo 9, pág. 103)

� Tres conjuntos de datos:

� Yeast, Lymphoma

� GaschYeast

� Tabla con valores descriptivos:

� volumen, correlación – MSR

� Representación gráfica de los biclusters


1) SScorr

� Valores de referencia: volumen, correlación – MSR


Patrones de escalado

41

1) SScorr

� Comparativa

� Datos de GaschYeast

� Criterio comparación: porcentaje de biclusters enriquecidos

� Estudio biológico de biclusters


1) SScorr

“Se dice que un bicluster está enriquecido si su grupo de genes está asociado a un término GO según un umbral”

� GO (Gene Ontology)

� Grupo de genes presente en un término� Por cada término un test de Fisher

� Contraste múltiple de hipótesis (correcciones de Bonferroni)

� Herramientas� Funcassociate

� AGO (GeneMerge)


(sección 9.4, pág. 108)

1) SScorr

� Conclusiones� Búsqueda dispersa + correlación

� Se encuentran biclústers con patrones de escalado

� Ideas: dificultades en� Datos, algoritmos

� Comparación� Técnica no supervisada:

Análisis “experto”/biológico resultados

� Decisión de no usar datos sintéticos� Evitar sobreajuste en la experimentación


Guía

1. Introducción

2. Estado del arte


1) SScorr

2) BISS

3) GoldBinch


5. Contribuciones


2) BISS

El contexto biológico del problema nos motiva:

� Patrones de activación-inhibición no estudiados� [104] Tao Zeng et al. Maximization of negative correlations

in time course gene expression data for enhancingunderstanding of molecular pathways. Nucleic Acids Research,38(1):e1, 2010

� Análisis de los resultados en profundidad


2) BISS

Correlaciones lineales II (capítulo 7, pág. 85)


Modificación en el cálculo de la correlación media

47

2) BISS


� Método de la mejora

� Se establece un umbral de correlación

� Procedimiento automático de elección


2) BISS



Correlación media:• Antes: 0.70• Después: 0.98

49

2) BISS


� Tres conjuntos de datos

� GaschYeast, GDS1116 (levadura), Alzheimer

� Estudio y ajuste parámetro función objetivo

� Comparación con

� Algoritmos clásicos

� Algoritmos basados en correlación

� Filtrados

� Estudio biológico algunos biclusters


2) BISS

� Configuración de parámetros



2) BISS

� Configuración de parámetros

� Elección del umbral de correlación (automático)


2) BISS

� Comparación con algoritmos clásicos


correlación con y sin valor absoluto

53

2) BISS



2) BISS


Debido a la influencia del tamaño de los biclusters en el estudio del enriquecimiento [16, 84, 36] se filtran aquellos biclusters con más de 50 genes [16]

[16] Bhattacharya et al. Bi-correlation clustering algorithm fordetermining a set of co-regulated genes. Bioinformatics, 25(21):2795--2801, 2009.


2) BISS



2) BISS

� Comparación con algoritmos basados en correlación


correlación con y sin valor absoluto

57

2) BISS



2) BISS



2) BISS


� Dificultad en el análisis: volumen de los biclusters


2) BISS

� Estudio biológico algunos biclusters


2) BISS

� Conclusiones:

� Heterogeneidad de los distintos algoritmos

� Ideas:

� Contexto del problema

� Ficheros de anotaciones

� Estructura de GO


Guía

1. Introducción

2. Estado del arte


1) SScorr

2) BISS

3) GoldBinch


5. Contribuciones


3) GoldBinch

� Motivación� La integración entre distintas fuentes de información es

una de las tendencias en bioinformática

� Manejo de los ficheros de anotaciones

� Visto en clustering pero aún no en biclustering� [97] Marie Verbanck et al. A new unsupervised gene

clustering algorithm based on the integration of biological knowledge into expression data. BMC Bioinformatics, 14(1):42, 2013


3) GoldBinch

� Ficheros de anotaciones

� Gen asociado a términos de un vocabulario (GO)


3) GoldBinch

� Entrada: Matriz de expresión + Fichero anotaciones


3) GoldBinch

� Idea:

� Los ficheros de anotaciones introducen información de tipo biológico

� Esta información proporciona un sesgo en el proceso de búsqueda

� Ampliar la función objetivo con un término que controle dicha información


3) GoldBinchIntroducción Estado del arte Propuestas y resultados Conclusiones Contribuciones

Datos de entrada:• Matriz expresión• Fichero anotaciones

68

3) GoldBinch

� Función objetivo (capítulo 8, pág. 91)

� Rango de parámetros

� Necesidad de los tres términos


volumencorrelación media

(valor absoluto)

término integración

información biológica

69

3) GoldBinch


� Independiente de la función objetivo

� Permite experimentar con varias definiciones

� Basado en permutaciones


3) GoldBinch

� Término integración de la información biológica� FracGO

� Basada en la “fracción relevante de un bicluster en un término GO”

� SimNTO� Adaptación de la medida GO propuesta en:

[72] Mistry M. et al. Gene ontology term overlap as a measure of gene functional similarity. BMC Bioinformatics, 9(1):327, 2008

� Ambas utilizan únicamente los ficheros de anotaciones*


3) GoldBinch

� FracGO

� Dado un término GO para el que el bicluster está enriquecido, se mide la proporción de genes asociados a dicho término GO.

� Se calcula la media de dicha proporción para todos los términos GO enriquecidos (p-value = 0.05)


valores entre 0 y 1

72

bi = {g1, …, g7, g8, g9, g10} � 8/10

3) GoldBinch

� SimNTO

� Se basa en el “solape 2 a 2” entre genes [72]


términos anotados asociados a g1

73

3) GoldBinch

� SimNTO

� Se basa en el “solape 2 a 2” entre genes [72]

� Media de los solapes (simetría)


términos anotados asociados a g1

valores entre 0 y 1

74

3) GoldBinch


� Objetivos

� La integración de información mejora los resultados

� Diferencias entre SimNTO y FracGO

� Dos conjuntos de datos

� GDS1116, GDS2914 (S. cerevisiae)

� Ficheros de anotaciones generados con Babelomics4.0

� Nuevas cuestiones asociadas



estudio parámetros3 ramas para evitar

sesgo de FracGOtérminos GO por bi.

“Sin integración”

76


estudio parámetros3 ramas para evitar

sesgo de FracGOtérminos GO por bi.

“Sin integración”

77


� Algoritmos clásicos

78

3) GoldBinch

� Imagen tablas (enriquecimiento) – GDS1116


3) GoldBinch

� Imagen tablas (enriquecimiento) – GDS2914


3) GoldBinch

� La integración de información mejora los resultados

� 211, 212, 221 frente a 210, 220

� Frente a los algoritmos clásicos

� Los biclusters de FracGO

� Más grandes

� Tienen un término GO por bi.

� Hipótesis

� Capturan términos altos en GO y por tanto irrelevantes


3) GoldBinch

� SimNTO� Inconvenientes: asociado a ficheros* de GO

� Ventajas: rápido

� FracGO� Inconvenientes

� mayor coste computacional

� biclusters capturan un solo término GO - (Hipótesis anterior)

� Ventajas� No depende de una estructura en forma de árbol, se puede

aplicar a ficheros de anotaciones distintos de GO (KEGG, InterPro)


3) GoldBinch

� Ejemplo en el que se puede aplicar FracGO pero no SimNTO

� Ficheros de anotaciones distintos de GO: KEGG, InterPro


3) GoldBinch

� Cómo se construyen los ficheros de anotaciones� Influye la calidad de la información a la hora de realizar la

integración


3) GoldBinch

� Cómo se construyen los ficheros de anotaciones� Influye la calidad de la información a la hora de realizar la

integración


3) GoldBinch

� FracGO

� Inconvenientes


� Estudio cualitativo de biclústers (GDS1116)

� Reactome:

� Encuentra rutas asociadas para todos los biclusters de SimNTO, dos de Corr y ninguno de FracGO

� Gene Term Linker: metagrupos de genes con significado biológico coherente en GO

� Revigo: agrupa términos GO según similitud


“funcionalidad biológica irrelevante”

3) GoldBinch

� FracGO

� Inconvenientes



� Reactome refuerza la hipótesis

� Gene Term Linker+Revigo la confirman


“funcionalidad biológica irrelevante”

3) GoldBinch

� FracGO

� Inconvenientes



� Reactome refuerza la hipótesis

� Gene Term Linker+Revigo la confirman


3) GoldBinch

� Otras medidas GO: SimGIC, SimUI

� Motivos del estudio


3) GoldBinch

� Conclusiones

� Integración de información biológica en biclustering

� Ideas

� Se puede extender la misma idea a otros algoritmos

� El proceso de experimentación didáctico:

� nuevas preguntas/hechos


Guía

1. Introducción

2. Estado del arte


1) SScorr

2) BISS

3) GoldBinch


5. Contribuciones


Resumen

� SScorr� Búsqueda dispersa + correlación

� Experimentación estándar

� BISS� Mejora el algoritmo anterior (patrones AI)

� Experimentación más extensa� Contexto biológico

� GoldBinch� Integración de información biológica

� Experimentación exhaustiva y didáctica


Plan de futuro

� Continuación natural: biclustering� Mejoras en el esquema de Búsqueda Dispersa

� Nueva codificación de soluciones

� Nuevo método de la combinación: operadores de cruce

� Visión multiobjetivo

� Comparativa entre algoritmos de biclustering� Partiendo de una visión más amplía de GO

� Estudiar el efecto de integración en otros algoritmos


Plan de futuro

� Otros problemas relacionados

� Datos de microRNA

� Algorítmicamente un problema de biclustering

� Adaptar el algoritmo

� Referencias base [80, 37]

� Clustering sobre redes haciendo hincapié en el solape

� Ideas parecidas

� Experimentación muy similar

� Referencias base [78, 87] - Cytoscape


Guía

1. Introducción

2. Estado del arte


1) SScorr

2) BISS

3) GoldBinch


5. Contribuciones


Difusión de resultados

� Tres artículos JCRs asociados a las propuestas:

� Resultados intermedios presentados en congresos:

� 7 internacionales y 6 nacionales




� SScorr

BioData Mining, 2011, 4, 3. DOI: 10.1186/1756-0381-4-3

� Impact Factor: 1.54*

� Cuartil: Q2 (Mathematical and Computational Biology)

� Citas: (23 citas según Google Scholar (01/05/2015))




� BISS

Applied Soft Computing. (En prensa). DOI: 10.1016/j.asoc.2015.06.019

� Impact Factor: 2.6

� Cuartil: Q1 (Computer Science and Artificial Intelligence)




�GoldBinch

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 (Computer Science, Theory and Methods)



� Resultados intermedios presentados en congresos:

� 7 internacionales y 6 nacionales

� IDEAL’07 - MAEB’07 - EvaBio’07 (CAEPIA)

� PRIB’09 - EvaBio’09 (CAEPIA)

� ISDA’09

� SAC’10

� EvoBIO’10 (EvoStar) - MAEB’10

� NaBIC’11

� ISDA’11 - BBC’11(Benelux Bioinformatics Conference)

� JdBI2014 (XII Symposium on Bioinformatics)


Otros méritos - CV

� Estancia CRP-Santé Luxemburgo

� Dr. Francisco Azuaje - (julio-agosto 2012)

� Financiada por Plan Propio (Universidad de Sevilla)

� Resultados de Minería de Datos no relacionados con el trabajo presentado en la tesis

� IEA/AIE’06, JISBD’06, DS’06


Otros méritos - CV

� Financiación

� Ministerio de Educación y Ciencia

� TIN2007-68084-C-00

� TIN2011-28956-C02-02

� Junta de Andalucía

� P12-TIC-1728


Minería de Datos

Computación Evolutiva

Bioinformática

• multi-disciplinar• inter-disciplinar• trans-disciplinar

103

Final

Muchas gracias por su atención

104

106

Anexo-1

� Estudio de parámetros (propuesta GoldBinch)

término integración

información biológica

experimentación extra (no relevante)experimentación

107

Anexo-2

� Solape entre biclusters� Evitar encontrar siempre misma solución

� Solape entre biclusters biológicamente relevante

� Estudiado efecto en función objetivo en ISDA’09

� Dispersión en Búsqueda dispersa/datos reales

� Experimentación: análisis resultados

108

Anexo-3

� Algoritmos de biclustering� ChCh: búsqueda voraz - MSR � FLOC: variación de ChCh� ISA: incremental - valores medios columnas/filas� OPSM: reordenación de filas y columnas según orden� xMotifs: valores constantes� Samba: teoría de grafos� Metaheurísticas: SEBI (GA+MSR)� BCCA: correlación Person – búsqueda según umbral� BICLIC: expansión de una semilla� Plaid Model, Spectral, BiMAX, …� eCCC y CCC-biclustering (Ukkonen – datos temporales)

109

Anexo-4

� Experimentación SScorr: (sección 9.4, pág. 108)

Documents

Biclustering sobre datos de expresión génicajanepo/doc/TESIS-presentacion-janepo.v2.pdf · 1. Introducción 2. Estado del arte 3. Propuestas y resultados 1) SScorr 2) BISS 3) GoldBinch