Search

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. [ABSTRACT FROM AUTHOR]

Securing complete control of complex systems comprised of tens of thousands of interconnected nodes holds immense significance across various fields, spanning from cell biology and brain science to human-engineered systems. However, depending on specific functional requirements, it can be more practical and efficient to focus on a pre-defined subset of nodes for control, a concept known as target control. While some methods have been proposed to find the smallest driver node set for target control, they either rely on heuristic approaches based on k-walk theory, lacking a guarantee of optimal solutions, or they are overly complex and challenging to implement in real-world networks. To address this challenge, we introduce a simple and elegant algorithm, inspired by the path cover problem, which efficiently identifies the nodes required to control a target node set within polynomial time. To practically apply the algorithm in real-world systems, we have selected several networks in which a specific set of nodes with functional significance can be designated as a target control set. The analysed systems include the complete connectome of the nematode worm C. elegans, the recently disclosed connectome of the Drosophila larval brain, as well as dozens of genome-wide metabolic networks spanning major plant lineages. The target control analysis shed light on distinctions between neural systems in nematode worms and larval brain insects, particularly concerning the number of nodes necessary to regulate specific functional systems. Furthermore, our analysis uncovers evolutionary trends within plant lineages, notably when examining the proportion of nodes required to control functional pathways. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Intelligent systems are applied in a wide range of areas, and computer-aided drug design is a highly important one. One major approach to drug design is the inverse QSAR/QSPR (quantitative structure-activity and structure-property relationship), for which a method that uses both artificial neural networks (ANN) and mixed integer linear programming (MILP) has been proposed recently. This method consists of two phases: a forward prediction phase, and an inverse, inference phase. In the prediction phase, a feature function f over chemical compounds is defined, whereby a chemical compound G is represented as a vector f(G) of descriptors. Following, for a given chemical property , using a dataset of chemical compounds with known values for property , a regressive prediction function is computed by an ANN. It is desired that takes a value that is close to the true value of property for the compound G for many of the compounds in the dataset. In the inference phase, one starts with a target value of the chemical property , and then a chemical structure such that is within a certain tolerance level of is constructed from the solution to a specially formulated MILP. This method has been used for the case of inferring acyclic chemical compounds. With this paper, we propose a new concept on acyclic chemical graphs, called a skeleton tree, and based on it develop a new MILP formulation for inferring acyclic chemical compounds. Our computational experiments indicate that our newly proposed method significantly outperforms the existing method when the diameter of graphs is up to 8. In a particular example where we inferred acyclic chemical compounds with 38 non-hydrogen atoms from the set {C, O, S} times faster. [ABSTRACT FROM AUTHOR]

Protein kinase-inhibitor interactions are key to the phosphorylation of proteins involved in cell proliferation, differentiation, and apoptosis, which shows the importance of binding mechanism research and kinase inhibitor design. In this study, a novel machine learning module (i.e., the WL Box) was designed and assembled to the Prediction of Interaction Sites of Protein Kinase Inhibitors (PISPKI) model, which is a graph convolutional neural network (GCN) to predict the interaction sites of protein kinase inhibitors. The WL Box is a novel module based on the well-known Weisfeiler-Lehman algorithm, which assembles multiple switch weights to effectively compute graph features. The PISPKI model was evaluated by testing with shuffled datasets and ablation analysis using 11 kinase classes. The accuracy of the PISPKI model with the shuffled datasets varied from 83 to 86%, demonstrating superior performance compared to two baseline models. The effectiveness of the model was confirmed by testing with shuffled datasets. Furthermore, the performance of each component of the model was analyzed via the ablation study, which demonstrated that the WL Box module was critical. The code is available at https://github.com/feiqiwang/PISPKI. [ABSTRACT FROM AUTHOR]

The widely used Maximum Matching (MM) method identifies the minimum driver nodes set to control biological and technological systems. Nevertheless, it is assumed in the MM approach that one driver node can send control signal to multiple target nodes, which might not be appropriate in certain complex networks. A recent work introduced a constraint that one driver node can control one target node, and proposed a method to identify the minimum target nodes set under such a constraint. We refer such target nodes to driven nodes. However, the driven nodes may not be uniquely determined. Here, we develop a novel algorithm to classify driven nodes in control categories. Our computational analysis on a large number of biological networks indicates that the number of driven nodes is considerably larger than the number of driver nodes, not only in all examined complete plant metabolic networks but also in several key human pathways, which firstly demonstrate the importance of use of driven nodes in analysis of real-world networks. [ABSTRACT FROM AUTHOR]

