Bio-inspired metaheuristics for automatic synthesis of novel metabolic pathways

GERARD, MATIAS F.; STEGMAYER, GEORGINA; MILONE, DIEGO H.

Buenos Aires

Congreso; 4th ISCB-LA Bioinformatics Conference; 2016

International Society for Computational Biology and Asociación Argentina de Bioinformática y Biología Computacional

BackgroundMetabolic pathways synthesis is currently a necessary technique to understand and manipulate the metabolism of livingbeings. Different approaches, mainly based on classical search algorithms, have been proposed to find linear sequences ofreactions (pathways) linking two compounds. However, such models do not take into account the availability of substratesfor each reaction, frequently leading to solutions that lack biological feasibility. Moreover, current available methods havethe problem of the exponential increase of search trees when the search space involves a large number of compounds andreactions. Thus, the synthesis of novel metabolic pathways is an especially challenging task due to the high number ofpotential solutions to explore and the feasibility restrictions that must be taken into account.ResultsWe present a novel metaheuristic-based tool1 for efficient search of metabolic pathways, able to make intelligent explorationon large spaces of solutions. This is inspired on the real ants behavior for searching food. Starting from a set of availablecompounds, the software ants explore the space of solutions by building only feasible metabolic pathways. On each stepthey select one feasible reaction and expand the set of available compounds with its products, for which new reactionscan be carried out. When an ant finds a solution, it leaves pheromones over the sequence of reactions followed accordingto the pathway size and the proportion of the specified compounds that were linked. Thus, given a base of reactions overwhich to seek a solution, the initial search conditions (compounds freely available) and the set of compounds to relate, thealgorithm search automatically a feasible metabolic pathway among the specified compounds. Figure 1 shows an outlineof the process. As it can be seen, just basic information is provided to the algorithm, in order to perform the searchand return a metabolic pathway linking the specified compounds. It has been tested on several real problems, searchingfor well known pathways for validation. Standard solutions were found, together with novel pathways linking the samecompounds. In all cases, solutions were built only with feasible reactions. Figure 2 presents an example of a metabolicpathway linking 4 specific compounds, searched over 589 possible reactions.ConclusionsIn this work we presented a novel metaheuristic-based tool for the automatic search of metabolic pathways. The modelallows to find, not only linear feasible metabolic pathways, but also branched ones. Tests performed using real cases forvalidation showed that the algorithm can recall the standard metabolic pathways, together with other alternatives offeasible solutions. The web interface provided for this tool can facilitate searching for metabolic pathways under a widerange of initial conditions, and can be an interesting option for the study and design of novel pathways.