Reynoso - Metaheuristicas aplicadas a la medicina y la biologia

0

No comments posted yet

Comments

Slide 1

Modelado de complejidad en biología, medicina y neurociencia Modelos evolucionarios y metaheurísticas Carlos Reynoso UNIVERSIDAD DE BUENOS AIRES http://carlosreynoso.com.ar

Slide 2

Objetivos Introducir al uso de algoritmos metaheurísticos en el dominio de la biología, la medicina y la neurociencia. Requisito: Presentación sobre algoritmo genético y otras mateheurísticas http://carlosreynoso.com.ar/algoritmo-genetico/ Inspeccionar herramientas apropiadas al dominio. Tipificar el campo de la Inteligencia Computacional Metaheurísticas, conjuntos toscos, minería de datos, redes neuronales, inteligencia de enjambre Describir estudios de caso y resultados obtenidos en IC y metaheurísticas. Sugerir otras líneas de investigación Referir documentación relevante.

Slide 3

Agenda Escenarios Usos de metaheurísticas en biología, medicina y neurociencia Referencias a casos Referencias a recursos Problemas pendientes y tendencias en modelos híbridos Síntesis y conclusiones

Slide 4

Escenarios Prevalencia de sistemas de decisión, clasificación, optimización y simulación. Reducción o conversión entre clases de problemas. Se usan metaheurísticas para encontrar soluciones aceptables a problemas duros. Difíciles o imposibles de resolver en tiempo polinómico.

Slide 5

Tiempo polinómico Existen varios órdenes de tiempo requeridos para ejecutar la resolución de un algoritmo. El tiempo polinómico denota una complejidad algo mayor a la intermedia en una escala que va desde el tiempo constante hasta el doble exponencial Tiempo constante (p. ej. determinar si un número es par o impar) Tiempo logarítmico (búsqueda binaria, p. ej. juegio 20 preguntas) Tiempo lineal (p. ej. encontrar el item más pequeño) Tiempo cuadrático Tiempo cúbico Tiempo polinómico Tiempo exponencial Tiempo factorial (p. ej. resolver TSP empleando fuerza bruta) Tiempo doble exponencial (p. ej. decidir valor de verdad en aritmética de Presburger) Eventualmente, reducción de problemas a otros problemas conocidos

Slide 6

Reducción de problemas Metálogo de la tetera Un matemático le propuso a un físico: “Supongamos que tienes una tetera vacía y un mechero de gas apagado. ¿Cómo haces para hervir agua?”. “Llenaría la tetera de agua, encendería el mechero y pondría la tetera sobre el fuego”. “Correcto”, dijo el matemático, “y ahora te propongo resolver otro problema. Supongamos que el gas está encendido y la tetera llena. ¿Cómo harías para hervir el agua?”. “Eso es aun más simple. Pondría la tetera sobre la llama”. “Erróneo”, exclamó el matemático. “Lo que tienes que hacer es apagar el fuego y vaciar la tetera. Esto reduciría el problema al problema anterior”. Esta es la razón por la cual cuando uno reduce un problema a otro ya resuelto, se dice que aplica el principio de la tetera (Vilenkin 1971: 11)

Slide 7

Recursos y casos – IC Cap. 2 – Computación evolucionaria en tratamiento de imágenes médicas Estrategia evolucionaria, AG y AG+RN para eliminación de ruido AG para mejora de imagen PG para mejora de contraste cromático AG para segmentación y detección de bordes de MRI Cap. 3 – Conjuntos toscos Detección de cáncer cervical con AG+conjuntos toscos Clasificación de imágenes, idem

Slide 8

Conjuntos toscos [rough sets] (1/2) Introducidos por Zdzisław Pawlak en los 80s. Computación granular, parte de inteligencia computacional. No confundir con conjuntos difusos [Lotfi Zadeh]. Se pregunta en qué medida un conjunto de objetos (p. ej. pixels en una imagen) se aproxima a otro conjunto de objetos de interés. La descripción de un objeto es una función vectorial cuyos valores representan atributos.

Slide 9

Conjuntos toscos [rough sets] (2/2) Se usa para descubrir dependencias entre datos, evaluar la importancia de rasgos, descubrir patrones, reducir objetos redundantes, buscar el subconjunto mínimo de rasgos y reconocer y clasificar objetos en gestión médica de imágenes. Un conjunto se define en términos de un par de conjuntos. Éstos representan la aproximación inferior y superior del conjunto original. Pueden ser nítidos [crisp] o borrosos [fuzzy] Es útil para inducción a partir de conjuntos de datos incompletos. Se usa como componente de soluciones híbridas en aprendizaje de máquina y data mining.

Slide 10

Recursos y casos - IC Análisis de mutación en cáncer con IC Análisis de datos espectrales en clínica proteómica Extracción de rasgos y eliminación de ruido con transformada de wavelet Segmentación de imágenes para citopatología Detección de pólipos y visualización en colonografía IC en oncología clínica

Slide 11

