Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (1): 16-34.doi: 10.1007/s11390-019-1896-x

Special Issue: Surveys; Artificial Intelligence and Pattern Recognition; Emerging Areas

• Special Section of Advances in Computer Science and Technology—Current Advances in the NSFC Joint Research Fund for Overseas Chinese Scholars and Scholars in Hong Kong and Macao 2014-2017 (Part 1) • Previous Articles     Next Articles

Controllability and Its Applications to Biological Networks

Lin Wu1, Min Li2, Jian-Xin Wang2, and Fang-Xiang Wu1,2,3,*, Senior Member, IEEE   

  1. 1 Division of Biomedical Engineering, University of Saskatchewan, Saskatoon, SK S7N59, Canada;
    2 School of Information Science and Engineering, Central South University, Changsha 410083, China;
    3 Department of Mechanical Engineering, University of Saskatchewan, Saskatoon, SK S7N 5A9, Canada
  • Received:2018-07-01 Revised:2018-11-08 Online:2019-01-05 Published:2019-01-12
  • Contact: Fang-Xiang Wu
  • About author:Lin Wu received his B.Sc. degree in computer science and technology from Central South University, Changsha, in 2012. Currently, he is working toward his Ph.D. degree in the Division of Biomedical Engineering at the University of Saskatchewan, Saskatoon, Canada. His current research interests include analysis of large-scale biological data, modeling, analysis, and control of biomolecular networks.
  • Supported by:
    The work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), the National Natural Science Foundation of China under Grant Nos. 61772552 and 61622213, and Chinese Scholarship Council (CSC).

Biological elements usually exert their functions through interactions with others to form various types of biological networks. The ability of controlling the dynamics of biological networks is of enormous benefits to pharmaceutical and medical industry as well as scientific research. Though there are many mathematical methods for steering dynamic systems towards desired states, the methods are usually not feasible for applying to complex biological networks. The difficulties come from the lack of accurate model that can capture the dynamics of interactions between biological elements and the fact that many mathematical methods are computationally intractable for large-scale networks. Recently, a concept in control theory—controllability, has been applied to investigate the dynamics of complex networks. In this article, recent advances on the controllability of complex networks and applications to biological networks are reviewed. Developing dynamic models is the prior concern for analyzing dynamics of biological networks. First, we introduce a widely used dynamic model for investigating controllability of complex networks. Then recent studies of theorems and algorithms for having complex biological networks controllable in general or specific application scenarios are reviewed. Finally, applications to real biological networks manifest that investigating the controllability of biological networks can shed lights on many critical physiological or medical problems, such as revealing biological mechanisms and identifying drug targets, from a systematic perspective.

Key words: biological network; network controllability; steering node;

