A practically efficient algorithm for identifying critical control proteins in directed probabilistic biological networks.

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.