1
|
Tokuhara Y, Akutsu T, Schwartz JM, Nacher JC. A practically efficient algorithm for identifying critical control proteins in directed probabilistic biological networks. NPJ Syst Biol Appl 2024; 10:87. [PMID: 39134558 PMCID: PMC11319667 DOI: 10.1038/s41540-024-00411-y] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/21/2024] [Accepted: 07/22/2024] [Indexed: 08/15/2024] Open
Abstract
Network controllability is unifying the traditional control theory with the structural network information rooted in many large-scale biological systems of interest, from intracellular networks in molecular biology to brain neuronal networks. In controllability approaches, the set of minimum driver nodes is not unique, and critical nodes are the most important control elements because they appear in all possible solution sets. On the other hand, a common but largely unexplored feature in network control approaches is the probabilistic failure of edges or the uncertainty in the determination of interactions between molecules. This is particularly true when directed probabilistic interactions are considered. Until now, no efficient algorithm existed to determine critical nodes in probabilistic directed networks. Here we present a probabilistic control model based on a minimum dominating set framework that integrates the probabilistic nature of directed edges between molecules and determines the critical control nodes that drive the entire network functionality. The proposed algorithm, combined with the developed mathematical tools, offers practical efficiency in determining critical control nodes in large probabilistic networks. The method is then applied to the human intracellular signal transduction network revealing that critical control nodes are associated with important biological features and perturbed sets of genes in human diseases, including SARS-CoV-2 target proteins and rare disorders. We believe that the proposed methodology can be useful to investigate multiple biological systems in which directed edges are probabilistic in nature, both in natural systems or when determined with large uncertainties in-silico.
Collapse
Affiliation(s)
- Yusuke Tokuhara
- Department of Information Science, Faculty of Science, Toho University, Funabashi, Chiba, Japan
| | - Tatsuya Akutsu
- Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto, Uji, Japan
| | | | - Jose C Nacher
- Department of Information Science, Faculty of Science, Toho University, Funabashi, Chiba, Japan.
| |
Collapse
|
2
|
Someya W, Akutsu T, Schwartz JM, Nacher JC. Measuring criticality in control of complex biological networks. NPJ Syst Biol Appl 2024; 10:9. [PMID: 38245555 PMCID: PMC10799883 DOI: 10.1038/s41540-024-00333-9] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/02/2023] [Accepted: 01/04/2024] [Indexed: 01/22/2024] Open
Abstract
Recent controllability analyses have demonstrated that driver nodes tend to be associated to genes related to important biological functions as well as human diseases. While researchers have focused on identifying critical nodes, intermittent nodes have received much less attention. Here, we propose a new efficient algorithm based on the Hamming distance for computing the importance of intermittent nodes using a Minimum Dominating Set (MDS)-based control model. We refer to this metric as criticality. The application of the proposed algorithm to compute criticality under the MDS control framework allows us to unveil the biological importance and roles of the intermittent nodes in different network systems, from cellular level such as signaling pathways and cell-cell interactions such as cytokine networks, to the complete nervous system of the nematode worm C. elegans. Taken together, the developed computational tools may open new avenues for investigating the role of intermittent nodes in many biological systems of interest in the context of network control.
Collapse
Affiliation(s)
- Wataru Someya
- Department of Information Science, Faculty of Science, Toho University, Funabashi, Chiba, 274-8510, Japan
| | - Tatsuya Akutsu
- Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto, Uji, 611-0011, Japan
| | - Jean-Marc Schwartz
- School of Biological Sciences, University of Manchester, Manchester, M13 9PT, UK
| | - Jose C Nacher
- Department of Information Science, Faculty of Science, Toho University, Funabashi, Chiba, 274-8510, Japan.
| |
Collapse
|
3
|
Wang P, Wen X, Li H, Lang P, Li S, Lei Y, Shu H, Gao L, Zhao D, Zeng J. Deciphering driver regulators of cell fate decisions from single-cell transcriptomics data with CEFCON. Nat Commun 2023; 14:8459. [PMID: 38123534 PMCID: PMC10733330 DOI: 10.1038/s41467-023-44103-3] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/07/2023] [Accepted: 11/30/2023] [Indexed: 12/23/2023] Open
Abstract
Single-cell technologies enable the dynamic analyses of cell fate mapping. However, capturing the gene regulatory relationships and identifying the driver factors that control cell fate decisions are still challenging. We present CEFCON, a network-based framework that first uses a graph neural network with attention mechanism to infer a cell-lineage-specific gene regulatory network (GRN) from single-cell RNA-sequencing data, and then models cell fate dynamics through network control theory to identify driver regulators and the associated gene modules, revealing their critical biological processes related to cell states. Extensive benchmarking tests consistently demonstrated the superiority of CEFCON in GRN construction, driver regulator identification, and gene module identification over baseline methods. When applied to the mouse hematopoietic stem cell differentiation data, CEFCON successfully identified driver regulators for three developmental lineages, which offered useful insights into their differentiation from a network control perspective. Overall, CEFCON provides a valuable tool for studying the underlying mechanisms of cell fate decisions from single-cell RNA-seq data.
Collapse
Affiliation(s)
- Peizhuo Wang
- Institute for Interdisciplinary Information Sciences, Tsinghua University, 100084, Beijing, China
- School of Engineering, Westlake University, 310030, Hangzhou, Zhejiang Province, China
| | - Xiao Wen
- CAS Key Laboratory of Genomic and Precision Medicine, Beijing Institute of Genomics, Chinese Academy of Sciences and China National Center for Bioinformation, 100101, Beijing, China
| | - Han Li
- Institute for Interdisciplinary Information Sciences, Tsinghua University, 100084, Beijing, China
| | - Peng Lang
- Institute for Interdisciplinary Information Sciences, Tsinghua University, 100084, Beijing, China
| | - Shuya Li
- Institute for Interdisciplinary Information Sciences, Tsinghua University, 100084, Beijing, China
- School of Engineering, Westlake University, 310030, Hangzhou, Zhejiang Province, China
| | - Yipin Lei
- Institute for Interdisciplinary Information Sciences, Tsinghua University, 100084, Beijing, China
| | - Hantao Shu
- Institute for Interdisciplinary Information Sciences, Tsinghua University, 100084, Beijing, China
| | - Lin Gao
- School of Computer Science and Technology, Xidian University, 710071, Xi'an, Shaanxi Province, China
| | - Dan Zhao
- Institute for Interdisciplinary Information Sciences, Tsinghua University, 100084, Beijing, China.
| | - Jianyang Zeng
- Institute for Interdisciplinary Information Sciences, Tsinghua University, 100084, Beijing, China.
- School of Engineering, Westlake University, 310030, Hangzhou, Zhejiang Province, China.
| |
Collapse
|
4
|
Yamaguchi E, Akutsu T, Nacher JC. Probabilistic Critical Controllability Analysis of Protein Interaction Networks Integrating Normal Brain Ageing Gene Expression Profiles. Int J Mol Sci 2021; 22:ijms22189891. [PMID: 34576052 PMCID: PMC8465977 DOI: 10.3390/ijms22189891] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/22/2021] [Revised: 08/27/2021] [Accepted: 09/05/2021] [Indexed: 11/16/2022] Open
Abstract
Recently, network controllability studies have proposed several frameworks for the control of large complex biological networks using a small number of life molecules. However, age-related changes in the brain have not been investigated from a controllability perspective. In this study, we compiled the gene expression profiles of four normal brain regions from individuals aged 20–99 years and generated dynamic probabilistic protein networks across their lifespan. We developed a new algorithm that efficiently identified critical proteins in probabilistic complex networks, in the context of a minimum dominating set controllability model. The results showed that the identified critical proteins were significantly enriched with well-known ageing genes collected from the GenAge database. In particular, the enrichment observed in replicative and premature senescence biological processes with critical proteins for male samples in the hippocampal region led to the identification of possible new ageing gene candidates.
Collapse
Affiliation(s)
- Eimi Yamaguchi
- Department of Information Science, Faculty of Science, Toho University, Funabashi 274-8510, Japan;
| | - Tatsuya Akutsu
- Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji 611-0011, Japan;
| | - Jose C. Nacher
- Department of Information Science, Faculty of Science, Toho University, Funabashi 274-8510, Japan;
- Correspondence:
| |
Collapse
|
5
|
Ebrahimi A, Yousefi M, Shahbazi F, Sheikh Beig Goharrizi MA, Masoudi-Nejad A. Nodes with the highest control power play an important role at the final level of cooperation in directed networks. Sci Rep 2021; 11:13668. [PMID: 34211043 PMCID: PMC8249622 DOI: 10.1038/s41598-021-93144-5] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/21/2021] [Accepted: 06/18/2021] [Indexed: 02/06/2023] Open
Abstract
Controllability of complex networks aims to seek the lowest number of nodes (the driver nodes) that can control all the nodes by receiving the input signals. The concept of control centrality is used to determine the power of each node to control the network. The more a node controls the nodes through connections in the network, the more it has the power to control. Although the cooperative and free-rider strategies and the final level of cooperation in a population are considered and studied in the public goods game. However, it is yet to determine a solution to indicate the effectiveness of each member in changing the strategies of the other members. In a network, the choice of nodes effective in changing the other nodes' strategies, as free-riders, will lead to lower cooperation and vice versa. This paper uses simulated and real networks to investigate that the nodes with the highest control power are more effective than the hubs, local, and random nodes in changing the strategies of the other nodes and the final level of cooperation. Results indicate that the nodes with the highest control power as free-riders, compared to the other sets being under consideration, can lead to a lower level of cooperation and are, therefore, more effective in changing the strategies of the other nodes. The obtained results can be considered in the treatment of cancer. So that, destroying the tumoral cells with the highest control power should be a priority as these cells have a higher capability to change the strategies of the other cells from cooperators to free-riders (healthy to tumoral).
Collapse
Affiliation(s)
- Ali Ebrahimi
- Laboratory of Systems Biology and Bioinformatics (LBB), Institute of Biochemistry and Biophysics, University of Tehran, Tehran, Iran
| | - Marzieh Yousefi
- Department of Physics, Isfahan University of Technology (IUT), Isfahan, Iran
| | - Farhad Shahbazi
- Department of Physics, Isfahan University of Technology (IUT), Isfahan, Iran
| | | | - Ali Masoudi-Nejad
- Laboratory of Systems Biology and Bioinformatics (LBB), Institute of Biochemistry and Biophysics, University of Tehran, Tehran, Iran.
| |
Collapse
|
6
|
Network controllability analysis of intracellular signalling reveals viruses are actively controlling molecular systems. Sci Rep 2019; 9:2066. [PMID: 30765882 PMCID: PMC6375943 DOI: 10.1038/s41598-018-38224-9] [Citation(s) in RCA: 13] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/21/2018] [Accepted: 12/21/2018] [Indexed: 12/19/2022] Open
Abstract
In recent years control theory has been applied to biological systems with the aim of identifying the minimum set of molecular interactions that can drive the network to a required state. However, in an intra-cellular network it is unclear how control can be achieved in practice. To address this limitation we use viral infection, specifically human immunodeficiency virus type 1 (HIV-1) and hepatitis C virus (HCV), as a paradigm to model control of an infected cell. Using a large human signalling network comprised of over 6000 human proteins and more than 34000 directed interactions, we compared two states: normal/uninfected and infected. Our network controllability analysis demonstrates how a virus efficiently brings the dynamically organised host system into its control by mostly targeting existing critical control nodes, requiring fewer nodes than in the uninfected network. The lower number of control nodes is presumably to optimise exploitation of specific sub-systems needed for virus replication and/or involved in the host response to infection. Viral infection of the human system also permits discrimination between available network-control models, which demonstrates that the minimum dominating set (MDS) method better accounts for how the biological information and signals are organised during infection by identifying most viral proteins as critical driver nodes compared to the maximum matching (MM) method. Furthermore, the host driver nodes identified by MDS are distributed throughout the pathways enabling effective control of the cell via the high ‘control centrality’ of the viral and targeted host nodes. Our results demonstrate that control theory gives a more complete and dynamic understanding of virus exploitation of the host system when compared with previous analyses limited to static single-state networks.
Collapse
|
7
|
Liu X, Hong Z, Liu J, Lin Y, Rodríguez-Patón A, Zou Q, Zeng X. Computational methods for identifying the critical nodes in biological networks. Brief Bioinform 2019; 21:486-497. [DOI: 10.1093/bib/bbz011] [Citation(s) in RCA: 46] [Impact Index Per Article: 9.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/25/2018] [Revised: 12/03/2018] [Accepted: 01/11/2019] [Indexed: 12/28/2022] Open
Abstract
Abstract
A biological network is complex. A group of critical nodes determines the quality and state of such a network. Increasing studies have shown that diseases and biological networks are closely and mutually related and that certain diseases are often caused by errors occurring in certain nodes in biological networks. Thus, studying biological networks and identifying critical nodes can help determine the key targets in treating diseases. The problem is how to find the critical nodes in a network efficiently and with low cost. Existing experimental methods in identifying critical nodes generally require much time, manpower and money. Accordingly, many scientists are attempting to solve this problem by researching efficient and low-cost computing methods. To facilitate calculations, biological networks are often modeled as several common networks. In this review, we classify biological networks according to the network types used by several kinds of common computational methods and introduce the computational methods used by each type of network.
Collapse
Affiliation(s)
- Xiangrong Liu
- Department of Computer Science, Xiamen University, China
| | - Zengyan Hong
- Department of Computer Science, Xiamen University, China
| | - Juan Liu
- Department of Computer Science, Xiamen University, China
| | - Yuan Lin
- ITOP Section, DNB Bank ASA, Solheimsgaten, Bergen, Norway
| | - Alfonso Rodríguez-Patón
- Universidad Politécnica de Madrid (UPM) Campus Montegancedo s/n, Boadilla del Monte, Madrid, Spain
| | - Quan Zou
- Department of Computer Science, Xiamen University, China
- Insitute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China, China
- School of Computer Science and Technology, Tianjin University, Tianjin, China
| | | |
Collapse
|