Improving BDD-based attractor detection for synchronous Boolean networks

Qu, Hongyang; Yuan, Qixia; Pang, Jun; Mizera, Andrzej

Download

Paper published in a book (Scientific congresses, symposiums and conference proceedings)

Improving BDD-based attractor detection for synchronous Boolean networks

Qu, Hongyang; Yuan, Qixia; Pang, Jun et al.

2015 • In Proceedings of the 7th Asia-Pacific Symposium on Internetware

Peer reviewed

Permalink
https://hdl.handle.net/10993/25937

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

internetware.pdf

Author postprint (339.81 kB)

Download

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Boolean networks; systems biology; binary decision diagram

Abstract :

[en] Boolean networks are an important formalism for modelling biological systems and have attracted much attention in recent years. An important direction in Boolean networks is to exhaustively find attractors, which represent steady states when a biological network evolves for a long term. 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, and two heuristics on ordering BDD variables. We demonstrate the performance of our approach on a number of examples, and compare it with one existing technique in the literature.

Disciplines :

Computer science

Author, co-author :

Qu, Hongyang; University of Sheffield

Yuan, Qixia ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)

Pang, Jun ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)

Mizera, Andrzej ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)

External co-authors :

yes

Language :

English

Title :

Improving BDD-based attractor detection for synchronous Boolean networks

Publication date :

2015

Event name :

7th Asia-Pacific Symposium on Internetware

Event date :

06-11-2015

Audience :

International

Main work title :

Proceedings of the 7th Asia-Pacific Symposium on Internetware

Publisher :

ACM

Peer reviewed :

Peer reviewed

FnR Project :

FNR7814267 - New Approaches To Parameter Estimation Of Gene Regulatory Networks, 2014 (01/03/2014-14/01/2018) - Qixia Yuan

Available on ORBilu :

since 17 March 2016

Statistics

Number of views

75 (7 by Unilu)

Number of downloads

173 (1 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

Akers, S. B. Binary decision diagrams. IEEE Transactions on Computers 100, 6 (1978), 509-516.
Bollig, B., and Wegener, L. Improving the variable ordering of OBDDs is NP-complete. IEEE Transactions on Computers 45, 9 (1996), 993-1002.
Bryant, R. E. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys 24, 3 (1992), 293-318.
Drechsler, R. Verification of multi-valued logic networks. In Proc. 26th Symposium on Multiple-Valued Logic (1996), IEEE, pp. 10-15.
Dubrova, E., and Teslenko, M. A SAT-based algorithm for finding attractors in synchronous Boolean networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8, 5 (2011), 1393-1399.
Dubrova, E., Teslenko, M., and Martinelli, A. Kauffman networks: Analysis and applications. In Proc. 2005 IEEE/ACM International Conference on Computer-Aided Design (2005), IEEE CS, pp. 479-484.
Ferrazzi, F., Engel, F. B., Wu, E., Moseman, A. P., Kohane, I. S., Bellazzi, R., and Ramoni, M. F. Inferring cell cycle feedback regulation from gene expression data. Journal of Biomedical Informatics 44, 4 (2011), 565-575.
Fujita, M., Fujisawa, H., and Matsunaga, Y. Variable ordering algorithms for ordered binary decision diagrams and their evaluation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 12, 1 (1993), 6-12.
Garg, A., Di Cara, A., Xenarios, I., Mendoza, L., and De Micheli, G. Synchronous versus asynchronous modeling of gene regulatory networks. Bioinformatics 24, 17 (2008), 1917-1925.
Garg, A., Xenarios, L., Mendoza, L., and DeMicheli, G. An efficient method for dynamic analysis of gene regulatory networks and in silico gene perturbation experiments. In Proc. 11th Annual Conference on Research in Computational Molecular Biology (2007), vol. 4453 of LNCS, Springer, pp. 62-76.
Huang, S. Genomics, complexity and drug discovery: insights from Boolean network models of cellular regulation. Pharmacogenomics 2, 3 (2001), 203-222.
Irons, D. J. Improving the efficiency of attractor cycle identification in Boolean networks. Physica D: Nonlinear Phenomena 217, 1 (2006), 7-21.
Kauffman, S. Homeostasis and differentiation in random genetic control networks. Nature 224 (1969), 177-178.
Kauffman, S. A. Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of Theoretical Biology 22, 3 (1969), 437-467.
Lee, C.-Y. Representation of switching circuits by binary-decision programs. Bell System Technical Journal 38, 4 (1959), 985-999.
Lomuscio, A., Qu, H., and Raimondi, F. MCMAS: An open-source model checker for the verification of multi-agent systems. International Journal on Software Tools for Technology Transfer (2015).
Luc, R. Dynamics of Boolean networks controlled by biologically meaningful functions. Journal of Theoretical Biology 218, 3 (2002), 331-341.
Malik, S., Wang, A. R., Brayton, R. K., and Sangiovanni-Vincentelli, A. Logic verification using binary decision diagrams in a logic synthesis environment. In Proc. IEEE International Conference on Computer-Aided Design (1988), IEEE, pp. 6-9.
Mizera, A., Pang, J., and Yuan, Q. ASSA-PBN: a tool for approximate steady-state analysis of large probabilistic Boolean networks. In Proc. 13th International Symposium on Automated Technology for Verification and Analysis (2015), vol. 9364 of LNCS, Springer, pp. 214-220. Software available at http://satoss.uni.lu/software/ASSA-PBN/.
Mushthofa, M., Torres, G., de Peer, Y. V., Marchal, K., and Cock, M. D. ASP-G: an ASP-based method for finding attractors in genetic regulatory networks. Bioinformatics 30, 21 (2014), 3086-3092.
Needham, C. J., Manfield, I. W., Bulpitt, A. J., Gilmartin, P. M., and Westhead, D. R. From gene expression to gene regulatory networks in arabidopsis thaliana. BMC Systems Biology 3, 1 (2009), 85.
Ravi, K., McMillan, K. L., Shiple, T. R., and Somenzi, F. Approximation and decomposition of binary decision diagrams. In Proc. 35th Annual Design Automation Conference (1998), ACM, pp. 445-450.
Shmulevich, I., and Dougherty, E. R. Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks. SIAM Press, 2010.
Somogyi, R., and Greller, L. D. The dynamics of molecular networks: applications to therapeutic discovery. Drug Discovery Today 6, 24 (2001), 1267-1277.
Trairatphisan, P., Mizera, A., Pang, J., Tantar, A.-A., Schneider, J., and Sauter, T. Recent development and biomedical applications of probabilistic Boolean networks. Cell Communication and Signaling 11 (2013), 46.
Zheng, D., Yang, G., Li, X., Wang, Z., Liu, F., and He, L. An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks. PLoS ONE 8, 4 (2013), e60593.