Background: The enumeration of chemical graphs (molecular graphs) satisfying given constraints is one of the fundamental problems in chemoinformatics and bioinformatics because it leads to a variety of useful applications including structure determination and development of novel chemical compounds. Results: We consider the problem of enumerating chemical graphs with monocyclic structure (a graph structure that contains exactly one cycle) from a given set of feature vectors, where a feature vector represents the frequency of the prescribed paths in a chemical compound to be constructed and the set is specified by a pair of upper and lower feature vectors. To enumerate all tree-like (acyclic) chemical graphs from a given set of feature vectors, Shimizu et al. and Suzuki et al. proposed efficient branch-and-bound algorithms based on a fast tree enumeration algorithm. In this study, we devise a novel method for extending these algorithms to enumeration of chemical graphs with monocyclic structure by designing a fast algorithm for testing uniqueness. The results of computational experiments reveal that the computational efficiency of the new algorithm is as good as those for enumeration of tree-like chemical compounds. Conclusions: We succeed in expanding the class of chemical graphs that are able to be enumerated efficiently. [ABSTRACT FROM AUTHOR]

Nonredundant and exhaustive generation of stereoisomers of a chemical compound with a specified constitution is one of the important tools for molecular structure elucidation and molecular design. In this paper, we deal with chemical compounds composed of carbon, hydrogen, oxygen and nitrogen atoms whose graphical structures are tree-like graphs because these compounds are most fundamental, and consider stereoisomers that can be generated by asymmetric carbon atoms and double bonds between two adjacent carbon atoms. Based on dynamic programming, we propose an algorithm of generating all stereoisomers without duplication. We treat a given tree-like graph as a tree rooted at its structural center. Our algorithm first computes recursively the numbers of stereoisomers of the subgraphs induced by the descendants of each vertex, and then constructs each stereoisomer by backtracking the process of computing the numbers of stereoisomers. Our algorithm correctly counts the number of stereoisomers in O( n) time and space, and correctly enumerates all the stereoisomers in O( n) space and in O( n) time per stereoisomer, where n is the number of atoms in a given structure. The source code of the program implementing the proposed algorithm is freely available for academic use upon request. [ABSTRACT FROM AUTHOR]

Singleton attractor (also called fixed point) detection is known to be NP-hard even for AND/OR Boolean networks (AND/OR BNs in short, i.e., BNs consisting of AND/OR nodes), where BN is a mathematical model of genetic networks and singleton attractors correspond to steady states. In our recent paper, we developed an O(1.787 n) time algorithm for detecting a singleton attractor of a given AND/OR BN where n is the number of nodes. In this paper, we present an O(1.757 n) time algorithm with which we succeeded in improving the above algorithm. We also show that this problem can be solved in $$2^{O(({\rm log} \, n)\sqrt{n})}$$ time, which is less than O((1 + ∈) n) for any positive constant ∈, when a BN is planar. [ABSTRACT FROM AUTHOR]

A Boolean network (BN) is a mathematical model of genetic networks. We propose several algorithms for control of singleton attractors in BN. We theoretically estimate the average-case time complexities of the proposed algorithms, and confirm them by computer experiments. The results suggest the importance of gene ordering. Especially, setting internal nodes ahead yields shorter computational time than setting external nodes ahead in various types of algorithms. We also present a heuristic algorithm which does not look for the optimal solution but for the solution whose computational time is shorter than that of the exact algorithms. [ABSTRACT FROM AUTHOR]

A Boolean network is a model used to study the interactions between different genes in genetic regulatory networks. In this paper, we present several algorithms using gene ordering and feedback vertex sets to identify singleton attractors and small attractors in Boolean networks. We analyze the average case time complexities of some of the proposed algorithms. For instance, it is shown that the outdegree-based ordering algorithm for finding singleton attractors works in O(1.19n) time for K = 2, which is much faster than the naive O(2n) time algorithm, where n is the number of genes and K is the maximum indegree. We performed extensive computational experiments on these algorithms, which resulted in good agreement with theoretical results. In contrast, we give a simple and complete proof for showing that finding an attractor with the shortest period is NP-hard. [ABSTRACT FROM AUTHOR]

