Metabolic pathfinding based on genetic algorithms

GERARD, M.; STEGMAYER, G.; MILONE, D. H.

Congreso; 3er. Congreso Argentino de Bioinformática y Biología Computacional; 2012

Background: Metabolic pathway searching consists of fnding a set of reactions allowing to transform a compound into another one. There are several search methods based on classical algorithms like breath-first search (BFS) and depth-first search (DFS) to perform this task. However, there are problems in which a very high number of solutions must be explored, making classical methods practically inapplicable. Genetic algorithms use stochastic search to explore multiple points of the search space at the same time. Material and methods: We propose a genetic algorithm (EAMP) that perform a two-end metabolic pathway search and compare its performance with two classical search algorithms. To achieve this, the chromosomes were built by attaching a reaction to each gene, and the left-to-right sequence of genes encoded a metabolic pathway. A initialization strategy to build variable size chromosomes with a partially conserved sequentiality of reactions was proposed. The crossover and mutation operators were designed to promote the building of a reaction chain. Fitness function was built to consider the validity of the reactions sequence, the presence of the compounds to relate and the occurrence of repeated reactions. Results: EAMP was studied for several mutation rates and different initialization strategies. Results indicate that minimum searching time was reached for a mutation rate of 0.04 and the initialization strategy with initial variable size for the chromosomes. Comparison of EAMP with BFS and DFS is shown on Figure 1. Boxplots correspond to searching time and number of reactions of 120 pathways founds with each algorithm. DFS perform the search with minimum search time but produce solutions with maximum number of reactions allowed. BFS found shortest pathways but employ greater time than EAMP. The genetic algorithm perform the search using an intermediate time to BFS and DFS, and not only found the shortest pathways but also solutions with greater number of reactions linking the two compounds. Conclusions: The proposed genetic algorithm found metabolic pathways using intermediate times to those required by BFS and DFS. Moreover, it builds metabolic pathways with variable size, including either shortest pathways and larger solutions. It is interesting from a biological viewpoint because pathways larger than shortest path could be provide relevant information about alternative metabolic pathways.