Research PapersOpen Access

FINDING AND ANALYZING THE MINIMUM SET OF DRIVER NODES IN CONTROL OF BOOLEAN NETWORKS

WENPIN HOU

Department of Mathematics, The University of Hong Kong, Pokfulam Road, Hong Kong 999077, Hong Kong

E-mail Address: whou@hku.hk

Search for more papers by this author

TAKEYUKI TAMURA

Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan

E-mail Address: tamura@kuicr.kyoto-u.ac.jp

Search for more papers by this author

WAI-KI CHING

Department of Mathematics, The University of Hong Kong, Pokfulam Road, Hong Kong 999077, Hong Kong

E-mail Address: wching@hku.hk

Search for more papers by this author

, and

TATSUYA AKUTSU

http://orcid.org/0000-0001-9763-797X

Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan

E-mail Address: takutsu@kuicr.kyoto-u.ac.jp

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0219525916500065Cited by:8 (Source: Crossref)

Abstract

We study the minimum number of driver nodes control of which leads a Boolean network (BN) from an initial state to a target state in a specified number of time steps. We show that the problem is NP-hard and present an integer linear programming-based method that solves the problem exactly. We mathematically analyze the average size of the minimum set of driver nodes for random Boolean networks with bounded in-degree and with a small number of time steps. The results of computational experiments using randomly generated BNs show good agreements with theoretical analyses. A further examination in realistic BNs demonstrates the efficiency and generality of our theoretical analyses.

Keywords:

References

