Attractor detection and enumeration algorithms for Boolean networks

[1] Kauffman SA. Metabolic stability and epigenesis in randomly constructed

genetic nets. J Theor Biol 1969;22(3):437–67. https://doi.org/10.1016/00225193(69)90015-0.

[2] Kauffman SA. Homeostasis and differentiation in random genetic control

networks. Nature 1969;224(5215):177–8.

[3] Kauffman SA. The origin of order: self-organization and selection in

evolution. New York: Oxford University Press; 1993.

[4] Kauffman SA. Metabolic stability and epigenesis in randomly constructed

genetic nets. J Theoret Biol 2010;22:437–67. https://doi.org/10.1016/00225193(69)90015-0.

[5] Cheng D, Qi H, Li Z. Analysis and control of Boolean networks: a semi-tensor

product approach. London, UK: Springer-Verlag; 2011.

2519

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

T. Mori and T. Akutsu

Computational and Structural Biotechnology Journal 20 (2022) 2512–2520

[65] Devloo V, Hansen P, Labbé M. Identification of all steady states in large

networks by logical analysis. Bull Math Biol 2003;65(6):1025–51. https://doi.

org/10.1016/S0092-8240(03)00061-2.

[66] Inoue K. Logic programming for Boolean networks. In: Proceedings of the 22nd

International Joint Conference on Artificial Intelligence. p. 924–30. https://doi.

org/10.5591/978-1-57735-516-8/IJCAI11-160.

[67] Abdallah EB, Folschette M, Roux O, Magnin M. Asp-based method for the

enumeration of attractors in non-deterministic synchronous and

asynchronous multi-valued networks. Algorithms Mol Biol 2017;12(20).

https://doi.org/10.1186/s13015-017-0111-2.

[68] Dubrova E, Teslenko M, Martinelli A. Kaufmann networks: analysis and

applications. In: Proceedings of IEEE/ACM International Conference on

Computer-Aided

Design.

p.

479–84.

https://doi.org/10.1109/

ICCAD.2005.1560115.

[69] Garg A, Cara AD, Xenarios I, Mendoza L, Micheli GD. Synchronous versus

asynchronous modeling of gene regulatory networks. Bioinformatics 2008;24

(17):1917–25. https://doi.org/10.1093/bioinformatics/btn336.

[70] Zheng D, Yang G, Li X, Wang Z, Liu F, He L. An efficient algorithm for computing

attractors of synchronous and asynchronous Boolean networks. PLoS ONE

2013;8(4):e60593.

[71] Akutsu T, Zhao Y, Hayashida M, Tamura T. Integer programming-based

approach to attractor detection and control of Boolean networks. IEICE Trans

Inf Syst 2012;E95-D(12):2960–70. https://doi.org/10.1587/transinf.E95.

D.2960.

[72] Klarner H, Bockmayr A, Siebert H. Computing symbolic steady states of

Boolean networks. In: Cellular Automata. ACRI 2014. Lecture Notes in

Computer Science; vol. 8751. Springer, Cham; 2014, p. 561–570. DOI:

10.1007/978-3-319-11520-7_59..

[73] Kobayashi K, Hiraishi K. ILP/SMT-based method for design of Boolean

networks based on singleton attractors. IEEE/ACM Trans Comput Biol

Bioinform 2010;11(4):1253–9. https://doi.org/10.1109/TCBB.2014.2325011.

[74] Veliz-Cuba A. Reduction of Boolean network models. J Theor Biol

2011;289:167–72. https://doi.org/10.1016/j.jtbi.2011.08.042.

[75] Veliz-Cuba A, Aguilar B, Hinkelmann F, Laubenbacher R. Steady state analysis

of Boolean molecular network models via model reduction and computational

algebra. BMC Bioinformatics 2014;15(221).

[76] He Q, Xia Z, Lin B. An efficient approach of attractor calculation for large-scale

Boolean gene regulatory networks. J Theor Biol 2016;408:137–44. https://doi.

org/10.1016/j.jtbi.2016.08.006.

[77] Saadatpour A, Albert R, Reluga TC. A reduction method for Boolean network

models proven to conserve attractors. SIAM J Appl Dyn Syst 2013;12

(4):1997–2011. https://doi.org/10.1137/13090537X.

[78] Beneš N, Brim L, Pastva S, Šafránek D. Computing bottom SCCs symbolically

using transtion guided reduction. In: International Conference on Computer

Aided Verification. Cham: Springer; 2021. p. 505–28. https://doi.org/10.1007/

978-3-030-81685-8_24.

[79] Gao Z, Chen X, Basßar T. Stability structures of conjunctive Boolean networks.

Automatica 2018;89:8–20. https://doi.org/10.1016/j.automatica.2017.11.017.

