Bioinformática

INTRODUCCION

El presente modulo se ha diseñado para facilitar el aprendizaje a los alumnos del curso de Bioinformática de la escuela de ingeniería de Sistemas e Informática, ya que es un curso que requiere de uso y manejo de Lenguajes de Programación para la construcción de Algoritmos Genéticos como: Lenguaje C, Java, etc. y contenidos de Biología, es por ello que el presente modulo brinda la información necesaria para que el alumno pueda comprender mejor el curso.

Bioinformática, utiliza tecnología de la información para organizar, analizar y distribuir información optima, con la ayuda de la biológica y poder solucionar problemas complejos de la vida real.

El modulo consta de 5 Actividades de Aprendizaje las cuales se detalla a continuación:

Actividad de Aprendizaje Nº 01: Computación basada en modelos naturales.- Aquí en primer lugar se define los modelos de Computación Bioinspirados, Características de los modelos Bioinspirados, modelos bioinspirados: Redes Neuronales, Algoritmos evolutivos, optimización basada en colonias de hormigas, Particle Swarm Optimization (PSO), Algoritmos Inmunológicos, Sistema Inmune Artificial, al finalizar los temas se mostrará una conclusión final, luego los alumnos observaran videos y elaboraran 4 conclusiones e investigaran sobre las diferentes aplicaciones que existen sobre modelos naturales.

Actividad de Aprendizaje Nº 02: Optimización mediante colonias de hormigas. Aquí el alumno empieza a conocer los algoritmos basados en poblaciones, combinaciones y mutaciones, para ello se necesita una serie de conceptos como: Función Maximizar, lenguajes binarios, números aleatorios, probabilidades, cruce, mutación.

Conocerá algoritmos de optimización como el problema de la mochila donde se verá: Introducción, descripción, otras explicaciones sobre el problema de la mochila.

Algoritmo de optimización sobre el problema del Viajante, al finalizar se dejará un Trabajo sobre los diferentes algoritmos aprendidos.

Actividad de Aprendizaje Nº 03: Heurísticas Bioinspiradas basadas en la adaptación de probabilidades. Aquí el alumno conocerá y aplicará técnicas de optimización probabilista y usara términos como: recombinación, mutación, función de calidad, algoritmo evolutivo, tipos de selección, tipos de Crossover.

El alumno desarrollará un trabajo grupal en aula, donde encontraran a la mejor generación de un grupo de individuos.

Actividad de Aprendizaje Nº 04: Introducción y conceptos Básicos de Algoritmos Genéticos. Aquí el alumno aprende a relacionar los conceptos de biología (Genotipo, Fenotipo, Cromosoma, Gen, Alelo, Función de aptitud), con los algoritmos genéticos (Código de cadenas, Punto sin codificar, Cadena, Posición de Cadenas, Valor en una posición determinada y Valor de la Función Objetivo). Luego el alumno realizará un Trabajo de investigación.

Actividad de aprendizaje nº 05: Programación Genética. Aquí se programaran diferentes aplicaciones Bioinformáticas tomando como referencia lo leído anteriormente; por Ejemplo el problema del viajante, problemas GPS, la Mochila, problema de Poblaciones etc.

INDICE

Pág

Introducción 2

Índice 3

Actividad de Aprendizaje Nº 01: Computación Basada en Modelos Naturales 5

Bioinformática 5

Modelos Naturales 5

Características de los Modelos Bioinspirados 5

Modelos Bioinspirados 6

Redes Neuronales 6

Algoritmos Evolutivos 7

Optimización basada en colonias de hormigas 7

Particle Swarm Optimization (pso) 7

Algoritmos Inmunológicos 8

Sistemas Inmune Artificial 8

Ejemplo de una aplicación 8

Conclusión Final de la Actividad de Aprendizaje 01 10

Trabajo de Investigación 10

Actividad de Aprendizaje Nº 02: Optimización Basada En Colonias de Hormigas 11

Optimización Basada En Colonias de Hormigas 11

Algoritmo Basados en Poblaciones, Combinaciones y Mutaciones 11

Algoritmo de Optimización con Colonia de Hormigas para el Problema de la Mochila 13

Introducción al Problema de la Mochila 13

Descripción del Problema de la Mochila 14

Otra Explicación del Problema de la Mochila 15

Problemas, Representación y Función de Calidad 17

Algoritmo de problema del Viajante 17

Definiciones 17

Trabajo Grupal 20

Actividad de Aprendizaje Nº 03: Heurísticas Bioinspiradas Basadas en la Adaptación de Probabilidades 21

Heurísticas Bioinspiradas Basadas en la Adaptación de Probabilidades 21

