SCIENCE CHINA Information Sciences, Volume 59, Issue 8: 080101(2016) https://doi.org/10.1007/s11432-016-5594-9

Improving BDD-based attractor detection for synchronous Boolean networks

More info
  • ReceivedApr 25, 2016
  • AcceptedMay 18, 2016
  • PublishedJul 18, 2016


Boolean networks are an important formalism for modelling biological systems and have attracted much attention in recent years. An~important challenge in Boolean networks is to exhaustively find attractors, which represent steady states of a~biological network. In this paper, we propose a~new approach to improve the efficiency of BDD-based attractor detection. Our approach includes a~monolithic algorithm for small networks, an~enumerative strategy to deal with large networks, a~method to accelerate attractor detection based on an~analysis of the network structure, and two heuristics on ordering BDD variables. We demonstrate the performance of our approach on a~number of examples and on a~realistic model of apoptosis in hepatocytes. We compare it with one existing technique in the literature.

Funded by

EPSRC project EP/J011894/2 and Royal Society Project IE141180. Qixia YUAN was supported by National Research Fund Luxembourg(7814267)



Honyang QU was supported by EPSRC project EP/J011894/2 and Royal Society Project IE141180. Qixia YUAN was supported by National Research Fund, Luxembourg (Grant No. 7814267).


[1] Kauffman S. Homeostasis and differentiation in random genetic control networks. Nature, 1969, 224: 177-178 CrossRef Google Scholar

[2] Huang S. Genomics, complexity and drug discovery: insights from Boolean network models of cellular regulation. Pharmacogenomics, 2001, 2: 203-222 CrossRef Google Scholar

[3] Needham C J, Manfield I W, Bulpitt A J, et al. From gene expression to gene regulatory networks in Arabidopsis thaliana. BMC Syst Biol, 2009, 3: 85-222 CrossRef Google Scholar

[4] Garg A, Xenarios L, Mendoza L, et al. An efficient method for dynamic analysis of gene regulatory networks and in silico gene perturbation experiments. In: Proceedings of 11th Annual Conference on Research in Computational Molecular Biology. Berlin: Springer, 2007. 62--76. Google Scholar

[5] Somogyi R, Greller L D. The dynamics of molecular networks: applications to therapeutic discovery. Drug Discov Today, 2001, 6: 1267-1277 CrossRef Google Scholar

[6] Raeymaekers L. Dynamics of Boolean networks controlled by biologically meaningful functions. J Theor Biol, 2002, 218: 331-341 CrossRef Google Scholar

[7] Irons D J. Improving the efficiency of attractor cycle identification in Boolean networks. Phys D, 2006, 217: 7-21 CrossRef Google Scholar

[8] Dubrova E, Teslenko M, Martinelli A. Kauffman networks: analysis and applications. In: Proceedings of 2005 IEEE/ACM International Conference on Computer-Aided Design. Washington DC: IEEE, 2005. 479--484. Google Scholar

[9] Garg A, Di Cara A, Xenarios L, et al. Synchronous versus asynchronous modeling of gene regulatory networks. Bioinformatics, 2008, 24: 1917-1925 CrossRef Google Scholar

[10] Zheng D S, Yang G W, Li X Y, et al. An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks. PLoS ONE, 2013, 8: e60593-1925 CrossRef Google Scholar

[11] Dubrova E, Teslenko M. A SAT-based algorithm for finding attractors in synchronous Boolean networks. IEEE/ACM Trans Comput Biol Bioinf, 2011, 8: 1393-1399 CrossRef Google Scholar

[12] Zhao Y, Kim J, Filippone M. Aggregation algorithm towards large-scale Boolean network analysis. IEEE Trans Automat Contr, 2013, 58: 1976-1985 CrossRef Google Scholar

[13] Guo W S, Yang G W, Wu W, et al. A parallel attractor finding algorithm based on Boolean satisfiability for genetic regulatory networks. PLoS ONE, 2014, 9: e94258-1985 CrossRef Google Scholar

[14] Kauffman S. Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol, 1969, 22: 437-467 CrossRef Google Scholar

[15] Mushthofa M, Torres G, Van de Peer Y, et al. ASP-G: an ASP-based method for finding attractors in genetic regulatory networks. Bioinformatics, 2014, 30: 3086-3092 CrossRef Google Scholar

[16] Shmulevich I, Edward R D. Probabilistic Boolean Networks: the Modeling and Control of Gene Regulatory Networks. Philadelphia: SIAM Press, 2010. Google Scholar

[17] Lee C. Representation of switching circuits by binary-decision programs. Bell Syst Tech J, 1959, 38: 985-999 CrossRef Google Scholar

[18] Akers S B. Binary decision diagrams. IEEE Trans Comput, 1978, 100: 509-516 Google Scholar

[19] Bollig B, Wegener L. Improving the variable ordering of OBDDs is NP-complete. IEEE Trans Comput, 1996, 45: 993-1002 CrossRef Google Scholar

[20] Bryant R E. Symbolic Boolean manipulation with ordered binary-decision diagrams. ACM Comput Surv, 1992, 24: 293-318 CrossRef Google Scholar

[21] Drechsler R. Verification of multi-valued logic networks. In: Proceedings of 26th Symposium on Multiple-Valued Logic. Washington DC: IEEE, 1996. 10--15. Google Scholar

[22] Malik S, Wang A R, Brayton R K, et al. Logic verification using binary decision diagrams in a logic synthesis environment. In: Proceedings of IEEE International Conference on Computer-Aided Design. Washington DC: IEEE, 1988. 6--9. Google Scholar

[23] Lomuscio A, Qu H Y, Raimondi F. MCMAS: an open-source model checker for the verification of multi-agent systems. Int J Softw Tools Technol Transf, 2015, doi: 10-x Google Scholar

[24] Mizera A, Pang J, Yuan Q X. ASSA-PBN: an approximate steady-state analyser of probabilistic Boolean networks. In: Proceedings of 13th International Symposium on Automated Technology for Verification and Analysis. Berlin: Springer, 2015. 214--220. Software available at \url {http://satoss.uni.lu/software/ASSA-PBN/}. Google Scholar

[25] Schlatter R, Schmich K, Vizcarra I A, et al. ON/OFF and beyond---a Boolean model of apoptosis. PLoS Comput Biol, 2009, 5: e1000595-x CrossRef Google Scholar

[26] Trairatphisan P, Mizera A, Pang J, et al. optPBN: an optimisation toolbox for probabilistic Boolean networks. PLoS ONE, 2014, 9: e98001-x CrossRef Google Scholar

[27] Mizera A, Pang J, Yuan Q X. Reviving the two-state Markov chain approach. Technical Report. 2015. Available online at \url{http://arxiv.org/abs/1501.01779}. Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有