Robust Optimal Metabolic Factories

Perhaps the most fundamental model in synthetic and systems biology for inferring pathways in metabolic reaction networks is a metabolic <i>factory</i>: a system of reactions that starts from a set of source compounds and produces a set of target molecules, while conserving or not depleting intermediate metabolites. Finding a shortest factory-that minimizes a sum of real-valued weights on its reactions to infer the most likely pathway-is NP-complete. The current state-of-the-art for shortest factories solves a mixed-integer linear program with a major drawback: it requires the user to set a critical parameter, where too large a value can make optimal solutions infeasible, while too small a value can yield degenerate solutions due to numerical error. We present the first <i>robust algorithm</i> for optimal factories that is both <i>parameter-free</i> (relieving the user from determining a parameter setting) and <i>degeneracy-free</i> (guaranteeing it finds an optimal nondegenerate solution). We also give for the first time a <i>complete characterization</i> of the graph-theoretic structure of shortest factories, that reveals an important class of degenerate solutions which was overlooked and potentially output by the prior state-of-the-art.We show degeneracy is precisely due to <i>invalid stoichiometries</i> in reactions, and provide an efficient algorithm for identifying all such <i>misannotations</i> in a metabolic network. In addition we settle the relationship between the two established pathway models of <i>hyperpaths</i> and factories by proving hyperpaths actually comprise a <i>subclass</i> of factories. Comprehensive experiments over all instances from the standard metabolic reaction databases in the literature demonstrate our parameter-free exact algorithm is <i>fast in practice</i>, quickly finding optimal factories in large real-world networks containing thousands of reactions. A preliminary implementation of our robust algorithm for shortest factories in a new tool called Freeia is available free for research use at http://freeia.cs.arizona.edu.