PDF de programación - ALGORITMOS HEURÍSTICOS EN BIOINFORMÁTICA

ALGORITMOS HEUR´’ISTICOS

EN

BIOINFORM ÁTICA

TESIS DOCTORAL

David Alejandro Pelta

[email protected]

DIRECTORES: José L. Verdegay - Armando Blanco

Depto. de Ciencias de la Computación e

Inteligencia Artificial.

Universidad de Granada, 18071 Granada

2

Índice General

Agradecimientos

Introducción

1 Optimización Combinatoria y Metaheurísticas

1.1 Definiciones Preliminares
. . . . . . . . . . . . . . . . . . . . .
1.2 Propiedades de las Metaheurísticas . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
1.3 Ejemplos de Metaheurísticas

2 FANS: una Heurística para Problemas de Optimización

2.1 Presentación de FANS . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 El Operador de Modificación . . . . . . . . . . . . . . .
2.1.2 La Valoración Difusa . . . . . . . . . . . . . . . . . . . .
2.1.3 El Administrador de Operación . . . . . . . . . . . . . .
2.1.4 El Administrador de Vecindario . . . . . . . . . . . . . .
2.1.5 Parámetros Globales . . . . . . . . . . . . . . . . . . . .
2.1.6 Manejo de optimos locales . . . . . . . . . . . . . . . . .
2.1.7 El Algoritmo . . . . . . . . . . . . . . . . . . . . . . . .

2.2 La Valoración Difusa como Mecanismo de

Variación del Comportamiento de FANS . . . . . . . . . . . . .
2.3 Comentarios Sobre la Implementación . . . . . . . . . . . . . .
2.4 Utilización de Múltiples Operadores

en el Proceso de Búsqueda . . . . . . . . . . . . . . . . . . . . .
2.4.1
“Un Operador, un Landscape” . . . . . . . . . . . . . .

3

7

11

17
18
20
22

33
35
36
37
37
38
39
39
41

42
46

48
48

4

2.4.2

2.5 Conclusiones

Justificación Experimental . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .

Índice General

52
56

59
60
61
62
66
67
67
68
75
75
75
80
80
81
84
89
89
93
99

3 Verificación Experimental de FANS

Instancias de Prueba

3.1 FANS vs AG en Problemas de Mochila . . . . . . . . . . . . . .
3.1.1 Formulación de los Problemas de Mochila . . . . . . . .
3.1.2
Implementación de FANS . . . . . . . . . . . . . . . . .
3.1.3 Descripción del Algoritmo Genético . . . . . . . . . . .
3.2 Problemas de Mochila Estandard . . . . . . . . . . . . . . . . .
3.2.1
. . . . . . . . . . . . . . . . . . .
3.2.2 Experimentos y Resultados . . . . . . . . . . . . . . . .
3.3 Mochila con Múltiples restricciones . . . . . . . . . . . . . . . .
3.3.1
Instancias de Prueba . . . . . . . . . . . . . . . . . . . .
3.3.2 Experimentos y Resultados . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
3.4.1 Funciones de Prueba . . . . . . . . . . . . . . . . . . . .
3.4.2
Implementación de FANS . . . . . . . . . . . . . . . . .
3.4.3 Experimentos y Resultados . . . . . . . . . . . . . . . .
3.5 Análisis Complementarios de FANS . . . . . . . . . . . . . . . .
3.5.1 Análisis de la Calidad de las Soluciones Investigadas . .
3.5.2 Evaluación de Administradores de Vecindarios
. . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Experimentos sobre Funciones Reales

3.6 Conclusiones

4 Aplicación de FANS a Problemas de Bioinformática

101
4.1 Conceptos Básicos
. . . . . . . . . . . . . . . . . . . . . . . . . 103
4.2 El Problema de Predicción de Estructura . . . . . . . . . . . . 108
4.2.1 Problemas en la determinación de la estructura . . . . . 110
4.2.2 Modelizaciones del Problema . . . . . . . . . . . . . . . 112
. . . . . . . . . . 117
4.3.1 Consideraciones Generales . . . . . . . . . . . . . . . . . 118
4.3.2 Comparación de Estructuras vía Matrices de Distancia . 120
4.3.3 Comparación de Estructuras vía Cliques . . . . . . . . . 121

4.3 El Problema de Comparación de Estructuras

Índice General

5

4.3.4 Comparación de Estructuras vía

Superposición de Mapas de Contacto . . . . . . . . . . . 122
4.4 FANS para el Problema de Predicción de Estructura . . . . . . 123
4.4.1
Introducción . . . . . . . . . . . . . . . . . . . . . . . . 123
4.4.2 Diseño de Algoritmos para PSP . . . . . . . . . . . . . . 125
4.4.3
Influencia de la Codificación en un AG . . . . . . . . . . 130
4.4.4
Influencia de la Codificación en FANS . . . . . . . . . . 133
4.4.5 Evitando los problemas del AG en PSP . . . . . . . . . 136
4.4.6
Instancias de prueba utilizadas en los experimentos . . . 139

4.5 FANS para el Problema de

Emparejamiento Estructural de Moléculas
. . . . . . . . . . . 141
4.5.1 Definición del Problema . . . . . . . . . . . . . . . . . . 142
4.5.2
Implementación de FANS para MSM . . . . . . . . . . . 142
4.5.3 Experimentos y Resultados . . . . . . . . . . . . . . . . 145
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

4.6 Conclusiones

Conclusiones y Trabajos Futuros

Bibliografía

156

167

6

Índice General

