La bioinformática estudia la aplicación de las ciencias computacionales a problemas existentes en las ciencias biológicas mediante el uso de algoritmos, bases de datos, conceptos y diversas tecnologías de la información [1]. Dentro de las ciencias computacionales, encontramos el área de la computación evolutiva, la cual usa metaheurísticas basadas en el principio de la supervivencia del más apto de la teoría de Charles Darwin, para resolver problemas de optimización y clasificación.
Esta tesis aborda la solución de un problema de bioinformática conocido como la inferencia de modelos de redes reguladoras de genes, usando técnicas de computación evolutiva y paralelismo. El algoritmo evolutivo adoptado para este trabajo es la evolución diferencial. Dicho algoritmo se eligió debido a su probada eficiencia (reportada en la literatura especializada) para resolver problemas de optimización en los que todas las variables de decisión son números reales. Las redes reguladoras de genes son conjuntos de genes que interactúan entre sí, afectando los niveles de expresión de los genes involucrados en la red. Inferir el comportamiento de las redes reguladoras de genes es un proceso computacionalmente costoso. Por ello, el uso de cómputo de alto rendimiento resulta una alternativa atractiva en este dominio. Recientemente, y gracias al desarrollo tecnológico de las unidades de procesamiento gráfico (GPUs, por sus siglas en inglés), éstas han sido utilizadas como una alternativa económica y muy eficiente para realizar cómputo de alto rendimiento.
En esta tesis presento la primera implementación de evolución diferencial basada en GPUs (utilizando CUDA) para resolver el problema de la inferencia de modelos de redes reguladoras de genes. En nuestra implementación, se adoptan sistemas de ecuaciones diferenciales ordinarias (llamados sistemas S) para modelar el dinamismo de los niveles de expresión que ocurren en las redes reguladoras de genes de nuestro interés. Los resultados presentados en esta tesis demuestran que el uso de cómputo paralelo mediante GPUs produce una importante reducción del tiempo de cómputo necesario para resolver este costoso problema de optimización. Los resultados que aquí se presentan, indican reducciones de hasta 140 veces en el tiempo de cómputo requerido para una ejecución del algoritmo propuesto, con respecto a su versión secuencial. Aunque las redes resueltas en esta tesis tienen tamaños modestos, la posible extrapolación de nuestro algoritmo a instancias más grandes puede pueden traer beneficios importantes, debido a las diversas aplicaciones que tienen las redes reguladoras de genes en medicina, ingeniería ambiental, diseño biológico y la industria farmacéutica.
Abstract
Bioinformatics studies the application of computer science techniques to problems arising in biological sciences through the use of algorithms, databases, concepts and several other information technologies. Within computer science, we have evolutionary computation, which uses metaheuristics based on the principle of the survival of the fittest from Charles Darwin's evolutionary theory in order to solve optimization and classification problems.
This thesis deals with the solution of a problem from bioinformatics known as the inference of models of gene regulatory networks, using evolutionary computation and parallel techniques. The evolutionary algorithm adopted for this work is differential evolution. Such an algorithm was chosen due to its well-known efficiency (as reported in the specialized literature) when solving optimization problems in which all the decision variables are real numbers. Gene regulatory networks are sets of genes that interact with each other, affecting the expression levels of the genes involved in the network. Inferring the behavior of gene regulatory networks is a computationally expensive process. Thus, the use of high performance computing is an attractive choice within this domain. Recently, and thanks to the technological advances in the development of graphical processing units (GPUs), they have been adopted as an economical and very efficient alternative for high performance computing.
In this thesis, we present what seems to be the first GPU-based implementation (using CUDA) of differential evolution for solving the problem of inferring models of gene regulatory networks. Our implementation adopts systems of differential equations (called S systems) for modelling the dynamism of the expression levels that occur in the regulatory networks of our interest. The results presented in this thesis show that the use of parallel computing through the use of GPUs produces an important reduction in the computational time required to solve this expensive optimization problem. The results shown here indicate reductions of up to 140 times in the computational time required for one execution of our optimization algorith, with respect to its sequential version. Although the networks solved in this thesis are of modest size, the possible extrapolation of our algorithm to larger instances could bring important benefits, mainly because of the many applications that gene regulatory networks have in medicine, environmental engineering, biological design and the pharmaceutical industry .
