Minimum steering node set of complex networks and its applications to biomolecular networks

Lin Wu; Min Li; Jianxin Wang; Fang-Xiang Wu

Minimum steering node set of complex networks and its applications to biomolecular networks

View Fulltext

Author(s): Lin Wu ¹¹ ; Min Li ²² ; Jianxin Wang ²² ; Fang-Xiang Wu ^{1, 3}^{1, 3}
- Affiliations: 1: Division of Biomedical Engineering, University of Saskatchewan, Saskatoon, Canada, SK S7N 5A9 ;
  2: School of Information Science and Engineering, Central South University, Changsha, Hunan 410083, People's Republic of China ;
  3: School of Mathematical Sciences, Nankai University, Tianjin 300071, People's Republic of China
Source: Volume 10, Issue 3, June 2016, p. 116 – 123
DOI: 10.1049/iet-syb.2015.0077 , Print ISSN 1751-8849, Online ISSN 1751-8857

Received 17/10/2015, Accepted 22/12/2015, Revised 25/11/2015, Published 01/06/2016

Many systems of interests in practices can be represented as complex networks. For biological systems, biomolecules do not perform their functions alone but interact with each other to form so-called biomolecular networks. A system is said to be controllable if it can be steered from any initial state to any other final state in finite time. The network controllability has become essential to study the dynamics of the networks and understand the importance of individual nodes in the networks. Some interesting biological phenomena have been discovered in terms of the structural controllability of biomolecular networks. Most of current studies investigate the structural controllability of networks in notion of the minimum driver node sets (MDSs). In this study, the authors analyse the network structural controllability in notion of the minimum steering node sets (MSSs). They first develop a graph-theoretic algorithm to identify the MSS for a given network and then apply it to several biomolecular networks. Application results show that biomolecules identified in the MSSs play essential roles in corresponding biological processes. Furthermore, the application results indicate that the MSSs can reflect the network dynamics and node importance in controlling the networks better than the MDSs.

References

1. 1)
  - 32. Sharir, M.: ‘A strong-connectivity algorithm and its applications in data flow analysis’, Comput. Math. Appl., 1981, 7, (1), pp. 67–72 (doi: 10.1016/0898-1221(81)90008-0).
2. 2)
  - 34. Goodrich, M.T., Tamassia, R.: ‘Algorithm design: foundation, analysis and internet examples’ (1em plus 0.5em minus 0.4em, John Wiley & Sons, 2006).
3. 3)
  - 22. Jia, T., Barabási, A.: ‘Control capacity and a random sampling method in exploring controllability of complex networks’, Sci. Rep., 2013, 3, p. 2354 (doi: 10.1038/srep02354).
4. 4)
  - 25. Liu, X., Pan, L.: ‘Identifying driver nodes in the human signaling network using structural controllability analysis’, IEEE/ACM Trans. Comput. Biol. Bioinf., 2015, 12, (2), pp. 467–472 (doi: 10.1109/TCBB.2014.2360396).
5. 5)
  - 4. Yang, K., Bai, H., Ouyang, Q., et al: ‘Finding multiple target optimal intervention in disease related molecular network’, Mol. Syst. Biol., 2008, 4, p. 228 (doi: 10.1038/msb.2008.60).
6. 6)
  - 37. Davidich, M.I., Bornholdt, S.: ‘Boolean network model predicts cell cycle sequence of fission yeast’, PloS One, 2008, 3, (2), p. e1672 (doi: 10.1371/journal.pone.0001672).
7. 7)
  - 12. Nepusz, T., Vicsek, T.: ‘Controlling edge dynamics in complex networks’, Nat. Phys., 2012, 8, pp. 568–573 (doi: 10.1038/nphys2327).
8. 8)
  - 29. Yin, H., Zhang, S.: ‘Minimum structural controllability problems of complex networks’, Phys. A, Stat. Mech. Appl., 2015, 43, pp. 467–476.
9. 9)
  - 10. Rosenbrock, H.H.: ‘State-space and multivariable theory’, 1970.
10. 10)
  - 11. Liu, Y., Zhao, S.: ‘Controllability for a class of linear time-varying impulsive systems with time delay in control input’, IEEE Trans. Autom. Control, 2011, 56, (2), pp. 395–399 (doi: 10.1109/TAC.2010.2088811).
11. 11)
  - 8. Liu, Y., Chen, H., Wu, B., et al: ‘A Mayer-type optimal control for multivalued logic control networks with undesirable states’, Appl. Math. Model., 2015, 39, (12), pp. 3357–3365 (doi: 10.1016/j.apm.2014.11.028).
12. 12)
  - 2. Boccaletti, S., Latora, V., Moreno, Y., et al: ‘Complex networks: structure and dynamics’, Phys. Rep., 2006, 424, pp. 175–308 (doi: 10.1016/j.physrep.2005.10.009).
13. 13)
  - 5. Cornelius, S.P., Kath, W.L., Motter, A.E.: ‘Realistic control of network dynamics’, Nat. Commun., 2013, 4, p. 1942 (doi: 10.1038/ncomms2939).
14. 14)
  - 27. Olshevsky, A.: ‘Minimal controllability problems’, IEEE Trans. Control Netw. Syst., 2014, 1, (3), pp. 249–258 (doi: 10.1109/TCNS.2014.2337974).
15. 15)
  - 14. Shields, R., Pearson, J.: ‘Structural controllability of multiinput linear systems’, IEEE Trans. Autom. Control, 1976, AC-21, (2), pp. 201–208.
16. 16)
  - 1. Newman, M.E.J.: ‘The structure and function of complex networks’, SIAM Rev., 2003, 45, (2), pp. 167–256 (doi: 10.1137/S003614450342480).
17. 17)
  - 38. Moes, M., Le Béchec, A., Crespo, I., et al: ‘A novel network integrating a mirna-203/snai1 feedback loop which regulates epithelial to mesenchymal transition’, PloS One, 2012, 7, (4), p. e35440 (doi: 10.1371/journal.pone.0035440).
18. 18)
  - 40. Zhang, P., Iwasaki-Arai, J., Iwasaki, H., et al: ‘Enhancement of hematopoietic stem cell repopulating capacity and self-renewal in the absence of the transcription factor c/ebpα’, Immunity, 2004, 21, (6), pp. 853–863 (doi: 10.1016/j.immuni.2004.11.006).
19. 19)
  - 13. Lin, C.: ‘Structural controllability’, IEEE Trans. Autom. Control, 1974, AC-19, (3), pp. 201–208.
20. 20)
  - 31. Edmonds, J., Karp, R.M.: ‘Theoretical improvements in algorithmic efficiency for network flow problems’, J. ACM (JACM), 1972, 19, (2), pp. 248–264 (doi: 10.1145/321694.321699).
21. 21)
  - 7. Liu, Y., Lu, J., Wu, B.: ‘Some necessary and sufficient conditions for the output controllability of temporal Boolean control networks’, ESAIM Control Optim. Calc. Var., 2014, 20, (1), p. 158 (doi: 10.1051/cocv/2013059).
22. 22)
  - 16. Poljak, S.: ‘On the generic dimension of controllable subspaces’, IEEE Trans. Autom. Control, 1990, 35, (3), pp. 367–369 (doi: 10.1109/9.50361).
23. 23)
  - 6. Kim, J., Park, S.M., Cho, K.H.: ‘Discovery of a kernel for controlling biomolecular regulatory networks’, Sci. Rep., 2013, 3, p. 2223.
24. 24)
  - 28. Olshevsky, A.: ‘Minimum input selection for structural controllability’, arXiv preprint arXiv:1407.2884, 2014, pp. 2218–2223.
25. 25)
  - 32. Hopcroft John, E., Karp, , et al: ‘An n5/2 algorithm for maximum matchings in bipartite graphs’, SIAM J. Comput., 1973, 2, (4), pp. 225–231 (doi: 10.1137/0202019).
26. 26)
  - 36. Li, F., Long, T., Lu, Y., et al: ‘The yeast cell-cycle network is robustly designed’. Proc. of the National Academy of Sciences of the United States of America, 2004, vol. 101, no. 14, pp. 4781–4786.
