×

Counting substrate cycles in topologically restricted metabolic networks. (English) Zbl 1491.92049

Kari, Jarkko (ed.) et al., Unveiling dynamics and complexity. 13th conference on computability in Europe, CiE 2017, Turku, Finland, June 12–16, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10307, 129-140 (2017).
Summary: Substrate cycles in metabolic networks play a role in various forms of homeostatic regulation, ranging from thermogenesis to the buffering and redistribution of steady-state populations of metabolites. While the general problem of enumerating these cycles is #P-hard, it is unclear if this result holds for realistic networks where e.g. pathological vertex degree distributions or minors may not exist. We attempt to address this gap by showing that the problem of counting directed substrate cycles (#DirectedCycle) remains #P-complete (implying #P-hardness for enumeration) for any superclass of cubic weakly-3-connected bipartite planar digraphs, and at the limit where all reactions are reversible, that the problem of counting undirected substrate cycles (#UndirectedCycle) is #P-complete for any superclass of cubic 3-connected bipartite planar graphs where the problem of counting Hamiltonian cycles is #P-complete. Lastly, we show that unless \(NP=RP\), no FPRAS can exist for either counting problem whenever the Hamiltonian cycle decision problem is NP-complete.
For the entire collection see [Zbl 1362.68012].

MSC:

92C40 Biochemistry, molecular biology
92C42 Systems biology, networks

Software:

KEGG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Schuster, S., Hilgetag, C.: On elementary flux modes in biochemical reaction systems at steady state. J. Biol. Syst. 2, 165–182 (1994) · doi:10.1142/S0218339094000131
[2] Schilling, C.H., Letscher, D., Palsson, B.O.: Theory for the systemic definition of metabolic pathways and their use in interpreting metabolic function from a pathway-oriented perspective. J. Theor. Biol. 203, 229–248 (2000) · doi:10.1006/jtbi.2000.1073
[3] Clark, M.G., Bloxham, D.P., Holland, P.C., Lardy, H.A.: Estimation of the fructose diphosphatase-phos-phofructokinase substrate cycle in the flight muscle of Bombus affinis. Biochem. J. 134, 589–597 (1973) · doi:10.1042/bj1340589
[4] Kazak, L., et al.: A Creatine-driven substrate cycle enhances energy expenditure and thermogenesis in beige fat. Cell 163, 643–655 (2015) · doi:10.1016/j.cell.2015.09.035
[5] Newsholme, E.A., Crabtree, B.: Substrate cycles in metabolic regulation and in heat generation. Biochem. Soc. Symp. 41, 61–110 (1976)
[6] Hervagault, J.F., Canu, S.: Bistability and irreversible transitions in a simple substrate cycle. J. Theor. Biol. 127, 439–449 (1987) · doi:10.1016/S0022-5193(87)80141-8
[7] Adolfsen, K.J., Brynildsen, M.P.: Futile cycling increases sensitivity toward oxidative stress in Escherichia coli. Metab. Eng. 29, 26–35 (2015) · doi:10.1016/j.ymben.2015.02.006
[8] Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, New York (2009) · Zbl 1193.68112 · doi:10.1017/CBO9780511804090
[9] Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103 (1972) · doi:10.1007/978-1-4684-2001-2_9
[10] Yamamoto, M.: Approximately counting paths and cycles in a graph. Discrete Appl. Math. 217, 381–387 (2017) · Zbl 1358.05140 · doi:10.1016/j.dam.2016.09.002
[11] Acuna, V., et al.: Modes and cuts in metabolic networks: complexity and algorithms. BioSystems 95, 51–60 (2009) · doi:10.1016/j.biosystems.2008.06.015
[12] Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189–201 (1979) · Zbl 0415.68008 · doi:10.1016/0304-3975(79)90044-6
[13] Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27, 119–123 (1988) · Zbl 0654.68086 · doi:10.1016/0020-0190(88)90065-8
[14] Acuna, V., et al.: A note on the complexity of finding and enumerating elementary modes. BioSystems 99, 210–214 (2010) · doi:10.1016/j.biosystems.2009.11.004
[15] Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N., Barabasi, A.L.: The large-scale organization of metabolic networks. Nature 407, 651–654 (2000) · doi:10.1038/35036627
[16] Kanehisa, M., Goto, S.: KEGG: Kyoto encyclopedia of genes and genomes. Nucleic Acids Res. 28, 27–30 (2000) · Zbl 05435931 · doi:10.1093/nar/28.1.27
[17] Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 410–421 (1979) · Zbl 0419.68082 · doi:10.1137/0208032
[18] Liskiewicz, M., Ogihara, M., Toda, S.: The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. Theor. Comput. Sci. 304, 129–156 (2003) · Zbl 1051.68116 · doi:10.1016/S0304-3975(03)00080-X
[19] Karp, R.M., Luby, M.: Monte-Carlo algorithms for enumeration and reliability problems. In: Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 56–64 (1983) · Zbl 0596.90033 · doi:10.1109/SFCS.1983.35
[20] Dyer, M., Greenhill, C., Goldberg, L.A., Jerrum, M.: On the relative complexity of approximate counting problems. Algorithmica 38, 471–500 (2004) · Zbl 1138.68424 · doi:10.1007/s00453-003-1073-y
[21] Plesnik, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett. 8, 199–201 (1979) · Zbl 0399.68070 · doi:10.1016/0020-0190(79)90023-1
[22] Zuckerman, D.: On unapproximable versions of NP-complete problems. SIAM J. Comput. 25, 1293–1304 (1996) · Zbl 0864.68039 · doi:10.1137/S0097539794266407
[23] Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704–714 (1976) · Zbl 0346.05110 · doi:10.1137/0205049
[24] Akiyama, T., Nishizeki, T., Saito, N.: NP-completeness of the Hamiltonian cycle problem for bipartite graphs. J. Inf. Process. 3, 73–76 (1980) · Zbl 0444.68058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.