Metabolic pathways synthesis based on ant colony optimization

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

Salta

Simposio; XX ASAI - 48 JAIIO; 2019

SADIO - Departamento de Informática de la UNSa

A current challenge in bioinformatics is to discover how to transform particular compounds into specific products. Typically, the common approach is finding the sequence of reactions that relate the specified substrate (source) and product (target) using classical searching algorithms. However, those methods have three main limitations: difficulty in handling large amounts of reactions and compounds; absence of a step that verifies the availability of substrates; and inabilityto find branched pathways.In [1], we propose a novel ant colony-based algorithm for metabolic pathways synthesis. This algorithm, named Pheromone-Directed Seeker (PhDSeeker), is able to relate several compounds simultaneously by emulating the behavior of real ants while seeking a path between their colony and a source of food. The process is designed to ensure the availability of substrates for every reaction in the solution. Thus, ants explore the set of reactions on each iteration searching for possible pathways to link the compounds. After that, they share information about solutions found by each one and then perform a new search. This process is guided by a cost function that evaluates the availability of substrates, the connection between source and target, and the pathway size.Experimental results show that searching time for PhDSeeker is kept almost constant when the number of reactions and compounds involved in the search increases. This is clearly an advantage over classical search methods, which suffer from the problem of the exponential growth of search trees. Furthermore, comparisons with classical searching algorithms and other recent approaches show clear advantages of PhDSeeker. The analysis performed over 42 pathways produce an average accuracy of 0.936 when analyzing compounds, meanwhile this value is 0.872 when reactions are considered. In short, PhDSeeker provides a simple and flexible way for synthesizing metabolic pathways.A web-interface to run PhDSeeker online is available for free academic use at http://sinc.unl.edu.ar/web-demo/phdseeker2/. A link to the full source code is also available there.References:1. Gerard, M.F., Stegmayer, G., Milone, D.H.: Metabolic pathways synthesis based on ant colony optimization. Sci. Rep. 8(1), 16398 (2018)