Enumerating all possible biosynthetic pathways from metabolic networks

Abstract

Exhaustive identification of all alternate possible pathways that exist within metabolic networks can provide valuable insights into cellular metabolism. With the growing number of metabolic reconstructions, there is a need for an efficient method to enumerate pathways, which can also scale well to large metabolic networks, such as those corresponding to microbial communities.\n\nWe developed MetQuest, an efficient graph-theoretic algorithm to enumerate all possible pathways of a particular length between a given set of source and target molecules. Our algorithm employs a guided breadth-first search to identify all feasible reactions based on the availability of the precursor molecules, followed by a novel dynamic-programming based enumeration, which assembles these reactions into pathways producing the target from the source. We demonstrate several interesting applications of our algorithm, ranging from predicting amino acid biosynthesis pathways to identifying the most diverse pathways involved in degradation of complex molecules. We also illustrate the scalability of our algorithm, by studying larger graphs such as those corresponding to microbial communities, and identify several metabolic interactions happening therein.\n\nA Python-based implementation of MetQuest is available at https://github.com/RamanLab/MetQuest