For a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem and the construction of a parse tree for a stochastic context-free language, O(n3) time algorithms were known. For both problems, this paper shows slightly improved O(n3(log log n)1/2/(log n)1/2) time exact algorithms, which are obtained by combining Valiant's algorithm for context-free recognition with fast funny matrix multiplication. Moreover, this paper shows an O(n2.776 + (1/∈)O(1)) time approximation algorithm for the former problem and an O(n2.976 log n + (1/∈)O(1)) time approximation algorithm for the latter problem, each of which has a guaranteed approximation ratio 1 − ∈ for any positive constant ∈, where the absolute value of the logarithm of the probability is considered as an objective value in the latter problem. The former algorithm is obtained from a non-trivial modification of the well-known O(n3) time dynamic programming algorithm, and the latter algorithm is obtained by combining Valiant's algorithm with approximate funny matrix multiplication. Several related results are shown too. [ABSTRACT FROM AUTHOR]

This paper proposes a kind of probably approximately correct (PAC) learning framework for inferring a set of functional dependencies (FDs) from example tuples. A simple algorithm is considered that outputs a set of all FDs which hold in a set of example tuples. Let r be a relation (a set of tuples). We define the error for a set of FDs FS as the minimum Σ; where ν (ν ⊂ r) is a set such that FS holds in r − ν, and P(t) denotes the probability that tuple t is picked from r. Our attention is focused on the sample complexity, and we show that the number of example tuples required to infer a set of FDs whose error does not exceed ω with probability at least 1 − δ under an arbitrary probability distribution is $$O((\sqrt {\ln (1/\delta )} /\varepsilon )\sqrt {\left| r \right|} )$$ . [ABSTRACT FROM AUTHOR]

Recent research has shown that many types of cancers take control of specific metabolic processes. We compiled metabolic networks corresponding to four healthy and cancer tissues, and analysed the healthy–cancer transition from the metabolic flux change perspective. We used a Probabilistic Minimum Dominating Set (PMDS) model, which identifies a minimum set of nodes that act as driver nodes and control the entire network. The combination of control theory with flux correlation analysis shows that flux correlations substantially increase in cancer states of breast, kidney and urothelial tissues, but not in lung. No change in the network topology between healthy and cancer networks was observed, but PMDS analysis shows that cancer states require fewer controllers than their corresponding healthy states. These results indicate that cancer metabolism is characterised by more streamlined flux distributions, which may be focused towards a reduced set of objectives and controlled by fewer regulatory elements. Metabolic rewiring is a feature of many cancers. Here, the authors combine control theory and flux correlation analysis to study the transition of healthy metabolic networks to cancer states, and find that cancer metabolism is characterized by more streamlined flux distributions. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

It is difficult to control multilayer networks in situations with real-world complexity. Here, we first define the multilayer control problem in terms of the minimum dominating set (MDS) controllability framework and mathematically demonstrate that simple formulas can be used to estimate the size of the minimum dominating set in multilayer (MDSM) complex networks. Second, we develop a new algorithm that efficiently identifies the MDSM in up to 6 layers, with several thousand nodes in each layer network. Interestingly, the findings reveal that the MDSM size for similar networks does not significantly differ from that required to control a single network. This result opens future directions for controlling, for example, multiple species by identifying a common set of enzymes or proteins for drug targeting. We apply our methods to 70 genome-wide metabolic networks across major plant lineages, unveiling some relationships between controllability in multilayer networks and metabolic functions at the genome scale. [ABSTRACT FROM AUTHOR]

Bacteria translocate effector molecules to host cells through highly evolved secretion systems. By definition, the function of these effector proteins is to manipulate host cell biology and the sequence, structural and functional annotations of these effector proteins will provide a better understanding of how bacterial secretion systems promote bacterial survival and virulence. Here we developed a knowledgebase, termed SecretEPDB (Bacterial Secreted Effector Protein DataBase), for effector proteins of type III secretion system (T3SS), type IV secretion system (T4SS) and type VI secretion system (T6SS). SecretEPDB provides enriched annotations of the aforementioned three classes of effector proteins by manually extracting and integrating structural and functional information from currently available databases and the literature. The database is conservative and strictly curated to ensure that every effector protein entry is supported by experimental evidence that demonstrates it is secreted by a T3SS, T4SS or T6SS. The annotations of effector proteins documented in SecretEPDB are provided in terms of protein characteristics, protein function, protein secondary structure, Pfam domains, metabolic pathway and evolutionary details. It is our hope that this integrated knowledgebase will serve as a useful resource for biological investigation and the generation of new hypotheses for research efforts aimed at bacterial secretion systems. [ABSTRACT FROM AUTHOR]

The article emphasizes the importance of developing genetic regulatory networks to systems biology. It stresses the need to process the signals produced by genome in order to distinguish their regulatory effects and their relationship to changes at the genotypic and phenotypic levels. It stresses that understanding gene network entails the study of its dynamics and long-term behavior. In the authors' opinion, the genomic signal processing will play a significant role in the advancement of systems medicine.