Agradecimientos

La finalización de esta tesis marca el fin de una etapa y el comienzo de otra.
El camino no ha sido fácil y obviamente no hubiera podido recorrerlo solo y
estando a más de 10000 km. de mi país y de los míos.

Es por eso que en estos párrafos quiero dejar expresado mi agradecimiento
a todos aquellos que contribuyeron, no sólo en el ámbito académico, a que estos
años de doctorado y estadía en Granada, hayan sido más que gratificantes y
dignos de recuerdo.

En primer lugar, es practicamente imposible para cualquier latinoamerica-
no realizar un doctorado en Europa sin apoyo económico, así que deseo agra-
decer a los Prof. Nicolás Perez de la Blanca, Armando de Giusti y Gabriel
Baum por su ayuda mediante una beca del proyecto Cometas del Programa
ALFA. Sin este apoyo inicial, quizás nunca hubiera podido iniciar el doctorado.
Posteriormente, mi beca del Consejo Nacional de Investigaciones Científicas
y Técnicas (CONICET) de Argentina me permitió llegar a este punto. Agra-
dezco a Gabriel Baum la confianza y el haber aceptado ser mi director desde
Argentina.

Deseo agradecer profundamente a mis directores José Luis Verdegay y
Armando Blanco. Podría hacer una lista de cosas por las cuales siento que les
debo un agradecimiento, pero la resumo en tres cosas: gracias por la constante
disponibilidad, apoyo y también su amistad. En estos casi 4 años de trabajo
conjunto he aprendido mucho y creo que más que una relación tutor-alumno
(o jefe-esclavo!), en mi opinión hemos sido verdaderos compañeros de trabajo.
Considerando que antes de empezar no nos conocíamos y viendo donde estamos
ahora, solo me queda expresar el deseo que ojalá sigamos trabajando juntos.

7

8

Agradecimientos

También vaya mi agradecimiento a todo el Departamento de Ciencias de

la Computación e Inteligencia Artificial.

Gracias también al Dr. Hilario Ramirez, nuestro biólogo de cabecera, por
hacerse tiempo para atendernos y por su ayuda en el problema de empareja-
miento estructural de moléculas.

Quiero expresar mi gratitud general hacia profesores del exterior (J. Szus-
takowsky, J. Beasley, A. Lokketangen, N. Krasnogor, P. Moscato, etc) que
amablemente me enviaron copias de sus trabajos y a todos aquellos que colo-
can los resultados de sus investigaciones en Internet para que otros podamos
acceder a ellos.

Fuera del ámbito académico, quiero agradecer a Sergio y Natalia (y flia.)
por su amistad y por hacer que la estadía en Granada sea más agradable.
Siempre recordaré las idas a la playa, las fiestas de fin de año y muchas y
buenas cenas compartidas.

A Juan José, Leticia, Erandi y Luis, los “mexicanos”, por compartir con

nosotros sus experiencias que en el fondo también son las nuestras.

A Ariel, Karin y Adrián, simplemente por estar dispuestos a ayudar en lo

que haga falta.

A mis compañeras de despacho en el Mecenas, Eva y Belén, por hacer de

mi lugar de trabajo en los últimos meses un sitio agradable y acogedor.

También quiero agradecer a mi amigo Natalio Krasnogor, con quien en 1996
empezamos el Grupo Biocom siendo de los primeros grupos en Argentina en
dedicarnos al área de Bioinformática. Sin su insistencia para que realizara la
preinscripción al doctorado en 1998, vaya uno a saber que estaría haciendo
en estos momentos. Su disponibilidad para leer varios manuscritos horribles
y sus constantes sugerencias, además del trabajo en conjunto que seguimos
realizando, hacen que lo considere un colega excepcional. Quizás con un poco
de suerte, el futuro nos encuentre trabajando juntos y en el mismo lugar. Si
no, Internet y el teléfono nos ayudarán.

Al otro lado del Atlántico están mis padres, Beba y Héctor, junto con mi
hermana Vero y Aquiles, y mi sobrino Valentín a quien al momento de escribir
estas líneas solo conozco por fotos. Ellos saben que a pesar de la distancia,

9

siempre los tengo presentes y que aunque las circunstancias hacen que estemos
un poco lejos, siempre aspiro a que podamos volver a estar un poco más cerca.
Espero poder dar a mi hija el mismo amor que ellos me dieron y que ha hecho
de mí la persona que soy.

Este último año ha sido especialmente duro para todos los argentinos.
Desde afuera, la angustia y la impotencia se multiplican y ojalá que entre
todos seamos capaces de generar las alternativas que permitan reconstruir un
país que esta vez sea justo, solidario y para todos.

Finalmente, me faltan las palabras para agradecerle a Gaby todo su esfuer-
zo, comprensión, apoyo, ayuda y amor para que esta aventura que empezamos
juntos en el 98 llegara a buen puerto. Sin ella nada de esto hubiera sido posible
y espero que los proximos años sean tan buenos como estos últimos.

Desde hace ahora 6 meses, tenemos un sol propio en nuestro universo par-
ticular: Martina. Ella nos llena de vida cada día con su sonrisa, sus progresos
constantes y su alegría. Es el centro de nuestra atención y la “responsable”
de que esta tesis no estuviera terminada antes.

Así que Gaby y Martina, mis dos amores, esta tesis que resume gran parte

del trabajo de casi 4 años, va dedicada a ustedes.

10

Agradecimientos

Introducción

Las técnicas de resolución de problemas basadas en computadoras son ele-
mentos claves en l