Maximizing Output and Recognizing Autocatalysis in Chemical Reaction Networks is NP-Complete

Details Maximizing Output and Recognizing Autocatalysis in Chemical Reaction Networks is NP-Complete Maximizing Output and Recognizing Autocatalysis in Chemical Reaction Networks is NP-Complete

2011-10-27

arxiv.org/abs/1110.6051v1

Biology

Quantitative Biology

Molecular Networks

Scientific paper

Background: A classical problem in metabolic design is to maximize the production of desired compound in a given chemical reaction network by appropriately directing the mass flow through the network. Computationally, this problem is addressed as a linear optimization problem over the "flux cone". The prior construction of the flux cone is computationally expensive and no polynomial-time algorithms are known. Results: Here we show that the output maximization problem in chemical reaction networks is NP-complete. This statement remains true even if all reactions are monomolecular or bimolecular and if only a single molecular species is used as influx. As a corollary we show, furthermore, that the detection of autocatalytic species, i.e., types that can only be produced from the influx material when they are present in the initial reaction mixture, is an NP-complete computational problem. Conclusions: Hardness results on combinatorial problems and optimization problems are important to guide the development of computational tools for the analysis of metabolic networks in particular and chemical reaction networks in general. Our results indicate that efficient heuristics and approximate algorithms need to be employed for the analysis of large chemical networks since even conceptually simple flow problems are provably intractable.

Affiliated with

Also associated with

No associations

Rating

Maximizing Output and Recognizing Autocatalysis in Chemical Reaction Networks is NP-Complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximizing Output and Recognizing Autocatalysis in Chemical Reaction Networks is NP-Complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximizing Output and Recognizing Autocatalysis in Chemical Reaction Networks is NP-Complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-375868