[80] Chen X, Gao Z, Basßar T. Asymptotic behavior of conjunctive Boolean networks

over weakly connected digraphs. IEEE Trans Automat Contr 2019;65

(6):2536–49. https://doi.org/10.1109/TAC.2019.2930675.

[81] Irons DJ. Improving the efficiency of attractor cycle identification in Boolean

networks.

Physica

2006;217(1):7–21.

https://doi.org/10.1016/

j.physd.2006.03.006.

[82] Su C, Pang J, Paul S. Towards optimal decomposition of Boolean networks.

IEEE/ACM Trans Comput Biol Bioinform 2021;18(6):2167–76. https://doi.org/

10.1109/TCBB.2019.2914051.

[83] Zañudo JGT, Albert R. An effective network reduction approach to find the

dynamical repertoire of discrete dynamic networks. Chaos 2013;23(025111).

https://doi.org/10.1063/1.4809777.

[84] Klarner H, Siebert H. Approximating attractors of Boolean networks by

iterative CTL model checking. Front Bioeng Biotechnol 2015;3(130). https://

doi.org/10.3389/fbioe.2015.00130.

[85] Choo SM, Cho KH. An efficient algorithm for identifying primary phenotype

attractors of a large-scale Boolean network. BMC Syst Biol 2016;10(95).

https://doi.org/10.1186/s12918-016-0338-4.

[86] Tamaki H. A directed path-decomposition approach to exactly identifying

attractors of Boolean networks. In: Proceedings of 10th International

Symposium on Communication and Information Technologies. p. 844–9.

https://doi.org/10.1109/ISCIT.2010.5665106.

[87] Skodawessely T, Klemm K. Finding attractors in asynchronous Boolean

dynamics. Adv Complex Syst 2011;14:439–49. https://doi.org/10.1142/

S0219525911003098.

[88] Lu J, Li H, Liu Y, Li F. Survey on semi-tensor product method with its

applications in logical networks and other finite-valued systems. IET Control

Theory Appl 2017;11(13):2040–7. https://doi.org/10.1049/iet-cta.2016.1659.

[89] Zhao Y, Ghosh BK, Cheng D. Control of large-scale Boolean networks via

network aggregation. IEEE Trans Neural Netw Learn Syst 2016;27(7):1527–36.

https://doi.org/10.1109/TNNLS.2015.2442593.

[90] Liu X, Wang Y, Shi N, Ji Z, He S. GAPORE: Boolean network inference using a

genetic algorithm with novel polynomial representation and encoding

scheme.

Knowl-Based

Syst

2021;228:.

https://doi.org/10.1016/

j.knosys.2021.107277107277.

[35] Aldana M, Coppersmith S, Kadanoff LP. Boolean dynamics with random

couplings. In: Kaplan E, Marsden J, Sreenivasan K, editors. Perspectives and

Problems in Nolinear Science. New York NY: Springer; 2003. p. 23–89. https://

doi.org/10.1007/978-0-387-21789-5_2.

[36] Harvey I, Bossomaier T. Time out of joint: attractors in asynchronous random

Boolean networks. In: Proceedings of 4th European Conference on Artificial

Life. p. 67–75.

[37] Mochizuki A. An analytical study of the number of steady states in gene

regulatory networks. J Theor Biol 2005;236(3):291–310. https://doi.org/

10.1016/j.jtbi.2005.03.015.

[38] Drossel B, Mihaljev T, Greil F. Number and length of attractors in a critical

Kauffman model with connectivity one. Phys Rev Lett 2005;94(8):. https://doi.

org/10.1103/PhysRevLett.94.088701088701.

[39] Samuelsson B, Troein C. Superpolynomial growth in the number of attractors

in Kauffman networks. Phys Rev Lett 2003;90(9):. https://doi.org/10.1103/

PhysRevLett.90.098701098701.

[40] Thomas R. Regulatory networks seen as asynchronous automata: a logical

description. J Theoretical Biol 1991;153(1):1–23. https://doi.org/10.1016/

S0022-5193(05)80350-9.

[41] Mizera A, Pang J, Qu H, Yuan Q. Taming asynchrony for attractor detection in

large Boolean networks. IEEE/ACM Trans Comput Biol Bioinform 2019;16

(1):31–42. https://doi.org/10.1109/TCBB.2018.2850901.

[42] Giang TV, Akutsu T, Hiraishi K. An FVS-based approach to attractor detection in

asynchronous random Boolean networks. IEEE/ACM Trans Comput Biol

Bioinform 2022;19(2):806–18. https://doi.org/10.1109/TCBB.2020.3028862.

[43] Chatain T, Haar S, Paulevé L. Most permissive semantics of boolean networks.

arXiv 2018;10.48550/arXiv. 1808.10240..