DFD de una Población de Individuos 22

Un Algoritmo Evolutivo 23

Tipos de Individuo 23

Operadores Genéticos 23

El Cruce 23

Evaluación de Soluciones 24

Historia de John Holland 24

Algoritmos Genéticos Propiamente dicho 25

Tamaño de la Población 25

Codificación de terminación 25

Evaluación y Selección 25

Basado en el Rango 26

Rueda de Ruleta, Selección de Torneo y Crossover 27

Crossover de n Puntos y Crossover Uniforme 28

Crossover Especializados y Mutación 29

Trabajo Grupal en el Aula 29

Actividad de Aprendizaje Nº 04: Introducción y Conceptos Básicos de Algoritmos Genéticos 31

Introducción y Conceptos Básicos de Algoritmos Genéticos 31

Cuadro de comparación en biología y en algoritmos genéticos 31

Ejemplo Hipotético 35

Resumen 41

Espacio de Búsqueda 52

Problemas NP Completos 52

Ejemplo Máximo Función 54

Operadores de un Algoritmo Genético 55

Operador de Mutación 56

Operador de Aceptación 57

Parámetros de los AGs 57

Selección 58

Elitismo 61

Representaciones de Genotipos 61

Actividad de aprendizaje nº 05: Programación Genética 63

Programación Genética 63

Problema del Viajante 63

Problema de poblaciones 65

Problema de la Mochila 78

Diagramas de Flujo del Problema de la Mochila 80

Diagramas de Flujo: Solución 01 81

Diagramas de Flujo Solución 02 82

Diagramas de Flujo Solución 03 84

Aplicación del Problema de la Mochila (Ventanas) 92

Codificación del Problema de la Mochila 94

Bibliografía 102

Actividad de Aprendizaje Nº 01

Computación Basada en Modelos Naturales

Objetivos:

• Definir modelos de Computación Bioinspirados.

• Conocer las características de los modelos Bioinspirados.

• Investigar sobre las diferentes aplicaciones que existen sobre modelos naturales.

Contenidos:

Modelos de Computación Bioinspirados.

Características de los Modelos Bioinspirados.

Aplicaciones sobre Modelos Naturales.

BIOINFORMÁTICA

Bioinformática es una disciplina científica emergente que utiliza tecnología de la información para organizar, analizar y distribuir información con la ayuda de la biológica y poder solucionar problemas complejos de la vida real.

Bioinformática es un área de investigación multidisciplinaria, la cual puede ser ampliamente definida como la interface entre dos ciencias: Biología y Computación y está impulsada por la incógnita del genoma humano y la promesa de una nueva era en la cual la investigación genómica puede ayudar dramáticamente a mejorar la condición y calidad de vida humana.

MODELOS NATURALES

COMPUTACIÓN BASADA EN MODELOS NATURALES

CONCEPTO DE MODELOS DE COMPUTACIÓN BIOINSPIRADOS

Se basa en emplear analogías con sistemas naturales o sociales para la resolución de problemas.

Los algoritmos bioinspirados simulan el comportamiento de sistemas naturales para el diseño de métodos heurísticos no determinanticos de “búsqueda” /”aprendizaje”/”comportamiento”.

CARACTERÍSTICAS DE LOS MODELOS BIOINSPIRADOS

• Modelan (de forma aproximada) un fenómeno existente en la naturaleza. Metáfora biológica.

• Son no determinísticos: Es decir un algoritmo no determinístico es un algoritmo que con la misma entrada ofrece muchos posibles resultados. No se puede saber de antemano cuál será el resultado de la ejecución de un algoritmo no determinístico.

• A menudo presentan, implícitamente, una estructura paralela (múltiples agentes).

• Son adaptativos (utilizan realimentación con el entorno para modificar el modelo y los parámetros).

MODELOS BIOINSPIRADOS

A) REDES NEURONALES:

• Basados en la simulación del comportamiento del Sistema Nervioso

• Paradigma de Aprendizaje Automático

B) ALGORITMOS EVOLUTIVOS: Basados en los principios Darwinianos de Evolución Natural.

C) OPTIMIZACIÓN BASADA EN COLONIAS DE HORMIGAS: Basados en la simulación del comportamiento de las colonias de hormigas cuando recogen comida.

D) PARTICLE SWARM OPTIMIZATION (PSO): Es una técnica de optimización inspirada en el comportamiento social de bandadas de aves o peces.

E) ALGORITMOS INMUNOLÓGICOS: Basados en la simulación del comportamiento del sistema inmunológico (El sistema inmunológico es la defensa natural del cuerpo contra las infecciones).

F) SISTEMAS

...