introducción al biclustering
DESCRIPTION
Introducción al Biclustering. Domingo Savio Rodríguez Baena Bioinformatics Research Group of Seville (BIGS) Dpto. de Lenguajes y Sistemas Informaticos Universidad de Sevilla. CLUSTERING vs BICLUSTERING. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/1.jpg)
Introducción al Biclustering
Domingo Savio Rodríguez BaenaBioinformatics Research Group of Seville (BIGS)
Dpto. de Lenguajes y Sistemas InformaticosUniversidad de Sevilla
![Page 2: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/2.jpg)
CLUSTERING vs BICLUSTERING
Objetivos Clustering: crear conjunto de elementos los cuales tengan alguna característica común.
Crear conjuntos de genes según su expresión bajo condiciones experimentales.
Crear conjuntos de condiciones según la expresión de los genes de un genoma.
PROBLEMA: el Clustering solo actúa bajo una dimensión.
LOS EXPERIMENTOS DEMUESTRAN QUE: en muchas ocasiones, un subconjunto de genes se co-expresan bajo un subconjunto de condiciones experimentales, mientras que con respecto a otras condiciones se pueden comportar de forma independiente.
![Page 3: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/3.jpg)
BICLUSTERING
Objetivo: buscar un subconjunto de genes que se co-expresen bajo un subconjunto de condiciones SUBMATRIZ.
![Page 4: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/4.jpg)
![Page 5: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/5.jpg)
Clasificación Técnicas Biclustering
Clasificación según varios criterios:
Tipo de biclusters que se puede encontrar
Estructura de los biclusters
Tipo de técnica algorítmica
Tipo de evaluación de los resultados
Ámbito de aplicación
![Page 6: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/6.jpg)
BICLUSTERING
Hay distintos tipos de Biclusters:
FORMADO POR VALORES CONSTANTES
![Page 7: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/7.jpg)
BICLUSTERING
FORMADO POR VALORES CONSTANTES EN FILAS O COLUMNAS:
![Page 8: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/8.jpg)
FORMADO POR VALORES COHERENTES:
BICLUSTERING
Modelo aditivo Modelo multiplicativo
![Page 9: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/9.jpg)
FORMADO POR VALORES DE EVOLUCIÓN COHERENTE:
BICLUSTERING
![Page 10: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/10.jpg)
BICLUSTERING
Nuestro objetivo puede variar en función de la estructura que queramos encontrar:
![Page 11: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/11.jpg)
TÉCNICAS DE BICLUSTERING
- Divide y Vencerás.
- Combinación de Clustering sobre filas y columnas
- Búsqueda voraz iterativa
- Búsqueda exhaustiva
- Identificación de parámetros de distribución
- Búsqueda estocástica
Existen técnicas muy variadas:
![Page 12: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/12.jpg)
Cheng & Church
Primer algoritmo, propiamente dicho, de Biclustering.
Parten de la suposición de que para que un subgrupo de genes y condiciones sea un bicluster, sus valores han de evolucionar al unísono, y esta característica estaba representada por un valor estadístico: The Mean Squared Residue (MSR).
Técnica de búsqueda voraz iterativa.
Y. Cheng and G. Church. Biclustering of expression data. In Proceedings of the 8thInternational Conference on Intelligent Systems for Molecular Biology (ISMB’00),pages 93–103, 2000.
![Page 13: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/13.jpg)
Cheng & Church. Definiciones I
IJIjiJijij aaaaaR )(
En una submatriz matriz A el residuo de un elemento aij es definido como:
iJaIja
ija
IJa
Donde:
= nivel de expresión del gen i en la condición j
= media de la fila i
= media de la fila j
= media de los elementos de A
![Page 14: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/14.jpg)
Cheng & Church. Definiciones II
-El Mean Squared Residue de una submatriz (I,J) es:
JjIi
IJIjiJij aaaaJI
JIH,
2)(1
),(
Este valor global H nos indica cómo se interrelacionan los datos de la matriz, es decir, si existe alguna coherencia en la evolución de sus valores o son aleatorios.
-Un valor alto de H significa que los datos no están correlacionados.
-Un valor bajo de H implica que la matriz está correlacionada.
-Si H(I,J)= 0 significaría que los datos de la matriz fluctúan al unísono.
![Page 15: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/15.jpg)
Cheng & Church. Ejemplo I
IJIjiJijij aaaaaR )(
R(1) = 1- 2 - 5.4 + 6.5 = 0.1
R(2) = 2 - 2 - 6.4 + 6.5 = 0.1: :: :
R(12) = 12 - 11 -7.4 + 6.5 = 0.1
Col Avg. 5.4 6.4 7.4
1 2 34 5 67 8 9
10 11 12
Matrix (M) Avg. = 6.5
H (M) = (0.01x12)/12 = 0.01
Si el 5 fuera reemplazado por 3, entonces la puntuación cambiaría a: H(M2) = 2.06
Si la matriz fuera generada aleatóriamente, entonces la puntuación sería aproximádamente: H(M3) = sqr(12-1)/12 = 10.08
![Page 16: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/16.jpg)
Cheng & Church. Ejemplo II
0
2
4
6
8
10
12
14
1 2 3
g1
g2
g3
g4
![Page 17: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/17.jpg)
Cheng & Church. Ejemplo III
0
2
4
6
8
10
12
14
1 2 3
g1
g2
g3
g4
![Page 18: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/18.jpg)
Cheng & Church. Algoritmo I
- Valor umbral de residuo, δ.
- Coeficiente de borrado múltiple, α.
- Número de biclusters a generar.
- Rango para la generación de números aleatorios.
Parámetros de entrada:
Pre-procesamiento de los datos: los huecos se rellenan con números aleatorios
![Page 19: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/19.jpg)
Cheng & Church. Algoritmo II
Fase 1): Borrado múltiple de nodos: se borran todas aquellas filas y columnas cuyo valor de MSR sea mayor que α * δ.
Fase 2): Borrado simple de nodos: se borra la fila o columna con el mayor valor de MSR.
Fase 3): Adición de nodos: se añaden aquellas filas o columnas cuyo MSR sea menor que δ.
Algoritmo iterativo formado por tres fases:
Al finalizar, se genera un solo bicluster. Para crear el siguiente, se sustituye el bicluster encontrado por números aleatorios en la matriz de entrada y a empezar de nuevo.
![Page 20: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/20.jpg)
Cheng & Church. Algoritmo III
![Page 21: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/21.jpg)
PROBLEMAS MSR I
-SHIFTING PATTERN
Efectos posibles en el comportamiento de los genes:
![Page 22: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/22.jpg)
PROBLEMAS MSR II
-SCALING PATTERN.
![Page 23: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/23.jpg)
J. Aguilar. Shifting and scaling patterns from gene expression
data. Bioinformatics,
21:3840–3845, 2005.
En este trabajo se demuestra de forma matemática que el residuo de Cheng y Church es altamente dependiente de la varianza del factor de escalado, lo que hace posible que un algoritmo basado en el MSR no tenga en cuenta este fenómeno cuando la varianza de los valores de expresión de los genes es demasiado alta.
![Page 24: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/24.jpg)
PROBLEMÁTICA BICLUSTERING
No existe una metodología clara para detectar los patrones de comportamiento en las bases de datos de expresión genética.
Las bases de datos son voluminosas.
Gran complejidad del problema planteado.
Métodos de evaluación de los biclusters obtenidos.
![Page 25: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/25.jpg)
APLICACIONES BICLUSTERING
EXPRESION GENETICA ANTE SUSTANCIAS TOXICAS
DIAGNOSTICO DE ENFERMEDADES
ESTUDIO DE ENFERMEDADES GENETICAS COMPLEJAS
FISIOLOGIA CELULAR
DETECTAR POLIMORFISMOS Y MUTACIONES
COMPORTAMIENTO DE LA CELULA ANTE FARMACOS
ESTUDIO DE LA EXPRESION GENETICA EN EL DESARROLLO
……
![Page 26: Introducción al Biclustering](https://reader035.vdocumento.com/reader035/viewer/2022081419/5681518b550346895dbfc280/html5/thumbnails/26.jpg)
FIN