[44] de Jong H, Page M. Search for steady states of piecewise-linear differential

equation models of genetic regulatory networks. IEEE/ACM Trans Comput Biol

Bioinform 2008;5(2):208–22. https://doi.org/10.1109/TCBB.2007.70254.

[45] Dubrova E, Teslenko M. A SAT-based algorithm for finding attractors in

synchronous Boolean networks. IEEE/ACM Trans Comput Biol Bioinform

2011;8(5):1393–9. https://doi.org/10.1109/TCBB.2010.20.

[46] Leone M, Pagnani A, Parisi G, Zagordi O. Finite size corrections to random

Boolean networks. J Stat Mech 2006. https://doi.org/10.1088/1742-5468/

2006/12/P12012.

[47] Balyo T, Heule M, Jarvisalo M. SAT competition 2016: recent developments. In:

Proceedings of the 31st AAAI Conference on Artificial Intelligence. p. 5061–3.

[48] Makino K, Tamaki S, Yamamoto M. Derandomizing the HSSW algorithm for 3SAT. Algorithmica 2013;67(2):112–24. https://doi.org/10.1007/978-3-64222685-4_1.

[49] Levy H, Low DW. A contraction algorithm for finding small cycle cutlets. J

Algorithms 1988;9(4):470–93.

[50] Chen J, Fomin FV, Liu Y, Lu S, Villanger Y. Improved algorithms for feedback

vertex set problems. J Comput Syst Sci 2008;74(7):1188–98. https://doi.org/

10.1016/j.jcss.2008.05.002.

[51] Li J, Nederlof J. Detecting feedback vertex sets of size k in o⁄(2.7k) time. In:

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms

(SODA). p. 971–89. https://doi.org/10.1137/1.9781611975994.58.

[52] Mochizuki A, Fiedler B, Kurosawa G, Saito D. Dynamics and control at feedback

vertex sets. II: a faithful monitor to determine the diversity of molecular

activities in regulatory networks. J Theor Biol 2013;335:130–46. https://doi.

org/10.1016/j.jtbi.2013.06.009.

[53] Mori F, Mochizuki A. Expected number of fixed points in Boolean networks

with arbitrary topology. Phys Rev Lett 2017;119(2). https://doi.org/10.1103/

PhysRevLett.119.028301.

[54] Zhang SQ, Hayashida M, Akutsu T, Ching WK, Ng MK. Algorithms for finding

small attractors in Boolean networks. EURASIP J Bioinform Syst Biol 2007;2007

(1). https://doi.org/10.1155/2007/20180.

[55] Tamura T, Akutsu T. Detection a singleton attractor in a Boolean network

utilizing SAT algorithms. IEICE Trans Fundamentals 2009;E92-A(2):493–501.

https://doi.org/10.1587/transfun.E92.A.493.

[56] Yamamoto M. An improved O(1.234

)-time deterministic algorithm for SAT.

In: Proceedings of 16th International Symposium on Algorithms and

Computation (Lecture Notes in Computer Science 3827). p. 644–53. https://

doi.org/10.1007/11602613_65.

[57] Melkman AA, Tamura T, Akutsu T. Determining a singleton attractor of an

AND/OR Boolean network in O(1.587n) time. Inf Process Lett 2010;110(14–

15):565–9. https://doi.org/10.1016/j.ipl.2010.05.001.

[58] Chu H, Xiao M, Zhang Z. An improved upper bound for SAT. Theoret Comput

Sci 2021;887:51–62. https://doi.org/10.1016/j.tcs.2021.06.045.

[59] Flum J, Grohe M. Parameterized complexity theory. Berlin: Springer; 2006.

[60] Fomin FV, Kratsch D. Exact exponential algorithms. Berlin: Springer; 2010.

[61] Akutsu T, Kosub S, Melkman AA, Tamura T. Finding a periodic attractor of a

Boolean networks. IEEE/ACM Trans Comput Biol Bioinform 2012;9

(5):1410–21. https://doi.org/10.1109/TCBB.2012.87.

[62] Chang CJ, Tamura T, Chao KM, Akutsu T. A fixed-parameter algorithm for

detecting a singleton attractor in an AND/OR Boolean network with bounded

treewidth. IEICE Trans Fundamentals 2015;98-A(1):384–90. https://doi.org/

10.1587/transfun.E98.A.384.

[63] Freuder EC. Complexity of k-tree structured constraint satisfaction problems.

In: Proceedings of the 8th AAAI Conference on Artificial Intelligence. p. 4–9.

[64] Just W. The steady state system problem is NP-hard even for monotone

quadratic Boolean dynamical systems; 2006. Preprint available at http://

www.ohio.edu/people/just/publ.html..

2520

...