{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T21:12:53Z","timestamp":1792185173769,"version":"4.4.0"},"reference-count":60,"publisher":"Oxford University Press (OUP)","issue":"15","license":[{"start":{"date-parts":[[2021,2,3]],"date-time":"2021-02-03T00:00:00Z","timestamp":1612310400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Italian Ministry for Research","award":["2017TWRCNB"],"award-info":[{"award-number":["2017TWRCNB"]}]},{"DOI":"10.13039\/501100004836","name":"Independent Research Fund Denmark","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"name":"DFF RP1 Project REDUCTO","award":["9040-00224B"],"award-info":[{"award-number":["9040-00224B"]}]},{"name":"Danish Poul Due Jensen Foundation","award":["883901"],"award-info":[{"award-number":["883901"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,8,9]]},"abstract":"<jats:title>Abstrtact<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Stochastic reaction networks are a widespread model to describe biological systems where the presence of noise is relevant, such as in cell regulatory processes. Unfortunately, in all but simplest models the resulting discrete state-space representation hinders analytical tractability and makes numerical simulations expensive. Reduction methods can lower complexity by computing model projections that preserve dynamics of interest to the user.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We present an exact lumping method for stochastic reaction networks with mass-action kinetics. It hinges on an equivalence relation between the species, resulting in a reduced network where the dynamics of each macro-species is stochastically equivalent to the sum of the original species in each equivalence class, for any choice of the initial state of the system. Furthermore, by an appropriate encoding of kinetic parameters as additional species, the method can establish equivalences that do not depend on specific values of the parameters. The method is supported by an efficient algorithm to compute the largest species equivalence, thus the maximal lumping. The effectiveness and scalability of our lumping technique, as well as the physical interpretability of resulting reductions, is demonstrated in several models of signaling pathways and epidemic processes on complex networks.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The algorithms for species equivalence have been implemented in the software tool ERODE, freely available for download from https:\/\/www.erode.eu.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btab081","type":"journal-article","created":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T21:30:48Z","timestamp":1611869448000},"page":"2175-2182","source":"Crossref","is-referenced-by-count":25,"title":["Exact maximal reduction of stochastic reaction networks by species lumping"],"prefix":"10.1093","volume":"37","author":[{"given":"Luca","family":"Cardelli","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford , Oxford 34127, OX1 3QD, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Isabel Cristina","family":"Perez-Verona","sequence":"additional","affiliation":[{"name":"IMT School for Advanced Studies , Lucca 55100, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6018-5989","authenticated-orcid":false,"given":"Mirco","family":"Tribastone","sequence":"additional","affiliation":[{"name":"IMT School for Advanced Studies , Lucca 55100, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Max","family":"Tschaikowski","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Aalborg , Aalborg 34127, 9220, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2606-7241","authenticated-orcid":false,"given":"Andrea","family":"Vandin","sequence":"additional","affiliation":[{"name":"Sant\u2019Anna School of Advanced Studies , Pisa 56127, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tabea","family":"Waizmann","sequence":"additional","affiliation":[{"name":"IMT School for Advanced Studies , Lucca 55100, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2021,2,3]]},"reference":[{"key":"2023061310411778900_btab081-B1","first-page":"45","author":"Autant","year":"1992"},{"issue":"1","key":"2023061310411778900_btab081-B2","doi-asserted-by":"crossref","DOI":"10.3390\/sym10010029","article-title":"How symmetric are real-world graphs? A large-scale study","volume":"10","author":"Ball","year":"2018","journal-title":"Symmetry"},{"key":"2023061310411778900_btab081-B3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2016.12.003","article-title":"Multiple-scale stochastic processes: decimation, averaging and beyond","volume":"670","author":"Bo","year":"2017","journal-title":"Phys. Rep"},{"key":"2023061310411778900_btab081-B4","doi-asserted-by":"crossref","first-page":"056122","DOI":"10.1103\/PhysRevE.70.056122","article-title":"Models of social networks based on social distance attachment","volume":"70","author":"Bogu\u00f1\u00e1","year":"2004","journal-title":"Phys. Rev. E"},{"key":"2023061310411778900_btab081-B5","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1002\/spe.587","article-title":"UbiCrawler: a scalable fully distributed web crawler","volume":"34","author":"Boldi","year":"2004","journal-title":"Softw. Pract. Exp"},{"key":"2023061310411778900_btab081-B6","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s11047-018-9723-9","article-title":"Computing with chemical reaction networks: a tutorial","volume":"18","author":"Brijder","year":"2019","journal-title":"Nat. Comput"},{"key":"2023061310411778900_btab081-B7","doi-asserted-by":"crossref","first-page":"59","DOI":"10.2307\/3215235","article-title":"Exact and ordinary lumpability in finite Markov Chains","volume":"31","author":"Buchholz","year":"1994","journal-title":"J. Appl. Prob"},{"key":"2023061310411778900_btab081-B8","doi-asserted-by":"crossref","first-page":"2915","DOI":"10.1214\/15-AAP1166","article-title":"Elimination of intermediate species in multiscale stochastic reaction networks","volume":"26","author":"Cappelletti","year":"2016","journal-title":"Ann. Appl. Prob"},{"key":"2023061310411778900_btab081-B9","first-page":"226","author":"Cardelli","year":"2015"},{"key":"2023061310411778900_btab081-B10","first-page":"310","author":"Cardelli","year":"2017"},{"key":"2023061310411778900_btab081-B11","first-page":"466","author":"Cardelli","year":"2017"},{"key":"2023061310411778900_btab081-B12","doi-asserted-by":"crossref","first-page":"056111","DOI":"10.1103\/PhysRevE.85.056111","article-title":"Second-order mean-field susceptible-infected-susceptible epidemic threshold","volume":"85","author":"Cator","year":"2012","journal-title":"Phys. Rev. E"},{"key":"2023061310411778900_btab081-B13","doi-asserted-by":"crossref","first-page":"582","DOI":"10.1038\/msb.2012.15","article-title":"A dynamical model of the spindle position checkpoint","volume":"8","author":"Caydasi","year":"2012","journal-title":"Mol. Syst. Biol"},{"key":"2023061310411778900_btab081-B14","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/S0020-0190(03)00343-0","article-title":"Optimal state-space lumping in Markov chains","volume":"87","author":"Derisavi","year":"2003","journal-title":"Inf. Process. Lett"},{"key":"2023061310411778900_btab081-B15","first-page":"30","article-title":"Equilibrium traffic assignment on an aggregated highway network for sketch planning","volume":"994","author":"Eash","year":"1983","journal-title":"Transp. Res. Rec"},{"key":"2023061310411778900_btab081-B16","doi-asserted-by":"crossref","first-page":"1183","DOI":"10.1126\/science.1070919","article-title":"Stochastic gene expression in a single cell","volume":"297","author":"Elowitz","year":"2002","journal-title":"Science"},{"key":"2023061310411778900_btab081-B17","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.tcs.2011.12.059","article-title":"Lumpability abstractions of rule-based systems","volume":"431","author":"Feret","year":"2012","journal-title":"Theor. Comput. Sci"},{"key":"2023061310411778900_btab081-B18","first-page":"527","article-title":"Stochastic fragments: a framework for the exact reduction of the stochastic semantics of rule-based models","volume":"7","author":"Feret","year":"2013","journal-title":"Int. J. Softw. Inform"},{"key":"2023061310411778900_btab081-B19","doi-asserted-by":"crossref","first-page":"2340","DOI":"10.1021\/j100540a008","article-title":"Exact stochastic simulation of coupled chemical reactions","volume":"81","author":"Gillespie","year":"1977","journal-title":"J. Phys. Chem"},{"key":"2023061310411778900_btab081-B20","doi-asserted-by":"crossref","first-page":"244112","DOI":"10.1063\/1.3050350","article-title":"Enhanced identification and exploitation of time scales for model reduction in stochastic chemical kinetics","volume":"129","author":"G\u00f3mez-Uribe","year":"2008","journal-title":"J. Chem. Phys"},{"key":"2023061310411778900_btab081-B21","doi-asserted-by":"crossref","first-page":"6475","DOI":"10.1093\/emboj\/19.23.6475","article-title":"Nud1p links astral microtubule organization and the control of exit from mitosis","volume":"19","author":"Gruneberg","year":"2000","journal-title":"EMBO J"},{"key":"2023061310411778900_btab081-B22","doi-asserted-by":"crossref","first-page":"14617","DOI":"10.1073\/pnas.0507322102","article-title":"Multisite protein phosphorylation makes a good threshold but can be a poor switch","volume":"102","author":"Gunawardena","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023061310411778900_btab081-B23","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1002\/bies.950171112","article-title":"Does replication-induced transcription regulate synthesis of the myriad low copy number proteins of Escherichia coli?","volume":"17","author":"Guptasarma","year":"1995","journal-title":"BioEssays"},{"key":"2023061310411778900_btab081-B24","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/978-3-642-02658-4_27","volume-title":"International Conference on Computer Aided Verification","author":"Henzinger","year":"2009"},{"key":"2023061310411778900_btab081-B25","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1006\/inco.1996.0057","article-title":"Bisimulation from open maps","volume":"127","author":"Joyal","year":"1996","journal-title":"Inform. Comput"},{"key":"2023061310411778900_btab081-B26","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1214\/12-AAP841","article-title":"Separation of time-scales and model reduction for stochastic reaction networks","volume":"23","author":"Kang","year":"2013","journal-title":"Ann. Appl. Prob"},{"key":"2023061310411778900_btab081-B27","volume-title":"Finite Markov Chains","author":"Kemeny","year":"1976"},{"key":"2023061310411778900_btab081-B28","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1098\/rspa.1927.0118","article-title":"A contribution to the mathematical theory of epidemics","volume":"115","author":"Kermack","year":"1927","journal-title":"Proc. R. Soc. Lond. Ser. A"},{"key":"2023061310411778900_btab081-B29","first-page":"1343","author":"Kunegis","year":"2013"},{"key":"2023061310411778900_btab081-B30","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1217299.1217301","article-title":"Graph evolution: densification and shrinking diameters","volume":"1","author":"Leskovec","year":"2007","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"2023061310411778900_btab081-B31","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1146\/annurev.genet.37.042203.120656","article-title":"The spindle assembly and spindle position checkpoints","volume":"37","author":"Lew","year":"2003","journal-title":"Annu. Rev. Genet"},{"key":"2023061310411778900_btab081-B32","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1186\/1752-0509-4-92","article-title":"BioModels database: an enhanced, curated and annotated resource for published quantitative kinetic models","volume":"4","author":"Li","year":"2010","journal-title":"BMC Syst. Biol"},{"key":"2023061310411778900_btab081-B33","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1038\/nrn753","article-title":"The molecular basis of CaMKII function in synaptic and behavioural memory","volume":"3","author":"Lisman","year":"2002","journal-title":"Nat. Rev. Neurosci"},{"key":"2023061310411778900_btab081-B34","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1038\/nrn3192","article-title":"Mechanisms of CaMKII action in long-term potentiation","volume":"13","author":"Lisman","year":"2012","journal-title":"Nat. Rev. Neurosci"},{"key":"2023061310411778900_btab081-B35","doi-asserted-by":"crossref","first-page":"48003","DOI":"10.1209\/0295-5075\/103\/48003","article-title":"Pair quenched mean-field theory for the susceptible-infected-susceptible model on complex networks","volume":"103","author":"Mata","year":"2013","journal-title":"Urophys. Lett"},{"key":"2023061310411778900_btab081-B36","first-page":"548","author":"McAuley","year":"2012"},{"key":"2023061310411778900_btab081-B37","doi-asserted-by":"crossref","first-page":"044104","DOI":"10.1063\/1.2145882","article-title":"The finite state projection algorithm for the solution of the chemical master equation","volume":"124","author":"Munsky","year":"2006","journal-title":"J. Chem. Phys"},{"key":"2023061310411778900_btab081-B38","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1137\/0216062","article-title":"Three partition refinement algorithms","volume":"16","author":"Paige","year":"1987","journal-title":"SIAM J. Comput"},{"key":"2023061310411778900_btab081-B39","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1103\/RevModPhys.87.925","article-title":"Epidemic processes in complex networks","volume":"87","author":"Pastor-Satorras","year":"2015","journal-title":"Rev. Modern Phys"},{"key":"2023061310411778900_btab081-B40","doi-asserted-by":"crossref","first-page":"e1000675","DOI":"10.1371\/journal.pcbi.1000675","article-title":"A dynamic model of interactions of Ca2+, calmodulin, and catalytic subunits of Ca2+\/calmodulin-dependent protein kinase II","volume":"6","author":"Pepke","year":"2010","journal-title":"PLoS Comput. Biol"},{"key":"2023061310411778900_btab081-B41","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.molcel.2005.05.030","article-title":"Kin4 kinase delays mitotic exit in response to spindle alignment defects","volume":"19","author":"Pereira","year":"2005","journal-title":"Mol. Cell"},{"key":"2023061310411778900_btab081-B42","author":"Rossi","year":"2015"},{"key":"2023061310411778900_btab081-B43","first-page":"1","article-title":"Exact linear lumping in abstract spaces","volume":"21","author":"R\u00f3zsa","year":"2003","journal-title":"Electron. J. Qual. Theory Differ. Equ"},{"key":"2023061310411778900_btab081-B44","doi-asserted-by":"crossref","first-page":"3177","DOI":"10.1111\/j.1742-4658.2009.07027.x","article-title":"Multisite protein phosphorylation \u2013 from molecular mechanisms to kinetic models","volume":"276","author":"Salazar","year":"2009","journal-title":"FEBS J"},{"key":"2023061310411778900_btab081-B45","doi-asserted-by":"crossref","first-page":"2457","DOI":"10.1093\/bioinformatics\/btr401","article-title":"Stochkit2: software for discrete stochastic simulation of biochemical systems with events","volume":"27","author":"Sanft","year":"2011","journal-title":"Bioinformatics"},{"key":"2023061310411778900_btab081-B46","doi-asserted-by":"crossref","first-page":"093001","DOI":"10.1088\/1751-8121\/aa54d9","article-title":"Approximation and inference methods for stochastic biochemical kinetics\u2014a tutorial review","volume":"50","author":"Schnoerr","year":"2017","journal-title":"J. Phys. A Math. Theor"},{"key":"2023061310411778900_btab081-B47","doi-asserted-by":"crossref","first-page":"13968","DOI":"10.1073\/pnas.0606433103","article-title":"Ca2+\/calmodulin-dependent protein kinase II (CaMKII) is activated by calmodulin with two bound calciums","volume":"103","author":"Shifman","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023061310411778900_btab081-B48","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s00285-010-0344-x","article-title":"Exact epidemic models on graphs using graph-automorphism driven lumping","volume":"62","author":"Simon","year":"2011","journal-title":"J. Math. Biol"},{"key":"2023061310411778900_btab081-B49","doi-asserted-by":"crossref","first-page":"10546","DOI":"10.1073\/pnas.0809340106","article-title":"Adiabatic coarse-graining and simulations of stochastic biochemical networks","volume":"106","author":"Sinitsyn","year":"2009","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023061310411778900_btab081-B50","doi-asserted-by":"crossref","first-page":"214105","DOI":"10.1063\/1.4936394","article-title":"Model reduction for stochastic chemical systems with abundant species","volume":"143","author":"Smith","year":"2015","journal-title":"J. Chem. Phys"},{"key":"2023061310411778900_btab081-B51","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1038\/nmeth.1546","article-title":"Efficient modeling, simulation and coarse-graining of biological complexity with NFsim","volume":"8","author":"Sneddon","year":"2011","journal-title":"Nat. Methods"},{"key":"2023061310411778900_btab081-B52","doi-asserted-by":"crossref","first-page":"1449","DOI":"10.1007\/s11538-017-0277-2","article-title":"Methods of model reduction for large-scale biological systems: a survey of current methods and trends","volume":"79","author":"Snowden","year":"2017","journal-title":"Bull. Math. Biol"},{"key":"2023061310411778900_btab081-B53","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1038\/nature08102","article-title":"Unlimited multistability in multisite phosphorylation systems","volume":"460","author":"Thomson","year":"2009","journal-title":"Nature"},{"key":"2023061310411778900_btab081-B54","first-page":"38","author":"Valmari","year":"2010"},{"key":"2023061310411778900_btab081-B55","volume-title":"Stochastic Processes in Physics and Chemistry","author":"Van Kampen","year":"2007","edition":"3rd edn"},{"key":"2023061310411778900_btab081-B56","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00607-011-0155-y","article-title":"The n-intertwined SIS epidemic network model","volume":"93","author":"Van Mieghem","year":"2011","journal-title":"Computing"},{"key":"2023061310411778900_btab081-B57","doi-asserted-by":"crossref","first-page":"e1004012","DOI":"10.1371\/journal.pcbi.1004012","article-title":"150 years of the mass action law","volume":"11","author":"Voit","year":"2015","journal-title":"PLoS Comput. Biol"},{"key":"2023061310411778900_btab081-B58","doi-asserted-by":"crossref","first-page":"036603","DOI":"10.1088\/1361-6633\/aa5398","article-title":"Unification of theoretical approaches for epidemic spreading on complex networks","volume":"80","author":"Wang","year":"2017","journal-title":"Rep. Prog. Phys"},{"key":"2023061310411778900_btab081-B59","author":"Zafarani","year":"2009"},{"key":"2023061310411778900_btab081-B60","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1145\/1052812.1052825","article-title":"Collecting the Internet AS-level topology","volume":"35","author":"Zhang","year":"2005","journal-title":"SIGCOMM Comput. Commun. Rev"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btab081\/36287939\/btab081.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/15\/2175\/50578760\/btab081.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/15\/2175\/50578760\/btab081.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T10:42:31Z","timestamp":1686652951000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/15\/2175\/6126804"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2021,2,3]]},"references-count":60,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2021,8,9]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab081","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,8,1]]},"published":{"date-parts":[[2021,2,3]]}}}