skip to main content
Idioma:

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

Andersen, Jakob L ; Flamm, Christoph ; Merkle, Daniel ; Stadler, Peter F

arXiv.org, 2011-10

Ithaca: Cornell University Library, arXiv.org

Texto completo disponível

Citações Citado por
  • Título:
    Maximizing Output and Recognizing Autocatalysis in Chemical Reaction Networks is NP-Complete
  • Autor: Andersen, Jakob L ; Flamm, Christoph ; Merkle, Daniel ; Stadler, Peter F
  • Assuntos: Algorithms ; Autocatalysis ; Chemical reactions ; Combinatorial analysis ; Computation ; Computer Science - Discrete Mathematics ; Mass flow ; Maximization ; Metabolism ; Networks ; Optimization ; Organic chemistry ; Polynomials ; Quantitative Biology - Molecular Networks ; Software
  • É parte de: arXiv.org, 2011-10
  • Descrição: 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.
  • Editor: Ithaca: Cornell University Library, arXiv.org
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.