[1] Ito T, Chiba T, Ozawa R et al. A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proceedings of the National Academy of Sciences, 2001, 98(8):4569-4574.
[2] Sprinzak E, Margalit H. Correlated sequence-signatures as markers of protein-protein interaction. Journal of Molecular Biology, 2001, 311(4):681-692.
[3] Liu L Z, Wu F X, Zhang W J. Reverse engineering of gene regulatory networks from biological data. Wiley Interdisciplinary Reviews:Data Mining and Knowledge Discovery, 2012, 2(5):365-385.
[4] Gu S, Pasqualetti F, Cieslak M et al. Controllability of structural brain networks. Nature Communications, 2015, 6:Article No. 8414.
[5] Csermely P, Agoston V, Pongor S. The efficiency of multitarget drugs:The network approach might help drug design. Trends in Pharmacological Sciences, 2005, 26(4):178-182.
[6] Dai Y F, Zhao X M. A survey on the computational approaches to identify drug targets in the postgenomic era. BioMed Research International, 2015, 2015:Article No. 239654.
[7] Wang X, Gulbahce N, Yu H. Network-based methods for human disease gene prediction. Briefings in Functional Genomics, 2011, 10(5):280-293.
[8] Chen B, Fan W, Liu J et al. Identifying protein complexes and functional modules-From static PPI networks to dynamic PPI networks. Briefings in Bioinformatics, 2013, 15(2):177-194.
[9] Kalman R E. Mathematical description of linear dynamical systems. Journal of the Society for Industrial and Applied Mathematics Control, Series A, 1963, 1(2):152-192.
[10] Lin C T. Structural controllability. IEEE Transactions on Automatic Control, 1974, 19(3):201-208.
[11] Liu Y Y, Slotine J J, Barabási A L. Controllability of complex networks. Nature, 2011, 473(7346):167-173.
[12] Wang B, Gao L, Zhang Q et al. Diversified control paths:A significant way disease genes perturb the human regulatory network. PLoS One, 2015, 10(8):Article No. e0135491.
[13] Wu L, Shen Y, Li M et al. Network output controllabilitybased method for drug target identification. IEEE Transactions on Nano Bioscience, 2015, 14(2):184-191.
[14] Yan G, Vértes P E, Towlson E K et al. Network control principles predict neuron function in the caenorhabditis elegans connectome. Nature, 2017, 550(7677):519-523.
[15] D'haeseleer P, Wen X, Fuhrman S et al. Linear modeling of mRNA expression levels during CNS development and injury. Pacific Symposium on Biocomputing, 1999, 4:41-52.
[16] Slotine J J, Li W. Applied Nonlinear Control. Pearson, 1991.
[17] Liu Y Y, Barabási A L. Control principles of complex systems. Reviews of Modern Physics, 2016, 88(3):Article 035006.
[18] Shields R, Pearson J. Structural controllability of multiinput linear systems. IEEE Transactions on Automatic Control, 1976, 21(2):203-212.
[19] Glover K, Silverman L. Characterization of structural controllability. IEEE Transactions on Automatic Control, 1976, 21(4):534-537.
[20] Hosoe S, Matsumoto K. On the irreducibility condition in the structural controllability theorem. IEEE Transactions on Automatic Control, 1979, 24(6):963-966.
[21] Linnemann A. A further simplification in the proof of the structural controllability theorem. IEEE Transactions on Automatic Control, 1986, 31(7):638-639.
[22] Hosoe S. Determination of generic dimensions of controllable subspaces and its application. IEEE Transactions on Automatic Control, 1980, 25(6):1192-1196.
[23] Poljak S. On the generic dimension of controllable subspaces. IEEE Transactions on Automatic Control, 1990, 35(3):367-369.
[24] Murota K, Poljak S. Note on a graph-theoretic criterion for structural output controllability. IEEE Transactions on Automatic Control, 1990, 35(8):939-942.
[25] Wu F X, Wu L, Wang J et al. Transittability of complex networks and its applications to regulatory biomolecular networks. Scientific Reports, 2014, 4:Article No. 4819.
[26] Mayeda H, Yamada T. Strong structural controllability. SIAM Journal on Control and Optimization, 1979, 17(1):123-138.
[27] Tu C. Strong structural control centrality of a complex network. Physica Scripta, 2015, 90(3):Article No. 035202.
[28] Nepusz T, Vicsek T. Controlling edge dynamics in complex networks. Nature Physics, 2012, 8(7):568-573.
[29] 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):Article No. e38398.
[30] Nie S, Wang X, Zhang H et al. Robustness of controllability for networks based on edge-attack. PLoS One, 2014, 9(2):Article No. e89066.
[31] Wang W X, Ni X, Lai Y C et al. Optimizing controllability of complex networks by minimum structural perturbations. Physical Review E, 2012, 85(2):Article No. 026115.
[32] Wu L, Li M, Wang J et al. CytoCtrlAnalyser:A cytoscape app for biomolecular network controllability analysis. Bioinformatics, 2018, 34(8):1428-1430.
[33] Wu L, Li M, Wang J et al. Minimum steering node set of complex networks and its applications to biomolecular networks. IET Systems Biology, 2016, 10(3):116-123.
[34] Liu Y Y, Slotine J J, Barabási A L. Control centrality and hierarchical structure in complex networks. PLoS One, 2012, 7(9):Article No. e44459.
[35] Iudice F L, Garofalo F, Sorrentino F. Structural permeability of complex networks to control signals. Nature Communications, 2015, 6:Article No. 8349.
[36] Liu X, Pan L. Controllability of the better chosen partial networks. Physica A:Statistical Mechanics and Its Applications, 2016, 456:120-127.
[37] Commault C, van der Woude J, Boukhobza T. On the fixed controllable subspace in linear structured systems. Systems & Control Letters, 2017, 102:42-47.
[38] Wu L, Shen Y, Li M et al. Drug target identification based on structural output controllability of complex networks. In Proc. the 10th International Symposium Bioinformatics Research and Applications, June 2014, pp.188-199.
[39] Gao J, Liu Y Y, D'Souza R M et al. Target control of complex networks. Nature Communications, 2014, 5:Article No. 5415.
[40] Ogata K. Modern Control Engineering (3rd edition). Prentice Hall, 1996.
[41] Hopcroft J E, Karp R M. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 1973, 2(4):225-231.
[42] Zhang X, Lv T, Yang X et al. Structural controllability of complex networks based on preferential matching. PLoS One, 2014, 9(11):Article No. e112039.
[43] Goodrich M T, Tamassia R. Algorithm Design:Foundation, Analysis and Internet Examples. John Wiley & Sons, 2006.
[44] Wu L, Tang L, Li M et al. The MSS of complex networks with centrality based preference and its application to biomolecular networks. In Proc. the 2016 IEEE International Conference on Bioinformatics and Biomedicine, December 2016, pp.229-234.
[45] Pequito S, Kar S, Aguiar A P. On the complexity of the constrained input selection problem for structural linear systems. Automatica, 2015, 62:193-199.
[46] Lindmark G, Altafini C. Controllability of complex networks with unilateral inputs. Scientific Reports, 2017, 7:Article No. 1824.
[47] Rugh W J, Kailath T. Linear System Theory (2nd edition). Pearson, 1995.
[48] Wang L Z, Chen Y Z, Wang W X et al. Physical controllability of complex networks. Scientific Reports, 2017, 7:Article No. 40198.
[49] Li G, Tang P, Wen C et al. Boundary constraints for minimum cost control of directed networks. IEEE Transactions on Cybernetics, 2017, 47(12):4196-4207.
[50] Czeizler E, Gratie C, Chiu W K et al. Target controllability of linear networks. In Proc. the 14th International Conference on Computational Methods in Systems Biology, September 2016, pp.67-81.
[51] Kuhn H W. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 1955, 2(1/2):83-97.
[52] Zhang X, Wang H, Lv T. Efficient target control of complex networks based on preferential matching. PLoS One, 2017, 12(4):Article No. e0175375.
[53] Liu X, Pan L, Stanley H E et al. Controllability of giant connected components in a directed network. Physical Review E, 2017, 95(4):Article No. 042318.
[54] Piao X, Lv T, Zhang X et al. Strategy for community control of complex networks. Physica A:Statistical Mechanics and Its Applications, 2015, 421:98-108.
[55] Guo W F, Zhang S W, Wei Z G et al. Constrained target controllability of complex networks. Journal of Statistical Mechanics:Theory and Experiment, 2017, 2017(6):Article No. 063402.
[56] Khazanchi R, Dempsey K, Thapa I et al. On identifying and analyzing significant nodes in protein-protein interaction networks. In Proc. the 23rd IEEE International Conference on Data Mining Workshops, December 2013, pp.343-348.
[57] Badhwar R, Bagler G. Control of neuronal network in caenorhabditis elegans. PLoS One, 2015, 10(9):Article No. e0139204.
[58] Noori H R, Schöttler J, Ercsey-Ravasz M et al. A multiscale cerebral neurochemical connectome of the rat brain. PLoS Biology, 2017, 15(7):Article No. e2002612.
[59] Deisseroth K. Circuit dynamics of adaptive and maladaptive behaviour. Nature, 2014, 505(7483):309-317.
[60] Kringelbach M L, Jenkinson N, Owen S L et al. Translational principles of deep brain stimulation. Nature Reviews Neuroscience, 2007, 8(8):623-635.
[61] Li F, Long T, Lu Y et al. The yeast cell-cycle network is robustly designed. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(14):4781-4786.
[62] Davidich M I, Bornholdt S. Boolean network model predicts cell cycle sequence of fission yeast. PLoS One, 2008, 3(2):Article No. e1672.
[63] 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):Article No. e35440.
[64] 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):Article No. e22649.
[65] Mendoza L. A network model for the control of the differentiation process in Th cells. Biosystems, 2006, 84(2):101-114.
[66] Lee H J, Takemoto N, Kurata H et al. Gata-3 induces T helper cell type 2(Th2) cytokine expression and chromatin remodeling in committed Th1 cells. Journal of Experimental Medicine, 2000, 192(1):105-116.
[67] Szabo S J, Kim S T, Costa G L et al. A novel transcription factor, T-bet, directs Th1 lineage commitment. Cell, 2000, 100(6):655-669.
[68] Hwang E S, Szabo S J, Schwartzberg P L et al. T helper cell fate specified by kinase-mediated interaction of T-bet with GATA-3. Science, 2005, 307(5708):430-433.
[69] Kanhaiya K, Czeizler E, Gratie C et al. Controlling directed protein interaction networks in cancer. Technical Report, Turku Centre for Computer Science, 2017., Nov. 2018.
[70] Wu L, Tang L, Li M et al. Biomolecular network controllability with drug binding information. IEEE Transactions on Nano Bioscience, 2017, 16(5):326-332.
[71] Jia T, Liu Y Y, Csóka E et al. Emergence of bimodality in controlling complex networks. Nature Communications, 2013, 4:Article No. 2002.
[72] Liu X, Pan L. Identifying driver nodes in the human signaling network using structural controllability analysis. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2015, 12(2):467-472.
[73] Jia T, Barabási A L. Control capacity and a random sampling method in exploring controllability of complex networks. Scientific Reports, 2013, 3:Article No. 2354.
[74] Liu X, Pan L. Detection of driver metabolites in the human liver metabolic network using structural controllability analysis. BMC Systems Biology, 2014, 8(1):Article No. 51.
[75] Vinayagam A, Gibson T E, Lee H J et al. Controllability analysis of the directed human protein interaction network identifies disease genes and drug targets. Proceedings of the National Academy of Sciences of the United States of America, 2016, 113(18):4976-4981.
[76] Matsuoka Y, Matsumae H, Katoh M et al. A comprehensive map of the influenza A virus replication cycle. BMC Systems Biology, 2013, 7(1):Article No. 97.
[77] Uhart M, Flores G, Bustos D. M. Controllability of proteinprotein interaction phosphorylation-based networks:Participation of the hub 14-3-3 protein family. Scientific Reports, 2016, 6:Article No. 26234.
[78] Ravindran V, Sunitha V, Bagler G. Identification of critical regulatory genes in cancer signaling network using controllability analysis. Physica A:Statistical Mechanics and Its Applications, 2017, 474:134-143.
[79] Ruths J, Ruths D. Control profiles of complex networks. Science, 2014, 343(6177):1373-1376.
[80] Tu C, Rocha R P, Corbetta M et al. Warnings and caveats in brain controllability. Neuroimage, 2017, 176:83-91.
[81] Vanunu O, Magger O, Ruppin E et al. Associating genes and protein complexes with disease via network propagation. PLoS Computational Biology, 2010, 6(1):Article No. e1000641.
[82] Wang B, Gao L, Gao Y. Control range:A controllabilitybased index for node significance in directed networks. Journal of Statistical Mechanics:Theory and Experiment, 2012, 2012(04):Article No. P04011.
[83] Wang B, Gao L, Gao Y et al. Controllability and observability analysis for vertex domination centrality in directed networks. Scientific Reports, 2014, 4:Article No. 5399.
No related articles found!
Full text



No Suggested Reading articles found!

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved