Desarrollo de algoritmos evolutivos para el descubrimiento de relaciones en datos metabólicos

Abstract

Relations among metabolic compounds are given by sequences of reactions known as metabolic pathways. These make it possible to produce one compound from another, and knowing this is essential for planning the synthesis of specific compounds. Currently, techniques used to find metabolic pathways are based on traditional search methods. However, these show difficulties when considering a large number of reactions and compounds due to the exponential growth of the search tree. Additionally, only two compounds are related by the solutions found, and the availability of substrates for each reaction in the metabolic pathway is not taked into account. This Thesis proposes the development of two new algorithms for finding metabolic pathways that relate a set of compounds. In particular, the approaches are based on evolutionary computation, giving that these methods are able to explore large search spaces. The first approach addresses the search of linear metabolic pathways between two compounds, and it is used as a framework for the development of the algorithm and its comparison with known searching techniques. The second approach is a generalization of the linear searching algorithm. It focuses on finding metabolic pathways that link more than two compounds, for which substrates of all reactions are availables. The structure and operators are described for each algorithm, and the effect of the parameters settings is analyzed. Finally, several case studies are evaluated.

Las relaciones entre compuestos metabólicos están dadas por secuencias de reacciones que conforman vías metabólicas. Éstas hacen que sea posible producir un compuesto a partir de otro, y su conocimiento es esencial para planificar la síntesis de compuestos específicos. Actualmente, las técnicas usadas para encontrar vías metabólicas se basan en métodos clásicos de búsqueda, los cuales presentan dificultades cuando se considera un gran número de reacciones y compuestos debido al crecimiento exponencial del árbol de búsqueda. Adicionalmente, las soluciones obtenidas se limitan a relacionar sólo dos compuestos y no contemplan la disponibilidad de los sustratos para cada reacción de la vía metabólica. En esta tesis se propone el desarrollo de dos nuevos algoritmos que permitan encontrar vías metabólicas que relacionen un conjunto de compuestos. En particular, se desarrollarán algoritmos basados en computación evolutiva, debido a la capacidad de estos métodos para explorar grándes espacios de búsqueda. La primera propuesta aborda la búsqueda de vías metabólicas lineales entre dos compuestos, la cual se utiliza como marco para el desarrollo del algoritmo y comparación con técnicas de búsqueda conocidas. La segunda propuesta consiste en una generalización del algoritmo de búsqueda lineal. Ésta se enfoca en la búsqueda de vías metabólicas que relacionan más de dos compuestos, para las que todas las reacciones disponen de los sustratos para que puedan realizarse. Para cada algoritmo se describe su estructura y componentes, se analiza el efecto de los parámetros que controlan su comportamiento y se presentan casos de estudio reales.