27. 27)
  - 41. Friedman, A.D.: ‘C/ebpα induces pu. 1 and interacts with ap-1 and nf-κb to regulate myeloid development’, Blood Cells Mol. Diseases, 2007, 39, (3), pp. 340–343 (doi: 10.1016/j.bcmd.2007.06.010).
28. 28)
  - 14. Kalman, R.E.: ‘Mathematical description of linear dynamical systems’, J. Soc. Ind. Appl. Math. Ser. A, 1963, 1, pp. 152–192 (doi: 10.1137/0301010).
29. 29)
  - 26. Badhwar, R., Bagler, G.: ‘Control of neuronal network in Caenorhabditis elegans’, PloS One, 2015, 10, (9), p. e0139204 (doi: 10.1371/journal.pone.0139204).
30. 30)
  - 15. Hosoe, S.: ‘Determination of generic dimensions of controllable subspaces and its application’, IEEE Trans. Autom. Control, 1980, AC-25, (6), pp. 1192–1196 (doi: 10.1109/TAC.1980.1102506).
31. 31)
  - 39. Krumsiek, J., Marr, C., Schroeder, T., et al: ‘Hierarchical differentiation of myeloid progenitors is encoded in the transcription factor network’, PloS One, 2011, 6, (8), p. e22649 (doi: 10.1371/journal.pone.0022649).
32. 32)
  - 7. Liu, Y.Y., Slotine, J.J., Barabasi, A.L.: ‘Controllability of complex networks’, Nature, 2011, 473, (7346), pp. 167–173 (doi: 10.1038/nature10011).
33. 33)
  - 20. Gao, J., Liu, Y.-Y., D'Souza, R.M., et al: ‘Target control of complex networks’, Nat. Commun., 2014, 5, p. 5415 (doi: 10.1038/ncomms6415).
34. 34)
  - 8. Cowan, N.J., Chastain, E.J., Vilhena, D.A., et al: ‘Nodal dynamics, not degree distributions, determine the structural controllability of complex networks’, PLoS One, 2012, 7, (6), p. 38398 (doi: 10.1371/journal.pone.0038398).
35. 35)
  - 11. Ruths, J., Ruths, D.: ‘Control profiles of complex networks’, Science, 2014, 343, (6177), pp. 1373–1376 (doi: 10.1126/science.1242063).
36. 36)
  - 9. Liu, Y., Chen, H., Lu, J., et al: ‘Controllability of probabilistic Boolean control networks based on transition probability matrices’, Automatica, 2015, 52, pp. 340–345 (doi: 10.1016/j.automatica.2014.12.018).
37. 37)
  - 21. Albert, R., Barabási, A.-L.: ‘Statistical mechanics of complex networks’, Rev. Mod. Phys., 2002, 74, (1), p. 47 (doi: 10.1103/RevModPhys.74.47).
38. 38)
  - 24. Liu, X., Pan, L.: ‘Detection of driver metabolites in the human liver metabolic network using structural controllability analysis’, BMC Syst. Biol., 2014, 8, (1), p. 51 (doi: 10.1186/1752-0509-8-51).
39. 39)
  - 21. Liu, Y.-Y., Slotine, J.-J., Barabási, A.-L.: ‘Control centrality and hierarchical structure in complex networks’, PLoS One, 2012, 7, (9), p. e44459 (doi: 10.1371/journal.pone.0044459).
40. 40)
  - 19. Wu, L., Shen, Y., Li, M., et al: ‘Drug target identification based on structural output controllability of complex networks’, Bioinf. Res. Appl., 1em plus 0.5em minus 0.4em Springer, 2014, pp. 188–199.
41. 41)
  - 18. Wu, F.-X., Wu, L., Wang, J., et al: ‘Transittability of complex networks and its applications to regulatory biomolecular networks’, Sci. Rep., 2014, 4, pp. 4819.

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Minimum steering node set of complex networks and its applications to biomolecular networks

References

Related content