On the complexity of reconstructing chemical reaction networks
From MaRDI portal
Publication:2254073
Abstract: The analysis of the structure of chemical reaction networks is crucial for a better understanding of chemical processes. Such networks are well described as hypergraphs. However, due to the available methods, analyses regarding network properties are typically made on standard graphs derived from the full hypergraph description, e.g. on the so-called species and reaction graphs. However, a reconstruction of the underlying hypergraph from these graphs is not necessarily unique. In this paper, we address the problem of reconstructing a hypergraph from its species and reaction graph and show NP-completeness of the problem in its Boolean formulation. Furthermore we study the problem empirically on random and real world instances in order to investigate its computational limits in practice.
Recommendations
- On the computational complexity of reaction systems, revisited
- A network dynamics approach to chemical reaction networks
- On design and analysis of chemical reaction network algorithms
- Polynomial time algorithms to determine weakly reversible realizations of chemical reaction networks
- On the relation between reactions and complexes of (bio)chemical reaction networks
- A compositional framework for reaction networks
- Identifiability of chemical reaction networks
Cites work
- Collective dynamics of `small-world' networks
- Concordant chemical reaction networks and the species-reaction graph
- Directed hypergraphs and applications
- Graph theory and qualitative analysis of reaction networks
- Graph-theoretic methods for the analysis of chemical and biochemical networks. I. Multistability and oscillations in ordinary differential equation models
- scientific article; zbMATH DE number 3771418 (Why is no real title available?)
- scientific article; zbMATH DE number 50596 (Why is no real title available?)
- scientific article; zbMATH DE number 3575605 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256679 (Why is no real title available?)
- scientific article; zbMATH DE number 1522768 (Why is no real title available?)
- scientific article; zbMATH DE number 5493266 (Why is no real title available?)
- Multiple Equilibria in Complex Chemical Reaction Networks: II. The Species-Reaction Graph
- Theory and Applications of Satisfiability Testing
Cited in
(16)- Metabolic networks are NP-hard to reconstruct
- Polynomial time algorithms to determine weakly reversible realizations of chemical reaction networks
- Independent decompositions of chemical reaction networks
- Netscan: a procedure for generating reaction networks by size
- Complexity results for autocatalytic network models
- Reachability analysis of low-order discrete state reaction networks obeying conservation laws
- Boolean constraint satisfaction problems for reaction networks
- Enumeration approach to computing chemical equilibria
- scientific article; zbMATH DE number 1522768 (Why is no real title available?)
- Solving moment hierarchies for chemical reaction networks
- Comparing Chemical Reaction Networks
- Automated reaction mapping
- Reconstructing biochemical cluster networks
- Testing binomiality of chemical reaction networks using comprehensive Gröbner systems
- Identifiability of chemical reaction networks
- On finding hypercycles in chemical reaction networks
Describes a project that uses
Uses Software
This page was built for publication: On the complexity of reconstructing chemical reaction networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2254073)
