{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:13:29Z","timestamp":1761808409040},"reference-count":47,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2020,12,3]],"date-time":"2020-12-03T00:00:00Z","timestamp":1606953600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"ANID-Chile","award":["AFB170001"],"award-info":[{"award-number":["AFB170001"]}]},{"name":"CONICYT-PCHA","award":["2016-21160885"],"award-info":[{"award-number":["2016-21160885"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,5,23]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>In the modeling of biological systems by Boolean networks, a key problem is finding the set of fixed points of a given network. Some constructed algorithms consider certain structural properties of the regulatory graph like those proposed by Akutsu et al. and Zhang et al., which consider a feedback vertex set of the graph. However, these methods do not take into account the type of action (activation and inhibition) between its components.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>In this article, we propose a new algorithm for finding the set of fixed points of a Boolean network, based on a positive feedback vertex set P of its regulatory graph and which works, by applying a sequential update schedule, in time O(2|P|\u00b7n2+k), where n is the number of components and the regulatory functions of the network can be evaluated in time O(nk),\u2009k\u22650. The theoretical foundation of this algorithm is due a nice characterization, that we give, of the dynamical behavior of the Boolean networks without positive cycles and with a fixed point.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>An executable file of FixedPoint algorithm made in Java and some examples of input files are available at: www.inf.udec.cl\/\u02dclilian\/FPCollector\/.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary material is available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa922","type":"journal-article","created":{"date-parts":[[2020,10,17]],"date-time":"2020-10-17T03:21:12Z","timestamp":1602904872000},"page":"1148-1155","source":"Crossref","is-referenced-by-count":7,"title":["Finding the fixed points of a Boolean network from a positive feedback vertex set"],"prefix":"10.1093","volume":"37","author":[{"given":"Julio","family":"Aracena","sequence":"first","affiliation":[{"name":"CI2MA and Departamento de Ingenier\u00eda Matem\u00e1tica, Facultad de Ciencias F\u00edsicas y Matem\u00e1ticas, Universidad de Concepci\u00f3n , Concepci\u00f3n, Chile"}]},{"given":"Luis","family":"Cabrera-Crot","sequence":"additional","affiliation":[{"name":"Departamento de Ing. Inform\u00e1tica y Cs. de la Computaci\u00f3n and CI2MA , Facultad de Ingenier\u00eda, Universidad de Concepci\u00f3n, Concepci\u00f3n, Chile"}]},{"given":"Lilian","family":"Salinas","sequence":"additional","affiliation":[{"name":"Departamento de Ing. Inform\u00e1tica y Cs. de la Computaci\u00f3n and CI2MA , Facultad de Ingenier\u00eda, Universidad de Concepci\u00f3n, Concepci\u00f3n, Chile"}]}],"member":"286","published-online":{"date-parts":[[2020,12,3]]},"reference":[{"key":"2023051612061426800_btaa922-B1","first-page":"695","volume":"98","author":"Akutsu","year":"1998","journal-title":"SODA 98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms"},{"key":"2023051612061426800_btaa922-B2","first-page":"151","article-title":"A system for identifying genetic networks from gene expression patterns produced by gene disruptions and overexpressions","volume":"9","author":"Akutsu","year":"1998","journal-title":"Genome Inform"},{"key":"2023051612061426800_btaa922-B3","first-page":"5610","author":"Akutsu","year":"2009","journal-title":"Proceedings of the 48th IEEE Conference on Decision and Control (CDC) held jointly with the 2009 28th Chinese Control Conference"},{"key":"2023051612061426800_btaa922-B4","doi-asserted-by":"crossref","first-page":"1275","DOI":"10.1089\/cmb.2010.0281","article-title":"Determining a singleton attractor of a Boolean network with nested canalyzing functions","volume":"18","author":"Akutsu","year":"2011","journal-title":"J. Comput. Biol"},{"key":"2023051612061426800_btaa922-B5","doi-asserted-by":"crossref","first-page":"1398","DOI":"10.1007\/s11538-008-9304-7","article-title":"Maximum number of fixed points in regulatory Boolean networks","volume":"70","author":"Aracena","year":"2008","journal-title":"Bull. Math. Biol"},{"key":"2023051612061426800_btaa922-B6","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.jtbi.2005.07.011","article-title":"Regulatory network for cell shape changes during drosophila ventral furrow formation","volume":"239","author":"Aracena","year":"2006","journal-title":"J. Theor. Biol"},{"key":"2023051612061426800_btaa922-B7","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.jcss.2017.03.016","article-title":"Fixed points in conjunctive networks and maximal independent sets in graph contractions","volume":"88","author":"Aracena","year":"2017","journal-title":"J. Comput. Syst. Sci"},{"key":"2023051612061426800_btaa922-B8","doi-asserted-by":"crossref","first-page":"1702","DOI":"10.1137\/16M1060868","article-title":"Number of fixed points and disjoint cycles in monotone Boolean networks","volume":"31","author":"Aracena","year":"2017","journal-title":"SIAM J. Discrete Math"},{"key":"2023051612061426800_btaa922-B9","doi-asserted-by":"publisher","first-page":"104540","DOI":"10.1016\/j.ic.2020.104540","article-title":"Fixing monotone Boolean networks asynchronously","volume":"274","author":"Aracena","year":"2020","journal-title":"Information and Computation"},{"volume-title":"Digraphs: Theory, Algorithms and Applications","year":"2008","author":"Bang-Jensen","key":"2023051612061426800_btaa922-B10"},{"key":"2023051612061426800_btaa922-B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1411509.1411511","article-title":"A fixed-parameter algorithm for the directed feedback vertex set problem","volume":"55","author":"Chen","year":"2008","journal-title":"J. ACM"},{"key":"2023051612061426800_btaa922-B12","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1016\/S0092-8240(03)00061-2","article-title":"Identification of all steady states in large networks by logical analysis","volume":"65","author":"Devloo","year":"2003","journal-title":"Bull. Math. Biol"},{"key":"2023051612061426800_btaa922-B13","doi-asserted-by":"crossref","first-page":"1393","DOI":"10.1109\/TCBB.2010.20","article-title":"A sat-based algorithm for finding attractors in synchronous Boolean networks","volume":"8","author":"Dubrova","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023051612061426800_btaa922-B14","doi-asserted-by":"crossref","first-page":"e0166906","DOI":"10.1371\/journal.pone.0166906","article-title":"An algorithm for finding the singleton attractors and pre-images in strong-inhibition Boolean networks","volume":"11","author":"He","year":"2016","journal-title":"PLoS One"},{"key":"2023051612061426800_btaa922-B15","doi-asserted-by":"crossref","first-page":"1913","DOI":"10.1073\/pnas.0705088105","article-title":"Emergent decision-making in biological signal transduction networks","volume":"105","author":"Helikar","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023051612061426800_btaa922-B16","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1186\/1471-2105-12-295","article-title":"ADAM: analysis of discrete models of biological systems using computer algebra","volume":"12","author":"Hinkelmann","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023051612061426800_btaa922-B17","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/s001099900023","article-title":"Gene expression profiling, genetic networks, and cellular states: an integrating concept for tumorigenesis and drug discovery","volume":"77","author":"Huang","year":"1999","journal-title":"J. Mol. Med"},{"key":"2023051612061426800_btaa922-B18","first-page":"85","volume-title":"Reducibility among Combinatorial Problems","author":"Karp","year":"1972"},{"key":"2023051612061426800_btaa922-B19","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":"2023051612061426800_btaa922-B20","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195079517.001.0001","volume-title":"Origins of Order Self-Organization and Selection in Evolution","author":"Kauffman","year":"1993"},{"key":"2023051612061426800_btaa922-B21","doi-asserted-by":"crossref","first-page":"446","DOI":"10.3389\/fphys.2012.00446","article-title":"Boolean model of yeast apoptosis as a tool to study yeast and human apoptotic regulations","volume":"3","author":"Kazemzadeh","year":"2012","journal-title":"Front. Physiol"},{"key":"2023051612061426800_btaa922-B22","doi-asserted-by":"crossref","first-page":"988","DOI":"10.1007\/s11538-012-9777-2","article-title":"Dynamics of influenza virus and human host interactions during infection and replication cycle","volume":"75","author":"Madrahimov","year":"2013","journal-title":"Bull. Math. Biol"},{"key":"2023051612061426800_btaa922-B23","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1016\/j.ipl.2010.05.001","article-title":"Determining a singleton attractor of an AND\/OR Boolean network in O (1.587 n) time","volume":"110","author":"Melkman","year":"2010","journal-title":"Inf. Process. Lett"},{"key":"2023051612061426800_btaa922-B24","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/j.endm.2008.01.043","article-title":"On the complexity of feedback set problems in signed digraphs","volume":"30","author":"Montalva","year":"2008","journal-title":"Electron. Notes Discret. Math"},{"key":"2023051612061426800_btaa922-B25","doi-asserted-by":"crossref","first-page":"680","DOI":"10.3389\/fphys.2018.00680","article-title":"The colomoto interactive notebook: accessible and reproducible computational analyses for qualitative biological networks","volume":"9","author":"Naldi","year":"2018","journal-title":"Front. Physiol"},{"key":"2023051612061426800_btaa922-B26","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1186\/1752-0509-2-36","article-title":"A logic-based diagram of signalling pathways central to macrophage activation","volume":"2","author":"Raza","year":"2008","journal-title":"BMC Syst. Biol"},{"key":"2023051612061426800_btaa922-B27","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.aam.2007.11.003","article-title":"Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework","volume":"41","author":"Remy","year":"2008","journal-title":"Adv. Appl. Math"},{"key":"2023051612061426800_btaa922-B28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2017.12.037","article-title":"Fixed points and connections between positive and negative cycles in Boolean networks","volume":"243","author":"Richard","year":"2018","journal-title":"Discret. Appl. Math"},{"key":"2023051612061426800_btaa922-B29","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.jtbi.2018.11.028","article-title":"Positive and negative cycles in Boolean networks","volume":"463","author":"Richard","year":"2019","journal-title":"J. Theor. Biol"},{"key":"2023051612061426800_btaa922-B30","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61607-5","volume-title":"Discrete Iterations: A Metric Study","author":"Robert","year":"1986"},{"volume-title":"Les Systemes Dynamiques Discrets","year":"1995","author":"Robert","key":"2023051612061426800_btaa922-B31"},{"key":"2023051612061426800_btaa922-B32","doi-asserted-by":"crossref","first-page":"929","DOI":"10.2307\/121059","article-title":"Permanents, Pfaffian orientations, and even directed circuits","volume":"150","author":"Robertson","year":"1999","journal-title":"Ann. Math"},{"key":"2023051612061426800_btaa922-B33","first-page":"111","article-title":"Improved bound for the PPSZ\/Sch\u00f6ning-algorithm for 3-SAT","volume":"1","author":"Rolf","year":"2006","journal-title":"JSAT"},{"key":"2023051612061426800_btaa922-B34","doi-asserted-by":"crossref","first-page":"e1002267","DOI":"10.1371\/journal.pcbi.1002267","article-title":"Dynamical and structural analysis of a t cell survival network identifies novel candidate therapeutic targets for large granular lymphocyte leukemia","volume":"7","author":"Saadatpour","year":"2011","journal-title":"PLoS Comput. Biol"},{"key":"2023051612061426800_btaa922-B35","doi-asserted-by":"crossref","first-page":"e163","DOI":"10.1371\/journal.pcbi.0030163","article-title":"A logical model provides insights into T cell receptor signaling","volume":"3","author":"Saez-Rodriguez","year":"2007","journal-title":"PLoS Comput. Biol"},{"key":"2023051612061426800_btaa922-B36","doi-asserted-by":"crossref","first-page":"e1000438","DOI":"10.1371\/journal.pcbi.1000438","article-title":"The logic of EGFR\/ ErbB signaling: theoretical properties and analysis of high-throughput data","volume":"5","author":"Samaga","year":"2009","journal-title":"PLoS Comput. Biol"},{"key":"2023051612061426800_btaa922-B37","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":"2023051612061426800_btaa922-B38","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/s11786-008-0063-5","article-title":"Algorithms for singleton attractor detection in planar and nonplanar and\/or Boolean networks","volume":"2","author":"Tamura","year":"2009","journal-title":"Math. Comput. Sci"},{"key":"2023051612061426800_btaa922-B39","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1587\/transfun.E92.A.493","article-title":"Detecting a singleton attractor in a Boolean network utilizing sat algorithms","volume":"E92-A","author":"Tamura","year":"2009","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci"},{"key":"2023051612061426800_btaa922-B40","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"},{"volume-title":"Biological Feedback","year":"1990","author":"Thomas","key":"2023051612061426800_btaa922-B41"},{"key":"2023051612061426800_btaa922-B42","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/j.jtbi.2011.08.042","article-title":"Reduction of Boolean network models","volume":"289","author":"Veliz-Cuba","year":"2011","journal-title":"J. Theor. Biol"},{"key":"2023051612061426800_btaa922-B43","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1186\/1471-2105-15-221","article-title":"Steady state analysis of Boolean molecular network models via model reduction and computational algebra","volume":"15","author":"Veliz-Cuba","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023051612061426800_btaa922-B44","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.entcs.2015.06.012","article-title":"Dimension reduction of large sparse AND-NOT network models","volume":"316","author":"Veliz-Cuba","year":"2015","journal-title":"Electron. Notes Theor. Comput. Sci"},{"key":"2023051612061426800_btaa922-B45","doi-asserted-by":"crossref","first-page":"025111","DOI":"10.1063\/1.4809777","article-title":"An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks","volume":"23","author":"Za\u00f1udo","year":"2013","journal-title":"Chaos"},{"key":"2023051612061426800_btaa922-B46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2007\/20180","article-title":"Algorithms for finding small attractors in Boolean networks","volume":"2007","author":"Zhang","year":"2007","journal-title":"EURASIP J. Bioinform. Syst. Biol"},{"key":"2023051612061426800_btaa922-B47","first-page":"670","author":"Zou","year":"2013","journal-title":"2013 ICME International Conference on Complex Medical Engineering, Beijing, China"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa922\/34686288\/btaa922.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/8\/1148\/50340654\/btaa922.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/8\/1148\/50340654\/btaa922.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T01:07:44Z","timestamp":1723770464000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/8\/1148\/5949737"}},"subtitle":[],"editor":[{"given":"Cowen","family":"Lenore","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,12,3]]},"references-count":47,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,5,23]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa922","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2021,4,15]]},"published":{"date-parts":[[2020,12,3]]}}}