{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T13:23:47Z","timestamp":1761744227406},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Boolean networks (BNs) are commonly used to model genetic regulatory networks (GRNs). Due to the sensibility of the dynamical behavior to changes in the updating scheme (order in which the nodes of a network update their state values), it is increasingly common to use different updating rules in the modeling of GRNs to better capture an observed biological phenomenon and thus to obtain more realistic models.<\/jats:p>\n               <jats:p>In Aracena et\u00a0al. equivalence classes of deterministic update schedules in BNs, that yield exactly the same dynamical behavior of the network, were defined according to a certain label function on the arcs of the interaction digraph defined for each scheme. Thus, the interaction digraph so labeled (update digraphs) encode the non-equivalent schemes.<\/jats:p>\n               <jats:p>Results: We address the problem of enumerating all non-equivalent deterministic update schedules of a given BN. First, we show that it is an intractable problem in general. To solve it, we first construct an algorithm that determines the set of update digraphs of a BN. For that, we use divide and conquer methodology based on the structural characteristics of the interaction digraph. Next, for each update digraph we determine a scheme associated. This algorithm also works in the case where there is a partial knowledge about the relative order of the updating of the states of the nodes. We exhibit some examples of how the algorithm works on some GRNs published in the literature.<\/jats:p>\n               <jats:p>Availability and implementation: An executable file of the UpdateLabel algorithm made in Java and the files with the outputs of the algorithms used with the GRNs are available at: www.inf.udec.cl\/ \u223clilian\/UDE\/<\/jats:p>\n               <jats:p>Contact: \u00a0lilisalinas@udec.cl<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv628","type":"journal-article","created":{"date-parts":[[2015,11,1]],"date-time":"2015-11-01T00:38:37Z","timestamp":1446338317000},"page":"722-729","source":"Crossref","is-referenced-by-count":7,"title":["Enumeration and extension of non-equivalent deterministic update schedules in Boolean networks"],"prefix":"10.1093","volume":"32","author":[{"given":"Eduardo","family":"Palma","sequence":"first","affiliation":[{"name":"1 Departamento de Ingenier\u00eda Inform\u00e1tica y Ciencias de la Computaci\u00f3n, Universidad de Concepci\u00f3n, Piso 3, Concepci\u00f3n, Chile."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lilian","family":"Salinas","sequence":"additional","affiliation":[{"name":"1 Departamento de Ingenier\u00eda Inform\u00e1tica y Ciencias de la Computaci\u00f3n, Universidad de Concepci\u00f3n, Piso 3, Concepci\u00f3n, Chile."},{"name":"3 Centro de Investigaci\u00f3n en Ingenier\u00eda Matem\u00e1tica, CI2MA, Casilla 160-C, Concepci\u00f3n, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julio","family":"Aracena","sequence":"additional","affiliation":[{"name":"2 Departamento de Ingenier\u00eda Matem\u00e1tica, Universidad de Concepci\u00f3n, Casilla 160-C, Concepci\u00f3n, Chile and"},{"name":"3 Centro de Investigaci\u00f3n en Ingenier\u00eda Matem\u00e1tica, CI2MA, Casilla 160-C, Concepci\u00f3n, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2015,10,31]]},"reference":[{"key":"2023020110442113800_btv628-B1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0022-5193(03)00035-3","article-title":"The topology of the regulatory interactions predicts the expression pattern of the drosophila segment polarity genes","volume":"223","author":"Albert","year":"2003","journal-title":"J. Theor. Biol."},{"key":"2023020110442113800_btv628-B2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.biosystems.2009.03.006","article-title":"On the robustness of update schedules in Boolean networks","volume":"97","author":"Aracena","year":"2009","journal-title":"Biosystems"},{"key":"2023020110442113800_btv628-B3","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1016\/j.dam.2010.10.010","article-title":"Combinatorics on update digraphs in Boolean networks","volume":"159","author":"Aracena","year":"2011","journal-title":"Discrete Appl. Math."},{"key":"2023020110442113800_btv628-B4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2012.07.003","article-title":"Limit cycles and update digraphs in Boolean networks","volume":"161","author":"Aracena","year":"2013","journal-title":"Discrete Appl. Math."},{"key":"2023020110442113800_btv628-B5","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/j.mbs.2013.01.007","article-title":"On the number of different dynamics in boolean networks with deterministic update schedules","volume":"242","author":"Aracena","year":"2013","journal-title":"Math. Biosci."},{"key":"2023020110442113800_btv628-B6","doi-asserted-by":"crossref","first-page":"e1672","DOI":"10.1371\/journal.pone.0001672","article-title":"Boolean network model predicts cell cycle sequence of fission yeast","volume":"3","author":"Davidich","year":"2008","journal-title":"PloS One"},{"key":"2023020110442113800_btv628-B7","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s10441-014-9229-5","article-title":"Stability, complexity and robustness in population dynamics","volume":"62","author":"Demongeot","year":"2014","journal-title":"Acta Biotheoretica"},{"key":"2023020110442113800_btv628-B8","volume-title":"Robustesse des r\u00e9seaux d\u2019automates boole\u00e9ns a seuil aux modes d\u2019it\u00e9ration. Application a la mod\u00e9lisation des r\u00e9seaux de r\u00e9gulation g\u00e9n\u00e9tique","author":"Elena","year":"2009"},{"key":"2023020110442113800_btv628-B9","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1093\/bioinformatics\/btl210","article-title":"Dynamical analysis of a generic Boolean model for the control of the mammalian cell cycle","volume":"22","author":"Faur\u00e9","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020110442113800_btv628-B10","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1016\/j.aam.2011.11.009","article-title":"Disjunctive networks and update schedules","volume":"48","author":"Goles","year":"2012","journal-title":"Adv. Appl. Math."},{"key":"2023020110442113800_btv628-B11","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/j.tcs.2007.09.008","article-title":"Comparison between parallel and serial dynamics of Boolean networks","volume":"396","author":"Goles","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"2023020110442113800_btv628-B12","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1007\/s11538-012-9794-1","article-title":"Deconstruction and dynamical robustness of regulatory networks: application to the yeast cell cycle networks","volume":"75","author":"Goles","year":"2013","journal-title":"Bull. Math. Biol."},{"key":"2023020110442113800_btv628-B13","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/0022-5193(69)90015-0","article-title":"Metabolic stability and epigenesis in randomly connected nets","volume":"22","author":"Kauffman","year":"1969","journal-title":"J. Theor. Biol."},{"key":"2023020110442113800_btv628-B14","doi-asserted-by":"crossref","first-page":"14796","DOI":"10.1073\/pnas.2036429100","article-title":"Random Boolean network models and the yeast transcriptional network","volume":"100","author":"Kauffman","year":"2003","journal-title":"Proc. Natl Acad. Sci."},{"key":"2023020110442113800_btv628-B15","doi-asserted-by":"crossref","first-page":"4781","DOI":"10.1073\/pnas.0305937101","article-title":"The yeast cell-cycle network is robustly designed","volume":"101","author":"Li","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020110442113800_btv628-B16","doi-asserted-by":"crossref","first-page":"e55946","DOI":"10.1371\/journal.pone.0055946","article-title":"Canalization and control in automata networks: Body segmentation in drosophila melanogaster","volume":"8","author":"Marques-Pita","year":"2013","journal-title":"PLoS ONE"},{"key":"2023020110442113800_btv628-B17","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1006\/jtbi.1998.0701","article-title":"Dynamics of the genetic regulatory network for arabidopsis thaliana flower morphogenesis","volume":"193","author":"Mendoza","year":"1998","journal-title":"J. Theor. Biol."},{"key":"2023020110442113800_btv628-B18","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.ejcon.2014.01.001","article-title":"Function perturbations in Boolean networks with its application in a d. melanogaster gene network","volume":"20","author":"Meng","year":"2014","journal-title":"Eur. J. Control"},{"key":"2023020110442113800_btv628-B19","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0012-365X(00)00115-1","article-title":"Discrete, sequential dynamical systems","volume":"226","author":"Mortveit","year":"2001","journal-title":"Discrete Math."},{"key":"2023020110442113800_btv628-B20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61607-5","volume-title":"Discrete Iterations: A Metric Study","author":"Robert","year":"1986"},{"key":"2023020110442113800_btv628-B21","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/s00521-011-0750-z","article-title":"Learning gene regulatory networks using the bees algorithm","volume":"22","author":"Ruz","year":"2013","journal-title":"Neural Comput. Appl."},{"key":"2023020110442113800_btv628-B22","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.biosystems.2013.10.007","article-title":"Dynamical and topological robustness of the mammalian cell cycle network: A reverse engineering approach","volume":"115","author":"Ruz","year":"2014","journal-title":"Biosystems"},{"key":"2023020110442113800_btv628-B23","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1186\/0717-6287-47-64","article-title":"Neutral space analysis for a boolean network model of the fission yeast cell cycle network","volume":"47","author":"Ruz","year":"2014","journal-title":"Biol. Res."},{"key":"2023020110442113800_btv628-B24","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1016\/j.jtbi.2010.03.006","article-title":"The arabidopsis thaliana flower organ specification gene regulatory network determines a robust differentiation process","volume":"264","author":"S\u00e1nchez-Corrales","year":"2010","journal-title":"J. Theor. Biol."},{"key":"2023020110442113800_btv628-B25","doi-asserted-by":"crossref","first-page":"i495","DOI":"10.1093\/bioinformatics\/bts410","article-title":"Boolean approach to signalling pathway modelling in hgf-induced keratinocyte migration","volume":"28","author":"Singh","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020110442113800_btv628-B26","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"2023020110442113800_btv628-B27","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1016\/0022-5193(73)90247-6","article-title":"Boolean formalization of genetic control circuits","volume":"42","author":"Thomas","year":"1973","journal-title":"J. Theor. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/5\/722\/49017463\/bioinformatics_32_5_722.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/5\/722\/49017463\/bioinformatics_32_5_722.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T22:00:32Z","timestamp":1675288832000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/5\/722\/1743454"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,31]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2016,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv628","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,3,1]]},"published":{"date-parts":[[2015,10,31]]}}}