La minería de datos en
bioinformática
Dra. Rocío Romero Zaliz
M4M Lab
www.m4m.es
[email protected]
Dept. Ciencias de la Computación e Inteligencia Artificial,
Universidad de Granada
Disciplinas
•
•
•
•
Inteligencia Artificial (AI)
Minería de Datos (DM)
Minería de Textos (TM)
Descubrimiento de
información (KD)
• Aprendizaje Automático (ML)
Inteligencia Artificial
• Automatizar tareas que
requieran un comportamiento
inteligente:
–
–
–
–
–
–
Control
Planificación y organización
Escritura manual
Lenguaje natural
Reconocimiento del habla
Reconocimiento de caras
Aprendizaje automático
• Desarrollo de técnicas y
algoritmos que permitan a
los ordenadores “aprender”
– Teoría de juegos
– Análisis de mercados
– Detección de fraudes en
tarjetas de crédito
– Motores de búsqueda
– Bioinformática
Aprendizaje automático
•
•
•
•
Aprendizaje supervisado
Aprendizaje no supervisado
Aprendizaje semi-supervisado
Aprendizaje por refuerzo
Minería de datos
• “Proceso de búsqueda de patrones automático
en grandes volúmenes de datos”
• Clasificación
• Reglas de asociación
• Agrupamiento de datos
• Estadística
Minería de textos
• Text data mining
– “proceso de adquirir
información de calidad a
partir de un texto”
• Objetivos
–
–
–
–
Categorización de texto
Agrupamiento de textos
Extracción de conceptos
Sumarización de
documentos
Agrupamiento de datos
Agrupamiento de datos
• El agrupamiento de datos o data clustering
consiste en la clasificación de objetos similares
en diferentes grupos.
• Más precisamente, consiste en particionar un
conjunto de datos en subconjuntos o clusters
de tal manera que estos tengan “algo en
común”.
– Proximidad
– Similitud
• Aprendizaje no supervisado
Tipos de clustering
• Particionales
• Jerárquicos
– Aglomerativos
– Divisibles
Clustering particional
Clustering jerárquico
Aglomerativo
Divisible
Objetivo
• Minimizar la distancia intracluster
• Maximizar la distancia entre clusters
Propiedades de los clusters
• Numéricos vs. Categóricos
Propiedades de los clusters
• Disjuntos vs. No disjuntos
Propiedades de los clusters
• Completos vs. Incompletos
Formas de los clusters
Particionales o no jerárquicos
Ej: K-means
K-means
•
•
•
•
•
Particional
Distancias: ej: euclídea
Necesita el valor de k (#clusters)
Búsqueda de prototipos
Sensible a outliers
K-means
• Ubicar k (2) puntos en el espacio representado por los
objetos a ser agrupados. Estos k puntos son los
centroides iniciales de cada grupo
K-means
• Asignar cada objeto al grupo que esté más cercano a su
centroide
K-means
• Recalcular la posición de los k centroides
K-means
• Repetir pasos 2 y 3 hasta que los prototipos ya no
varíen
De esta manera se minimiza la distancia intracluster
según la metrica dada
K-means
http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html
Distancias
• Distancia euclidiana
– s
• Distancia Manhattan
– f
• Distancia Minkowsy
– d
Distancias
• Coeficiente de correlación de Pearson
–
• σXY la covarianza de (X,Y)
• σX y σY las desviaciones típicas de las distribuciones marginales
• Coeficiente de correlación de Spearman
– j
• Los coeficientes oscilan entre -1 y +1, indicándonos
asociaciones negativas o positivas respectivamente, 0
cero, significa no correlación pero no independencia.
K-means
Jerárquicos
Ej: Single-linkage
Single-linkage
• Jerárquico
• Aglomerativo
• Si hay un error en algún paso no se puede
volver atrás …
Single-linkage
• Dado un conjunto de N (5) elementos a ser
agrupado y una matriz de distancia (o similitud)
de N x N:
d
1
2
3
4
5
1
0
5
6
10
13
2
5
0
1
5
8
3
6
1
0
4
7
4
10
5
4
0
3
5
13
8
7
3
0
Single-linkage
• Comenzar por asignar cada item a un cluster.
• Tenemos 5 clusters
• Sean las distancias entre los clusters las mismas que
entre los elementos de cada cluster
d
1
2
3
4
5
1
0
5
6
10
13
2
5
0
1
5
8
3
6
1
0
4
7
4
10
5
4
0
3
5
13
8
7
3
0
Single-linkage
• Encontrar el par más cercano de clusters y
unirlo en un único cluster.
• Tenemos 4 clusters
d
1
2
3
4
5
1
0
5
6
10
13
2
5
0
1
5
8
3
6
1
0
4
7
4
10
5
4
0
3
5
13
8
7
3
0
Single-linkage
• Calcular las distancias entre el nuevo cluster y
los viejos clusters
d
1
2-3
4
5
1
0
5
10
13
7
2-3
5
0
4
7
0
3
4
10
4
0
3
3
0
5
13
7
3
0
d
1
2
3
4
5
1
0
5
6
10
13
2
5
0
1
5
8
3
6
1
0
4
4
10
5
4
5
13
8
7
Single-linkage
• Repetir los pasos 2 y 3 hasta que todos los
elementos se encuentren en el mismo cluster
de tamaño N
Single-linkage
http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletH.html
Linkage criteria
• Determina la distancia entre dos conjuntos
de observaciones como una función de
distancia entre dos elementos.
Nombre
Maximum or complete
linkage clustering
Minimum or single-linkage
clustering
Mean or average linkage
clustering, or UPGMA
Fórmula
Redes Neuronales
Redes Neuronales
“Las redes neuronales artificiales son
simulaciones de estructuras
cognitivas de procesamiento de
información, basadas en modelos
de las funciones cerebrales”
Redes Neuronales
Redes Neuronales
• Una NN tiene la capacidad de generalización,
es capaz de aprenderse las características de
una categoría general de patrones, basándose
en una serie de ejemplos específicos de la
categoría.
– Tolerantes a fallas.
• Las redes neuronales no se programan, más
bien aprenden o se entrenan en la tarea que ha
de computarse.
• Ciertas redes aprenden por ensayo y error.
Perceptrón simple
• Estructura
– Un Perceptron consta de dos niveles o
capas.
– 1er. Nivel: unidades de entrada,
denominadas unidades sensoriales
– 2do. Nivel: unidades de salida, denominadas
unidades de asociación, cuyas entradas son
las salidas de las unidades de entrada
ponderadas por unos pesos.
– Las unidades transmiten la señal que
aparece en su entrada.
Perceptrón simple
http://lcn.epfl.ch/tutorial/english/perceptron/html/index.html
• La NN tiene dos entradas y
una salida, todas binarias.
• La salida es:
1
S 
0
w1  x1  w 2  x 2  u  h
w1  x1  w 2  x 2  u  h
Perceptrón simple
• Seteo los pesos a:
– W1 = -0.6
– W2 = 0.2
– U=0
• Pruebo con:
– X1 = 0
– X2 = 0
S  x 1  w 1  x 2  w 2  (  1)  u  0  0 . 2  0  (  0 . 6 )  1  0  0
Perceptrón simple
• Seteo los pesos a:
– W1 = -0.1
– W2 = 0.2
– U=0
• Pruebo con:
– X1 = 1
– X2 = 1
S  x 1  w 1  x 2  w 2  (  1)  u  1  0 . 2  1  (  0 . 1)  1  0  0 . 1
Cálculo de error
• El error se calcula restando al valor esperado
el valor obtenido
w ij new  w ij old  C ( t j  x j ) a i
•
•
•
•
C (learning rate)
ti valor esperado
xi valor obtenido
ai valor de entrada
Forward propagation
1.
2.
3.
4.
5.
6.
7.
Setear los pesos y el umbral a valores aleatorios entre -1.0 y 1.0 (lo hace
automaticamente)
Setear el patrón de entrada a las neuronas de la capa de entrada
•
Activar cada neurona de la capa siguiente multiplicando el peso de las
conexiones que llegan a esta neurona con la salida de los valores de
las neuronas precedentes
•
Sumar estos valores
•
Pasar el resultado a la función de activación, la cual calcula el valor de
salida a esta neurona
Repetir este proceso hasta que se llegue a la capa de salida
Comparar el patrón de salido con el patrón esperado y calcular el valor de
error
Cambiar los pesos y el umbral de acuerdo a este error
Ir al paso 2
El algoritmo termina cuando todos los patrones de salida concuerdan con
los patrones esperados
Probemos con …
•
http://lcn.epfl.ch/tutorial/english/perceptron/html/index.html
Probemos con …
AND
0
1
0
0
0
1
0
1
Probemos con …
Probemos con …
Probemos con …
Probemos con …
Probemos con …
Perceptrón simple
• Linealmente separables
Probemos con XOR
Probemos con XOR
Redes Multicapa
Redes Multicapa
• Más lentas
• Más poderosas
http://neuron.eng.wayne.edu/bpFunctionApprox/bpFunctionApprox.html
Probemos con …
Probemos con …
Redes neuronales: predicción de genes
Mapa auto-organizado
SOM
Mapa auto-organizado
• SOM (Self-Organizing Map)
• Redes de Kohonen
• Red neuronal distribuida de forma regular en
una rejilla de, normalmente, dos dimensiones,
cuyo fin es descubrir la estructura subyacente
de los datos introducidos en ella:
– no supervisada
– competitiva
Mapa auto-organizado
• La información de
entrada no es recibida
por una única neurona y
además influencia otras
neuronas en la vecindad.
• Esta organización resulta
en una clase de mapa en
donde las neuronas con
funciones similares se
encuentran juntas.
Mapa auto-organizado
• A lo largo del entrenamiento de la red, los
vectores de datos son introducidos en cada
neurona y se comparan con el vector de
peso característico de cada neurona
• La neurona que presenta menor diferencia entre
su vector de peso y el vector de datos es la
neurona ganadora y ella y sus vecinas verán
modificados sus vectores de pesos.
Mapa auto-organizado
• http://davis.wpi.edu/~
matt/courses/soms/ap
plet.html
Mapa auto-organizado
• http://fbim.fhregensburg.de/~saj39
122/jfroehl/diplom/eindex.html
Mapa auto-organizado
Classification of samples by SOM analysis and
K-means clustering. SOM component
planes are shown for a) 42 DLBCL samples
and three DLBCL cell lines (OCILy3,
OCILy10 and OCILy1). SOM map size is (22
× 14) and the color scale of SOM component
plane represented the mean ratio in each
map node, and red indicates high
expression, blue indicates low expression.
See supplementary information for full
data. b) K-means clustering of SOM, mean
SOM component planes for DLBCL, FL and
CLL. The cluster numbers are given, and the
genes contained within each SOM node and
K-means cluster are listed in the web
supplement [13], selected genes from
clusters 10, 11 and 1, 7, 9 are listed in
table ​table11.
BMC Bioinformatics. 2002; 3: 36.
Published online 2002 November 24. doi:
10.1186/1471-2105-3-36.
Support Vector Machines
(SVM)
SVM
• Método de aprendizaje supervisado usado
para clasificación (y regresión: SVR).
• Teniendo dos conjuntos de datos como
dos vectores en un espacion ndimensional, un SVM construirá un hiperplano que separa ese espacio que
maximice el margen entre los dos
vectores.
SVM
• Para calcular este margen, dos hiperplanos paralelos son construidos, uno en
cada lado del hiper-plano separador, los
cuales son empujados hacia los conjuntos
de datos.
• Una buena separacion se consigue
cuando el hiper-plano tiene mayor
distancia a los puntos de los dos
conjuntos de datos.
SVM
SVM
• Clasificador no-lineal usando kernels (~transformadas
integrales).
• Similar al lineal pero cada producto escalar es
reemplazado por una función no-lineal de kernel.
• Esta transformación trabaja en un espacio de alta
dimensionalidad, y el clasificador es un hiper-plano en
este espacio, el cual puede ser no-lineal en el espacio
original.
SVM
• El espacio de características es el espacio
de Hilbert de dimensión infinita.
–
–
–
–
–
Polynomial (homogeneous):
Polynomial (inhomogeneous):
Radial Basis Function: γ > 0,
Gaussian Radial basis function:
Hyperbolic tangent:
todos) κ > 0 y c < 0
, para algún (no
SVM
• http://svm.dcs.rhbnc.a
c.uk/pagesnew/GPat.
shtml
SVM
• http://www.eee.met
u.edu.tr/~alatan/Co
urses/Demo/Applet
SVM.html
Optimización Combinatoria
Optimización Combinatoria
•
•
•
•
•
Asignación de invitados a una boda
Llenar el maletero del coche
Diseñar una ruta en un viaje
Fijación de horarios en un centro
Creación de un menú semanal
Optimización Combinatoria
• A veces es difícil encontrar una solución
posible.
• Existen un número muy elevado de
soluciones posibles.
• De todas las soluciones una es la
“óptima”.
Optimización Combinatoria
• Algoritmos exhaustivos o exactos.
• Agloritmos heurísticos.
– Un método heurístico es un procedimiento para
resolver un problema de optimización bien definido
mediante una aproximación intuitiva, en la que la
estructura del problema se utiliza de forma inteligente
para obtener una buena solución.
– Las heurísticas no ofrecen en general garantas de
obtención de una solución optima, lo que no implica
que no puedan obtenerse.
Meta-Heurísticas
• Una meta-heurística es un método heurístico
para resolver un tipo de problema
computacional general.
• Se usan cuando:
– ...no es posible implementar el método optimo.
– ...no se tiene un algoritmo o heurística específica que
de una solución satisfactoria.
Meta-Heurísticas
•
•
•
•
•
•
Local search / Busqueda local
Simulated annealing / Recocido simulado
Swarm intelligence / Inteligencia de enjambre
Tabu search / Busqueda tabu
Genetic algorithms / Algoritmos geneticos
Ant colony optimization / Colonias de hormigas
Algoritmos Genéticos
• Los Algoritmos Genéticos (AGs) son métodos
adaptativos que pueden usarse para resolver
problemas de optimización.
• Estan basados en el proceso genético de los
organismos vivos.
– A lo largo de las generaciones, las
poblaciones evolucionan en la naturaleza de
acorde con los principios de la selección
natural y la supervivencia de los mas fuertes,
postulados por Darwin.
Algoritmos Genéticos
• Por imitación de este proceso, los AGs son
capaces de ir creando soluciones para
problemas del mundo real.
• La evolución de dichas soluciones hacia valores
óptimos del problema depende en buena
medida de una adecuada codificación de las
mismas.
Algoritmos Genéticos
• Los AGs usan una analogía directa con el
comportamiento natural.
– Trabajan con una población de individuos, cada uno
de los cuales representa una solución factible a un
problema dado.
– A cada individuo se le asigna un valor o puntuación,
relacionado con la bondad de dicha solución.
– Cuanto mayor sea la adaptación de un individuo al
problema, mayor será la probabilidad de que el
mismo sea seleccionado para reproducirse, cruzando
su material genetico con otro individuo seleccionado
de igual forma.
Algoritmos Genéticos
– Este cruce producirá nuevos individuos,
descendientes de los anteriores, los cuales
comparten algunas de las características de sus
padres.
– Cuanto menor sea la adaptación de un individuo,
menor será la probabilidad de que dicho individuo
sea seleccionado para la reproducción, y por tanto de
que su material genético se propague en sucesivas
generaciones.
Algoritmos Genéticos
Algoritmos Genéticos
http://www.obitko.com/tutorials/genetic-algorithms/example-function-minimum.php
Algoritmos Genéticos
http://www.obitko.com/tutorials/genetic-algorithms/example-3d-function.php
Algoritmos Genéticos
http://www.obitko.com/tutorials/genetic-algorithms/tsp-example.php
Algoritmos Genéticos
Computación molecular
(bioinformatica “al vesre”)
Computación molecular
• La computación basada en ADN consiste en usar
moléculas de ADN en vez de procesadores basados en
silicio.
• Ventajas:
– Paralelismo de las hebras de ADN. Muchos de los problemas
considerados intratables, pueden ser resueltos haciendo un
búsqueda exhaustiva sobre todas las soluciones posibles. La
densidad de información almacenada en hebras de ADN y la
facilidad de construir muchas copias de ellas puede convertir
esas búsquedas en una posibilidad real.
– La complementariedad de bases. Cuando se unen dos hebras
(en condiciones ideales) se sabe el opuesto a cada miembro, no
hay necesidad de verificarlo.
Computación molecular
• Un camino hamiltoniano en un grafo es
un camino, una sucesión de aristas adyacentes,
que visita todos los vértices del grafo una sola
vez. Si además el último vértice visitado es
adyacente al primero, el camino es un ciclo
hamiltoniano.
• El problema de encontrar un ciclo (o camino)
hamiltoniano en un grafo arbitrario se sabe que
es NP-completo.
Computación molecular
• Leonard M. Adleman (1994):
– Un camino hamiltoniano es un camino que visita cada vértice
exactamente una vez. Un grafo que contiene un camino
hamiltoniano se denomina un ciclo hamiltoniano ó circuito
hamiltoniano si es un ciclo que visita cada vértice exactamente
una vez (excepto el vértice del que parte y al cual llega.
Computación molecular
1. Generar todas las posibles rutas.
2. Seleccionar los itinerarios que
comiencen y terminen en la ciudad
correcta.
3. Seleccionar los itinerarios con el
número correcto de ciudades.
4. Seleccionar los itinerarios que
contengan cada ciudad una sola
vez.
Computación molecular
• Parte I: Generar todas las posibles rutas.
– Estrategia: Codificar los nombres de las ciudades con pequñas
secuencias de ADN, luego codificar los itinerarios concatenando
estas secuencias.
Los Angeles
GCTACG
Chicago
CTAGTA
Dallas
TCGTAC
Miami
CTACGG
New York
ATGCCG
– Ej: la ruta L.A -> Chicago -> Dallas -> Miami -> New York será
GCTACGCTAGTATCGTACCTACGGATGCCG.
Computación molecular
Computación molecular
• Parte II: Seleccionar itinerarios que comiencen y
terminen en las ciudades correctas.
– Estrategia: Copiar y amplificar solamente aquellas secciones de
ADN que comiencen y terminen con las ciudades elegidas
usando PCR.
Computación molecular
• Parte III: Seleccionar itinerarios que contengan un
número correcto de ciudades.
– Estrategia: Ordenar el ADN por su tamaño y seleccionar solo
aquel con tamaño (largo) de 5 ciudades.
Computación molecular
• Parte IV: Seleccionar itinerarios que tengan el set
completo de ciudades.
– Estrategia: Filtrar el ADN por ciudad, una por vez.
Computación molecular
• Leer la respuesta:
– PCR gradual: usando un primers para ciudad y calculando el
tamaño de lo que se recupera se puede deducir el recorrido.
• Es exponencial con respecto a la cantidad de ADN.
– Para resolver el TSP para 200 ciudades se requeriría una
cantidad de ADN que pesa más que la propia tierra.
– Error acumulado es grande...
Preguntas…
http://www.m4m.es
Descargar

5 - genoma . unsam . edu . ar