Metaheurísticas, optimización multiobjetivo y paralelismo para descubrir motifs en secuencias de ADN

Resumen

La resolución de problemas complejos mediante técnicas evolutivas es uno de los aspectos más investigados en Informática. El objetivo principal de esta tesis doctoral es desarrollar nuevos algoritmos capaces de resolver estos problemas con el menor tiempo computacional posible, mejorando la calidad de los resultados obtenidos por los métodos ya existentes. Para ello, combinamos tres conceptos importantes: metaheurísticas, optimización multiobjetivo y paralelismo. Con este fin, primero buscamos un problema de optimización importante que aún no fuese resuelto de forma eficiente y encontramos el Problema del Descubrimiento de Motifs (PDM). El PDM tiene como objetivo descubrir pequeños patrones repetidos (motifs) en conjuntos de secuencias de ADN que puedan poseer cierto significado biológico. Para abordarlo, definimos una formulación multiobjetivo adecuada a los requerimientos del mundo real, implementamos un total de diez algoritmos de distinta naturaleza (población, trayectoria, inteligencia colectiva...), analizando aspectos como la capacidad de escalar y converger. Finalmente, diseñamos diversas técnicas paralelas, haciendo uso de entornos de programación como OpenMP y MPI, que tratan de combinar las propiedades de varias metaheurísticas en una única aplicación. Los resultados obtenidos son estudiados en detalle a través de la aplicación de numerosos test estadísticos, y las predicciones son comparadas con las descubiertas por un total de trece herramientas biológicas bien conocidas en la literatura. Las conclusiones obtenidas demuestran que la utilización de la optimización multiobjetivo en técnicas metaheurísticas favorece el descubrimiento de soluciones de calidad y que el paralelismo es útil para combinar las propiedades evolutivas de diferentes algoritmos.