1. Abul, O., Alhajj, R. and Polat, F., Markov decision processes based optimal control policies for probabilistic boolean networks, in Proc. Forth IEEE Symp. Bioinformatics and Bioengineering (BIBE 2004) (2004), pp. 337–344. Google Scholar
2. Akutsu, T., Hayashida, M., Ching, W.-K. and Ng, M. K., Control of boolean networks: Hardness results and algorithms for tree structured networks, J. Theor. Biol. 244 (2007) 670–679. Crossref, Web of Science, Google Scholar
3. Akutsu, T., Hayashida, M., Zhang, S.-Q., Ching, W.-K. and Ng, M. K., Analyses and algorithms for predecessor and control problems for boolean networks of bounded indegree, IPSJ Trans. Bioinform. 1 (2008) 23–24. Crossref, Google Scholar
4. Akutsu, T., Kuhara, S., Maruyama, O. and Miyano, S., A system for identifying genetic networks from gene expression patterns produced by gene disruptions and overexpressions, Genome Inform. 9 (1998) 151–160. Google Scholar
5. Akutsu, T., Miyano, S. and Kuhara, S., Inferring qualitative relations in genetic networks and metabolic pathways, Bioinformatics 16 (2000) 727–734. Crossref, Web of Science, Google Scholar
6. Akutsu, T., Zhao, Y., Hayashida, M. and Tamura, T., Integer programming-based approach to attractor detection and control of boolean networks, IEICE Trans. Inform. Syst. E95-D (2012) 2960–2970. Crossref, Web of Science, Google Scholar
7. Albert, R. and Barabási, A. L., Dynamics of complex systems: Scaling laws for the period of boolean networks, Phys. Rev. Lett. 84 (2000) 5660–5663. Crossref, Web of Science, Google Scholar
8. Albert, R. and Othmer, H. G., The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in drosophila melanogaster, J. Theor. Biol. 223 (2003) 1–18. Crossref, Web of Science, Google Scholar
9. Albert, R. and Thakar, J., Boolean modeling: A logic-based dynamic approach for understanding signaling and regulatory networks and for making useful predictions, WIREs Syst. Biol. Med. 6 (2014) 353–369. Crossref, Web of Science, Google Scholar
10. Aldana, M., Boolean dynamcis of networks with scale-free topology, Physica D 185 (2003) 45–66. Crossref, Web of Science, Google Scholar
11. Amaral, L. A. N., Guilera, A. D., Moreira, A. A., Goldberger, A. L. and Lipsitz, L. A., Emergence of complex dynamics in a simple model of signaling networks, Proc. Natl. Acad. Sci. USA 101 (2004) 15551–15555. Crossref, Web of Science, Google Scholar
12. Azuma, S. and Imura, J., Synthesis of optimal controllers for piecewise affine systems with sampled-data switching, Automatica 42 (2006) 697–710. Crossref, Web of Science, Google Scholar
13. Barabási, A. L. and Oltval, Z. N., Network biology: Understanding the cell’s functional organization, Nat. Rev. Genet. 5 (2004) 101–113. Crossref, Web of Science, Google Scholar
14. Bharti, A. C. and Aggarwal, B. B., Nuclear factor-kappa b and cancer: Its role in prevention and therapy, Biochem. Pharmacol. 64 (2002) 883–888. Crossref, Web of Science, Google Scholar
15. Chaos, A., Aldana, M., Espinosa-Soto, C., de Leon, B., Arroyo, A. G. and Alvares-Buylla, E. R. From genes to flower patterns and evolution: Dynamic models of gene regulatory networks, J. Plant Growth Regul. 25 (2006) 278–289. Crossref, Web of Science, Google Scholar
16. Chen, H., Li, X. and Sun, J., Stabilization, controllability and optimal control of boolean networks with impulsive effects and state constraints, IEEE Trans. Autom. Control 60 (2015) 806–811. Crossref, Web of Science, Google Scholar
17. Cheng, D. and Qi, H., Controllability and observability of boolean control networks, Automatica 45 (2009) 1659–1667. Crossref, Web of Science, Google Scholar
18. Cheng, D., Qi, H. and Li, Z., Analysis and Control of Boolean Networks: A Semi-Tensor Product Approach (Springer, New York, 2011). Crossref, Google Scholar
19. Cheng, D. and Zhao, Y., Identification of boolean control networks, Automatica 47 (2011) 702–710. Crossref, Web of Science, Google Scholar
20. Clipstone, N. A. and Crabtree, G. R., Identification of calcineurin as a key signalling enzyme in $t$ $t$ -lymphocyte activation, Lett. Nat. 357 (1992) 695–697. Crossref, Web of Science, Google Scholar
21. Coppersmith, S. N., Complexity of the predecessor problem in kauffman networks, Phys. Rev. E 75 (2007) 051108. Crossref, Web of Science, Google Scholar
22. Datta, A., Choudhary, A., Bittner, M. L. and Dougherty, E. R., External control in markovian genetic regulatory networks, Mach. Learn. 52 (2003) 169–191. Crossref, Web of Science, Google Scholar
23. Davidich, M. I. and Bornholdt, S., Boolean network model predicts cell cycle sequence of fission yeast, PLoS One 3 (2008) e1672. Crossref, Web of Science, Google Scholar
24. Drossel, B., Mihaljev, T. and Greil, F., Number and length of attractors in a critical kauffman model with connectivity one, Phys. Rev. Lett. 94 (2005) 088701. Crossref, Web of Science, Google Scholar
25. Dubrova, E., Teslenko, M. and Martinelli, A., Kauffman networks: Analysis and applications, Proc. Int. Conf. Computer-Aided Design (ICCAD’2005) (2005), pp. 479–484. Google Scholar
26. Fauré, A., Naldi, A., Chaouiya, C. and Thieffry, D., Dynamical analysis of a generic boolean model for the control of the mammalian cell cycle, Bioinformatics 22 (2006) e124–e131. Crossref, Web of Science, Google Scholar
27. Feng, J., Yao, J. and Cui, P., Singular boolean networks: Semi-tensor product approach, Sci. China Inf. Sci. 56 (2013) 112203. Google Scholar
28. Fornasini, E. and Valcher, M. E., Optimal control of boolean control networks, IEEE Trans. Autom. Control 59 (2014) 1258–1270. Crossref, Web of Science, Google Scholar
29. Gao, J., Liu, Y.-Y., D’Souza, R. M. and Barabási, A.-L., Target control of complex networks, Nat. Commun. 5 (2014) 5415. Crossref, Web of Science, Google Scholar
30. Garg, A., DeMicheli, G., Xenarios, L. and Mendoza, L., An efficient method for dynamic analysis of gene regulatory networks and in silico gene perturbation experiments, Lect. Notes Comput. Sci. 4453 (2007) 62–76. Crossref, Google Scholar
31. Giacomantonio, C. E. and Goodhill, G. J., A boolean model of the gene regulatory network underlying mammalian cortical area development, PLoS Comput. Biol. 6 (2010) e1000936. Crossref, Web of Science, Google Scholar
32. Haura, E. B., Turkson, J. and Jove, R., Mechanisms of disease: Insights into the emerging role of signal transducers and activators of transcription in cancer, Nat. Clin. Practice Oncol. 2 (2005) 315–324. Crossref, Google Scholar
33. Hayashida, M., Tamura, T., Akutsu, T., Zhang, S.-Q. and Ching, W.-K., Algorithms and complexity analyses for control of singleton attractors in boolean networks, EURASIP J. Bioinform. Syst. Biol. 2008 (2008) 521407. Crossref, Google Scholar
34. Hopcroft, J. E. and Karp, R. M., An $n^{5 / 2}$ $n^{5 / 2}$ algorithm for maximum matchings in bipartite graphs, SIAM J. Comput. 2 (1973) 225–231. Crossref, Google Scholar
35. Hwang, L. H., Lau, L. F., Smith, D. L., Mistrot, C. A., Hardwick, K. G., Hwang, E. S., Amon, A. and Murray, A. W., Budding yeast cdc20: A target of the spindle checkpoint, Science 279 (1998) 1041–1044. Crossref, Web of Science, Google Scholar
36. Karlof, J. K., Integer Programming: Theory and Practice (CRC Press, 2006). Google Scholar
37. Kauffman, S., Homeostasis and differentiation in random genetic control networks, Nature 224 (1969) 177–178. Crossref, Web of Science, Google Scholar
38. Kauffman, S., The Origins of Order: Self-Organization and Selectionin Evolution (Oxford University Press, New York, 1993). Crossref, Google Scholar
39. Kim, S. H., Lin, D. P., Matsumoto, S., Kitazono, A. and Matsumoto, T., Fission yeast slp1: An effector of the mad2-dependent spindle checkpoint, Science 279 (1998) 1045–1047. Crossref, Web of Science, Google Scholar
40. Kitano, H., Computational systems biology, Nature 420 (2002) 206–210. Crossref, Web of Science, Google Scholar
41. Kitano, H., Cancer as a robust system: Implications for anticancer therapy, Nat. Rev. Cancer 4 (2004) 227–235. Crossref, Web of Science, Google Scholar
42. Kiu, H. and Nicholson, S. E., Biology and significance of the jak/stat signalling pathways, Growth Factors 30 (2012) 88–106. Crossref, Web of Science, Google Scholar
43. Klamt, S., Saez-Rodriguez, J., Lindquist, J. A., Simeoni, L. and Giles, E. D., A methodology for the structural and functional analysis of signaling and regulatory networks, BMC Bioinform. 7 (2006) 56. Crossref, Web of Science, Google Scholar
44. Klinke, D. J., A multiscale systems perspective on cancer, immunotherapy, and interleukin-12, Mol. Cancer 9 (2010) 1. Crossref, Web of Science, Google Scholar
45. Kobayashi, K. and Hiraishi, K., An integer programming approach to optimal control problems in context-sensitive probabilistic boolean networks, Automatica 47 (2011) 1260–1264. Crossref, Web of Science, Google Scholar
46. Kobayashi, K. and Hiraishi, K., Optimal control of probabilistic boolean networks using polynomial optimization, IEICE Trans. Fundam. E95-A (2012) 1512–1517. Crossref, Web of Science, Google Scholar
47. Kyozuka, J., Harcourt, R., Peacock, W. and Dennis, E., Eucalyptus has functional equivalents of the arabidopsis ap1 gene, Plant Mol. Biol. 35 (1997) 573–584. Crossref, Web of Science, Google Scholar
48. Lähdesmäki, H., Shmulevich, I. and Yli-Harja, O., On learning gene regulatory networks under the boolean network model, Mach. Learn. 52 (2003) 147–167. Crossref, Web of Science, Google Scholar
49. Langmead, C. J. and Jha, S. K., Symbolic approaches for finding control strategies in boolean networks, J. Bioinform. Comput. Biol. 7 (2009) 323–338. Link, Google Scholar
50. Laschov, D. and Margaliot, M., A maximum principle for single-input boolean control networks, IEEE Trans. Autom. Control 56 (2011) 913–917. Crossref, Web of Science, Google Scholar
51. Leibfried, A., To, J. P., Busch, W., Stehling, S., Kehle, A., Demar, M., Kieber, J. J. and Lohmann, J. U., Wuschel controls meristem function by direct regulation of cytokinin-inducible response regulators, Nature 438 (2005) 1172–1175. Crossref, Web of Science, Google Scholar
52. Li, F., Long, T., Lu, Y., Ouyang, Q. and Tang, C., The yeast cell-cycle network is robustly designed, Proc. Natl. Acad. Sci. 101 (2004) 4781–4786. Crossref, Web of Science, Google Scholar
53. Li, F. and Sun, J., Controllability of boolean control networks with time delays in states, Automatica 47 (2011) 603–607. Crossref, Web of Science, Google Scholar
54. Li, F. and Sun, J., Controllability and optimal control of a temporal boolean network, Neural Netw. 34 (2012) 10–17. Crossref, Web of Science, Google Scholar
55. Li, H., Wang, Y. and Liu, Z., A semi-tensor product approach to pseudo-boolean functions with application to boolean control networks, Asian J. Control 16 (2014) 1073–1081. Crossref, Web of Science, Google Scholar
56. Liang, S., Fuhrman, S. and Somogyi, R., Reveal, a general reverse engineering algorithm for inference of genetic network architectures, Proc. Pac. Symp. Biocomput. 3 (1998), pp. 18–29. Google Scholar
57. Lim, C. P. and Cao, X., Structure, function, and regulation of stat proteins, Molecular Biosystems 2 (2006) 536–550. Crossref, Web of Science, Google Scholar
58. Lin, C., Structural controllability, IEEE Trans. Autom. Control AC-19 (1974) 201–208. Google Scholar
59. Liu, S. K., Smith, C. A., Arnold, R., Kiefer, F. and McGlade, C. J., The adaptor protein gads (grb2-related adaptor downstream of shc) is implicated in coupling hemopoietic progenitor kinase-1 to the activated tcr, J. Immunol. 165 (2000) 1417–1426. Crossref, Web of Science, Google Scholar
60. Liu, Y., Chen, H., Lu, J. and Wu, B., Controllability of probabilistic boolean control networks based on transition probability matrices, Automatica 52 (2015) 340–345. Crossref, Web of Science, Google Scholar
61. Liu, Y., Slotine, J. J. and Barabási, A. L., Controllability of complex networks, Nature 473 (2011) 167–173. Crossref, Web of Science, Google Scholar
62. Mendoza, L. and Xenarios, I., A method for the generation of standardized qualitative dynamical systems of regulatory networks, J. Theor. Biol. Med. Model. 3 (2006) 3–13. Crossref, Web of Science, Google Scholar
63. Mochizuki, A., Fiedler, B., Kurosawa, G. and 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. 335 (2013) 130–146. Crossref, Web of Science, Google Scholar
64. Nacher, J. C. and Akutsu, T., Dominating scale-free networks with variable scaling exponent: Heterogeneous networks are not difficult to control, New J. Phys. 14 (2015) 073005. Crossref, Web of Science, Google Scholar
65. Nacher, J. C. and Akutsu, T., Structurally robust control of complex networks, Phys. Rev. E 91 (2015) 012826. Crossref, Web of Science, Google Scholar
66. Nepusz, T. and Vicsek, T., Controlling edge dynamics in complex networks, Nature Physics 8 (2012) 568–573. Crossref, Web of Science, Google Scholar
67. Ng, M. K., Zhang, S., Ching, W.-K. and Akutsu, T., A control model for markovian genetic regulatory networks, in Transactions on Computational Systems Biology V, Lecture Notes in Bioinformatics, Vol. 4070 (Springer, Heidelberg, 2006), pp. 36–48. Crossref, Google Scholar
68. Nie, S., Wang, X., Zhang, H., Li, Q. and Wang, B., Robustness of controllability for networks based on edge-attack, PLoS One 9 (2014) e89066. Crossref, Web of Science, Google Scholar
69. Novák, B. and Tyson, J. J., Modelling the controls of the eukaryotic cell cycle, Biochem. Soc. Trans. 31 (2003) 1526–1529. Crossref, Web of Science, Google Scholar
70. Zañudo, J. G. T. and Albert, R., Cell fate reprogramming by control of intracellular network dynamics, PLoS Comput. Biol. 11 (2015) e1004193. Crossref, Web of Science, Google Scholar
71. Pal, R., Datta, A., Bittner, M. L. and Dougherty, E. R., Intervention in context-sensitive probabilistic boolean networks, Bioinform. 21 (2005) 1211–1218. Crossref, Web of Science, Google Scholar
72. Papadimitriou, C. H. and Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (Courier Corporation, 1982). Google Scholar
73. Pu, C., Pei, W. and Michaelson, A., Robustness analysis of network controllability, Physica A 391 (2012) 4420–4425. Crossref, Web of Science, Google Scholar
74. Ruths, J. and Ruths, D., Robustness of network controllability under edge removal, Complex Networks IV Proc. 4th Workshop on Complex Networks CompleNet 2013, Vol. 476 (2013), pp. 185–193. Google Scholar
75. Saadatpour, A., Wang, R.-S., Liao, A., Liu, X., Loughran, T. P., Albert, I. and Albert, R., Dynamical and structural analysis of a $t$ $t$ cell survival network identifiers novel candidate therapeutic targets for large granular lymphocyte leukemia, PLoS Comput. Biol. 7 (2011) e1002267. Crossref, Web of Science, Google Scholar
76. Samuelsson, B. and Troein, C., Superpolynomial growth in the number of attractors in kauffman networks, Phys. Rev. Lett. 90 (2003) 098701. Crossref, Web of Science, Google Scholar
77. Schrijver, A., Theory of Linear and Integer Programming (Wiley, 1998). Google Scholar
78. Schulze, A., Zerfass, K., Spitkovsky, D., Middendorp, S., Berges, J., Helin, K., Jansen-Dürr, P. and Henglein, B., Cell cycle regulation of the cyclin a gene promoter is mediated by a variant e2f site, Proc. Natl. Acad. Sci. 92 (1995) 11264–11268. Crossref, Web of Science, Google Scholar
79. Sveiczer, A., Csikasz-Nagy, A., Gyorffy, B., Tyson, J. J. and Novak, B., Modeling the fission yeast cell cycle: Quantized cycle times in wee1-cdc25 $δ$ $δ$ mutant cells, Proc. Natl. Acad. Sci. 97 (2000) 7865–7870. Crossref, Web of Science, Google Scholar
80. Takahashi, K., Tanabe, K., Ohnuki, M., Narita, M., Ichisaka, T., Tomoda, K. and Yamanaka, S., Induction of pluripotent stem cells from adult human fibroblasts by defined factors, Cell 131 (2007) 861–872. Crossref, Web of Science, Google Scholar
81. Veliz-Cuba, A., Aguilar, B., Hinkelmann, F. and Laubenbacher, R., Steady state analysis of boolean molecular network models via model reduction and computational algebra, BMC Bioinform. 15 (2014) 221. Crossref, Web of Science, Google Scholar
82. Yang, X. and Sladek, T., Overexpression of the e2f-1 transcription factor gene mediates cell transformation, Gene Expression 4 (1994) 195–204. Google Scholar
83. Zhang, S.-Q., Hayashida, M., Akutsu, T., Ching, W.-K. and Ng, M. K., Algorithms for finding small attractors in boolean networks, EURASIP J. Bioinform. Syst. Biol. 2007 (2007) 20180. Crossref, Google Scholar
84. Zhao, Y., Li, Z. and Cheng, D., Optimal control of logical control networks, IEEE Trans. Autom. Control 56 (2011) 1766–1776. Crossref, Web of Science, Google Scholar

Vol. 19, No. 03

Metrics

Downloaded 817 times

History

Received 16 April 2016

Accepted 19 July 2016

Published: 2 September 2016

Information

This is an Open Access article published by World Scientific Publishing Company. It is distributed under the terms of the Creative Commons Attribution 4.0 (CC-BY) License. Further distribution of this work is permitted, provided the original work is properly cited.

Keywords

PDF download

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

FINDING AND ANALYZING THE MINIMUM SET OF DRIVER NODES IN CONTROL OF BOOLEAN NETWORKS

Abstract

Recommended