back icon
close icon

Capture phrases in quotes for more specific queries (e.g. "rocket ship" or "Fred Lynn")

Article  July 1, 2014

Optimal Metabolic Route Search Based on Atom Mappings

SRI Authors Mario Latendresse, Peter Karp



Latendresse, M., Krummenacker, M., & Karp, P. D. (2014). Optimal metabolic route search based on atom mappings. Bioinformatics, 30(14), 2043-2050. doi: 10.1093/bioinformatics/btu150


Motivation: A key computational problem in metabolic engineering is finding efficient metabolic routes from a source to a target compound in genome-scale reaction networks, potentially considering the addition of new reactions. Efficiency can be based on many factors, such as route lengths, atoms conserved and the number of new reactions, and the new enzymes to catalyze them, added to the route. Fast algorithms are needed to systematically search these large genome-scale reaction networks.

Results: We present the algorithm used in the new RouteSearch tool within the Pathway Tools software. This algorithm is based on a general Branch-and-Bound search and involves constructing a network of atom mappings to facilitate efficient searching. As far as we know, it is the first published algorithm that finds guaranteed optimal routes where atom conservation is part of the optimality criteria. RouteSearch includes a graphical user interface that speeds user understanding of its search results. We evaluated the algorithm on five example metabolic-engineering problems from the literature; for one problem the published solution was equivalent to the optimal route found by RouteSearch; for the remaining four problems, RouteSearch found the published solution as one of its best-scored solutions. These problems were each solved in less than 5 s of computational time.

Availability and implementation: RouteSearch is accessible at by using the menu command  [Graphic]  RouteSearch and by downloading Pathway Tools. Pathway Tools software is freely available to academic users, and for a fee to commercial users. Download from:

How can we help?

    Once you hit send…

    We’ll match your inquiry to the person who can best help you. Expect a response within 48 hours.

    Our Privacy Policy