Recursos y casos - CE Interpretación de espectros analíticos Métodos de selección de rasgos para diseño de drogas Descubrimiento de interacciones genéticas y ambientales en enfermedades Identificación de redes de regulación genética Visualización fractal de secuencias de datos Predicción de estructuras de polipéptidos Alineamiento de estructuras de proteínas

Slide 12

Fogel & Corne – Casos (1/6)

Slide 13

Fogel & Corne – Casos (2/6)

Slide 14

Fogel & Corne – Casos (3/6)

Slide 15

Fogel & Corne – Casos (4/6)

Slide 16

Fogel & Corne – Casos (5/6)

Slide 17

Fogel & Corne – Casos (6/6)

Slide 18

Recursos y casos - CE Comprensión de secuencias de señales mediante aprendizaje de máquina. Modelado de redes genéticas mediante modelos estáticos y dinámicos. Predicción de la encima proteasa de HIV mediante máquina de vectores de soporte.

Slide 19

Máquina de vector de soporte Conjunto de métodos de aprendizaje supervisado. Análisis y descubrimiento de patrones para clasificación y análisis de regresión. Asigna cada input a una de 2 clases. Es un clasificador binario y lineal no determinista. Hay versión no lineal desde 1992. Un modelo de SVM es una representación de puntos en un espacio. De hecho, en un hiperplano.

Slide 20

Recursos y casos - CE Comparación de algoritmo evolucionario y algoritmo de enjambre de partículas para estimación de parámetros en sistemas bioquímicos. Elección de esquema de aprendizaje de máquina para la clasificación de datos biomédicos. Algoritmos meméticos para reconstrucción filogenética. Refinamiento de clustering difuso basado en AG para la clasificación no supervisada de cáncer.

Slide 21

Recursos y casos - CE Comparación de métodos de aprendizaje de máquina para la predicción de cáncer de mamas. Buscando motivos en secuencias de DNA mediante algoritmo de colonia de abejas. Gramáticas estocásticas independientes de contexto para análisis y síntesis de proteínas →

Slide 22

Jerarquía de la complejidad Chomsky Gramáticas regulares (Tipo 3). Pueden consistir sólo de reglas de re-escritura de tipo Ab, o AbC. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas deterministas de estado finito. Estos autómatas no tienen memoria. Reconocen o generan lenguajes regulares. Gramáticas independientes de contexto (Tipo 2). Sólo tienen reglas de forma A, y por lo tanto no tienen restricción en cuanto a la forma que pueden tomar las reglas de producción de la derecha. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas no deterministas de almacén o de pushdown (PDA). Estos autómatas tienen una memoria limitada y pueden, por ejemplo, llevar a cabo una comparación. Reconocen o generan lenguajes independientes del contexto. Gramáticas sensibles al contexto (Tipo 1). Pueden tener reglas de forma A, donde  no es un elemento vacío. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas ligados linealmente. Poseen una memoria auxiliar semi-infinita, proporcional a la cantidad de elementos que deben tratar. Reconocen o generan lenguajes sensibles al contexto. Gramáticas irrestrictas (Tipo 0). Son idénticas a las anteriores, excepto por el hecho que  puede ser nulo. Corresponden a los lenguajes y conjuntos susceptibles de ser tratados por máquinas de Turing. Poseen memoria irrestricta y pueden efectuar cualquier computación. Reconocen o generan lenguajes recursivamente enumerables.

Slide 23

Recursos y casos - CE Clasificación de mamogramas con mehateurísticas evolucionarias (programación genética cartesiana). Computación evolucionaria en otros campos de aplicación (transporte, finanzas, juegos, arte).

Slide 24

Recursos - Metaheurísticas

Slide 25

Bibliografía esencial (1/2) Bajar desde ftp://ftp.uwasa.fi/cs/report94-1/gaMEDICINEbib.pdf (Vínculo activo en este slide) +700 textos, 93 páginas Actualizado hasta marzo de 2012

Slide 26

Bibliografía esencial (2/2)

Slide 27

Recursos - Metaheurísticas Enumeración y descripción canónica de todas las metaheurísticas fundamentales

Slide 28

Referencias http://carlosreynoso.com.ar/modelado-de-complejidad-en-biologia/

Slide 29

Otros materiales relevantes* Introducción a la complejidad para medicina, biología y neurociencia Geometría y dimensión fractal Redes complejas, epidemiología y percolación Sistemas complejos adaptativos: Autómatas celulares Modelos basados en agentes Vida artificial Metaheurísticas biológicas Aprendizaje de máquinas y minería de datos en bioinformática (biología molecular [Weaver]) Neurociencia, complejidad y cognición * Hipervínculos activos en esta página

Slide 30

¿Preguntas? Carlos Reynoso UNIVERSIDAD DE BUENOS AIRES http://carlosreynoso.com.ar

Summary: Metaheuristicas evolucionarias basadas en la biologia

Tags: algoritmo genetico complejidad medicina

URL: