Maximizing output and recognizing autocatalysis in chemical reaction networks is NP-complete
Tóm tắt
A classical problem in metabolic design is to maximize the production of a 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. 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 bi-molecular 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. 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.
Tài liệu tham khảo
Bernal A, Daza E: Metabolic networks: beyond the graph. Curr Comput Aided Drug Des 2011, 7: 122–132.
Zeigarnik AV: On Hypercycles and Hypercircuits in Hypergraphs. In Discrete Mathematical Chemistry, Volume 51 of DIMACS series in discrete mathematics and theoretical computer science. Edited by: Hansen P, Fowler PW, Zheng M. Providence, RI: American Mathematical Society; 2000:377–383.
Gallo G, Scutellà M: Directed hypergraphs as a modelling paradigm. Decisions in Economics and Finance 1998, 21: 97–123. 10.1007/BF02735318
Ausiello G, Franciosa PG, Frigioni D: Directed hypergraphs: problems, algorithmic results, and a novel decremental approach. In ICTCS, Volume 2202 of Lecture Notes in Computer Science. Edited by: Restivo A, Rocca SRD, Roversi L. Springer; 2001:312327.
Kauffman KJ, Prakash P, Edwards JS: Advances influx balance analysis. Curr Opin Biotechnol 2003, 14: 491–496. 10.1016/j.copbio.2003.08.001
Hatzimanikatis V, Emmerling M, Sauer U, Bailey JE: Application of mathematical tools for metabolic design of microbial ethanol production. Biotech Bioeng 1998, 58: 154–161. 10.1002/(SICI)1097-0290(19980420)58:2/3<154::AID-BIT7>3.0.CO;2-K
Schuster S, Hilgetag C: On elementary flux modes in biochemical reaction systems at steady state. J Biol Syst 1994, 2: 165–182. 10.1142/S0218339094000131
Schuster S, Fell DA, Dandekar T: A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic networks. Nat Biotechnol 2000, 18: 326–332. 10.1038/73786
Klamt S, Stelling J: Two approaches for metabolic pathway analysis? Trends Biotechnol 2003, 21: 64–69. 10.1016/S0167-7799(02)00034-3
Klamt S, Stelling J: Combinatorial complexity of pathway analysis in metabolic networks. Mol Biol Rep 2002, 29: 233–236. 10.1023/A:1020390132244
Ip K, Colijn C, Lun DS: Analysis of Complex Metabolic Behavior through Pathway Decomposition. BMC Systems Biology 2011, 5: 91. 10.1186/1752-0509-5-91
Acuña V, Chierichetti F, Lacroix V, Marchetti-Spaccamela A, Sagot MF, Stougie L: Modes and cuts in metabolic networks: Complexity and algorithms. BioSystems 2009, 95: 51–60. 10.1016/j.biosystems.2008.06.015
Özturan C: On finding hypercycles in chemical reaction networks. Appl Math Letters 2008, 21: 881–884. 10.1016/j.aml.2007.07.031
Acuña V, Marchetti-Spaccamela A, Sagot MF, Stougie L: A note on the complexity of finding and enumerating elementary modes. Biosystems 2010, 99: 210–214. 10.1016/j.biosystems.2009.11.004
Klamt S, Gilles ED: Minimal cut sets in biochemical reaction networks. Bioinformatics 2004, 20: 226–234. 10.1093/bioinformatics/btg395
Klamt S: Generalized concept of minimal cut sets in biochemical networks. Biosystems 2006, 83: 233–247. 10.1016/j.biosystems.2005.04.009
Pitkänen E, Rantanen A, Rousu J, Ukkonen E: Finding Feasible Pathways in Metabolic Networks. In Panhellenic Conference on Informatics, Volume 3746. Edited by: Bozanis P, Houstis EN. Heidelberg: Springer; 2005:123–133.
Kaleta C, Centler F, Dittrich P: Analyzing molecular reaction networks: from pathways to chemical organizations. Mol Biotechnol 2006, 34: 117–123. 10.1385/MB:34:2:117
Centler F, Kaleta C, Speroni di Fenizio P, Dittrich P: Computing chemical organizations in biological networks. Bioinformatics 2008, 24: 1611–1618. 10.1093/bioinformatics/btn228
Kaleta C, Richter S, Dittrich P: Using chemical organization theory for model checking. Bioinformatics 2009, 25: 1915–1922. 10.1093/bioinformatics/btp332
Benkö G, Centler F, Dittrich P, Flamm C, Stadler BMR, Stadler PF: A Topological Approach to Chemical Organizations. Alife 2009, 15: 71–88.
Domach MM: Introduction to biomedical engineering. Upper Saddle River: Pearson Prentice Hall; 2004.
Ahuja RK, Magnanti TL, Orlin J: Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice Hall; 1993.
Kun Á, Papp B, Szathmáry E: Computational identification of obligatorily autocatalytic replicators embedded in metabolic networks. Genome Biol 2008, 9: R51. 10.1186/gb-2008-9-3-r51
Hordijk W, Steel M: Detecting autocatalytic, self-sustaining sets in chemical reaction systems. J Theor Biol 2004, 227: 451–461. 10.1016/j.jtbi.2003.11.020
Cambini R, Gallo G, Scutellà MG: Flows on hypergraphs. Mathematical Programming 1997, 78: 195–217.
Garey MR, Johnson DS: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY: W. H. Freeman & Co; 1979.
Garey MR, Johnson DS: Complexity results for multiprocessor scheduling under resource constraints. SIAM J Comput 1975, 4: 397–411. 10.1137/0204035
Hulett H, Will TG, Woeginger GJ: Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. Operations Res Let 2008, 36: 594–596. 10.1016/j.orl.2008.05.004
Fortnow L: The Status of the P versus NP problem. Comm ACM 2009,52(9):78–86. 10.1145/1562164.1562186
Karp RM: Reducibility among combinatorial problems. In Complexity of Computer Computations. Edited by: Miller RE, Thatcher JW. NY: Plenum Press; 1972.
Coleman TF, Pothen A: The null space problem I: Complexity. SIAM J Alg Disc Meth 1986, 7: 527–537. 10.1137/0607059