Hypergraphs and cellular networks

Modeling Cell Communication with Time-Dependent Signaling Hypergraphs

Signaling pathways describe a group of molecules in a cell that collaborate to control one or more cell functions, such as cell division or cell death. The pathways communicate by sending signals between molecules, and this process is repeated until the terminal molecule is activated and the cell function is executed. Signaling pathways are often represented as directed graphs, which does not provide enough information when modeling cell functions and reactions. Recently, directed hypergraphs have been proposed to more accurately represent reactions such as protein activation and interaction. To further improve the representation of signaling pathways, time dependency must be considered to improve the representation of cell signaling at any given time. In this paper, the importance of time dependency in modeling signaling pathways is presented. An algorithm that finds the shortest a priori path using time-dependent hypergraphs to more robustly model signaling pathways is adopted. The shortest time-dependent hyperpaths representing signaling pathways are an improvement to the recent adoption of hypergraphs representing these pathways. The results display the improved representation of signaling pathways and motivate the adoption of time-dependent signaling hypergraphs.

Atlas: automatic modeling of regulation of bacterial gene expression and metabolism using rule-based languages

MOTIVATION

Cells are complex systems composed of hundreds of genes whose products interact to produce elaborated behaviors. To control such behaviors, cells rely on transcription factors to regulate gene expression, and gene regulatory networks (GRNs) are employed to describe and understand such behavior. However, GRNs are static models, and dynamic models are difficult to obtain due to their size, complexity, stochastic dynamics and interactions with other cell processes.

RESULTS

We developed Atlas, a Python software that converts genome graphs and gene regulatory, interaction and metabolic networks into dynamic models. The software employs these biological networks to write rule-based models for the PySB framework. The underlying method is a divide-and-conquer strategy to obtain sub-models and combine them later into an ensemble model. To exemplify the utility of Atlas, we used networks of varying size and complexity of Escherichia coli and evaluated in silico modifications, such as gene knockouts and the insertion of promoters and terminators. Moreover, the methodology could be applied to the dynamic modeling of natural and synthetic networks of any bacteria.

AVAILABILITY AND IMPLEMENTATION

Code, models and tutorials are available online (https://github.com/networkbiolab/atlas).

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

The effective graph reveals redundancy, canalization, and control pathways in biochemical regulation and signaling

The ability to map causal interactions underlying genetic control and cellular signaling has led to increasingly accurate models of the complex biochemical networks that regulate cellular function. These network models provide deep insights into the organization, dynamics, and function of biochemical systems: for example, by revealing genetic control pathways involved in disease. However, the traditional representation of biochemical networks as binary interaction graphs fails to accurately represent an important dynamical feature of these multivariate systems: some pathways propagate control signals much more effectively than do others. Such heterogeneity of interactions reflects canalization-the system is robust to dynamical interventions in redundant pathways but responsive to interventions in effective pathways. Here, we introduce the effective graph, a weighted graph that captures the nonlinear logical redundancy present in biochemical network regulation, signaling, and control. Using 78 experimentally validated models derived from systems biology, we demonstrate that 1) redundant pathways are prevalent in biological models of biochemical regulation, 2) the effective graph provides a probabilistic but precise characterization of multivariate dynamics in a causal graph form, and 3) the effective graph provides an accurate explanation of how dynamical perturbation and control signals, such as those induced by cancer drug therapies, propagate in biochemical pathways. Overall, our results indicate that the effective graph provides an enriched description of the structure and dynamics of networked multivariate causal interactions. We demonstrate that it improves explainability, prediction, and control of complex dynamical systems in general and biochemical regulation in particular.

Scarcity of scale-free topology is universal across biochemical networks

Biochemical reactions underlie the functioning of all life. Like many examples of biology or technology, the complex set of interactions among molecules within cells and ecosystems poses a challenge for quantification within simple mathematical objects. A large body of research has indicated many real-world biological and technological systems, including biochemistry, can be described by power-law relationships between the numbers of nodes and edges, often described as "scale-free". Recently, new statistical analyses have revealed true scale-free networks are rare. We provide a first application of these methods to data sampled from across two distinct levels of biological organization: individuals and ecosystems. We analyze a large ensemble of biochemical networks including networks generated from data of 785 metagenomes and 1082 genomes (sampled from the three domains of life). The results confirm no more than a few biochemical networks are any more than super-weakly scale-free. Additionally, we test the distinguishability of individual and ecosystem-level biochemical networks and show there is no sharp transition in the structure of biochemical networks across these levels of organization moving from individuals to ecosystems. This result holds across different network projections. Our results indicate that while biochemical networks are not scale-free, they nonetheless exhibit common structure across different levels of organization, independent of the projection chosen, suggestive of shared organizing principles across all biochemical networks.

Consensus on simplicial complexes: Results on stability and synchronization

We consider a nonlinear flow on simplicial complexes related to the simplicial Laplacian and show that it is a generalization of various consensus and synchronization models commonly studied on networks. In particular, our model allows us to formulate flows on simplices of any dimension so that it includes edge flows, triangle flows, etc. We show that the system can be represented as the gradient flow of an energy functional and use this to deduce the stability of various steady states of the model. Finally, we demonstrate that our model contains higher-dimensional analogs of structures seen in related network models.

Opportunities at the Interface of Network Science and Metabolic Modeling

Metabolism plays a central role in cell physiology because it provides the molecular machinery for growth. At the genome-scale, metabolism is made up of thousands of reactions interacting with one another. Untangling this complexity is key to understand how cells respond to genetic, environmental, or therapeutic perturbations. Here we discuss the roles of two complementary strategies for the analysis of genome-scale metabolic models: Flux Balance Analysis (FBA) and network science. While FBA estimates metabolic flux on the basis of an optimization principle, network approaches reveal emergent properties of the global metabolic connectivity. We highlight how the integration of both approaches promises to deliver insights on the structure and function of metabolic systems with wide-ranging implications in discovery science, precision medicine and industrial biotechnology.

A system architecture for parallel analysis of flux-balanced metabolic pathways

Elementary flux mode (EFM) analysis is a well-studied method in constraint-based modeling of metabolic networks. In EFM analysis, a network is decomposed into minimal functional pathways based on the assumption of balanced metabolic fluxes. In this paper, a system architecture is proposed that approximately models the functionality of metabolic networks. The AND/OR graph model is used to represent the metabolic network and each processing element in the system emulates the functionality of a metabolite. The system is implemented on a graphics processing unit (GPU) as the hardware platform using CUDA environment. The proposed architecture takes advantage of the inherent parallelism in the network structure in terms of both pathway and metabolite traversal. The function of each element is defined such that it can find flux-balanced pathways. Pathways in both small and large metabolic networks are applied to the proposed architecture and the results are discussed.

Coupled dynamics on hypergraphs: Master stability of steady states and synchronization

In the study of dynamical systems on networks or graphs, a key theme is how the network topology influences stability for steady states or synchronized states. Ideally, one would like to derive conditions for stability or instability that, instead of microscopic details of the individual nodes or vertices, rather make the influence of the network coupling topology visible. The master stability function is an important such tool to achieve this goal. Here, we generalize the master stability approach to hypergraphs. A hypergraph coupling structure is important as it allows us to take into account arbitrary higher-order interactions between nodes. As, for instance, in the theory of coupled map lattices, we study Laplace-type interaction structures in detail. Since the spectral theory of Laplacians on hypergraphs is richer than on graphs, we see the possibility of different dynamical phenomena. More generally, our arguments provide a blueprint for how to generalize dynamical structures and results from graphs to hypergraphs.

Covering Problems and Core Percolations on Hypergraphs

We introduce two generalizations of core percolation in graphs to hypergraphs, related to the minimum hyperedge cover problem and the minimum vertex cover problem on hypergraphs, respectively. We offer analytical solutions of these two core percolations for uncorrelated random hypergraphs whose vertex degree and hyperedge cardinality distributions are arbitrary but have nondiverging moments. We find that for several real-world hypergraphs their two cores tend to be much smaller than those of their null models, suggesting that covering problems in those real-world hypergraphs can actually be solved in polynomial time.

Structural conserved moiety splitting of a stoichiometric matrix

Characterising biochemical reaction network structure in mathematical terms enables the inference of functional biochemical consequences from network structure with existing mathematical techniques and spurs the development of new mathematics that exploits the peculiarities of biochemical network structure. The structure of a biochemical network may be specified by reaction stoichiometry, that is, the relative quantities of each molecule produced and consumed in each reaction of the network. A biochemical network may also be specified at a higher level of resolution in terms of the internal structure of each molecule and how molecular structures are transformed by each reaction in a network. The stoichiometry for a set of reactions can be compiled into a stoichiometric matrix N∈Z^m×n, where each row corresponds to a molecule and each column corresponds to a reaction. We demonstrate that a stoichiometric matrix may be split into the sum of m-rank(N) moiety transition matrices, each of which corresponds to a subnetwork accessible to a structurally identifiable conserved moiety. The existence of this moiety matrix splitting is a property that distinguishes a stoichiometric matrix from an arbitrary rectangular matrix.

Hypergraph-based connectivity measures for signaling pathway topologies

Characterizing cellular responses to different extrinsic signals is an active area of research, and curated pathway databases describe these complex signaling reactions. Here, we revisit a fundamental question in signaling pathway analysis: are two molecules “connected” in a network? This question is the first step towards understanding the potential influence of molecules in a pathway, and the answer depends on the choice of modeling framework. We examined the connectivity of Reactome signaling pathways using four different pathway representations. We find that Reactome is very well connected as a graph, moderately well connected as a compound graph or bipartite graph, and poorly connected as a hypergraph (which captures many-to-many relationships in reaction networks). We present a novel relaxation of hypergraph connectivity that iteratively increases connectivity from a node while preserving the hypergraph topology. This measure, B-relaxation distance, provides a parameterized transition between hypergraph connectivity and graph connectivity. B-relaxation distance is sensitive to the presence of small molecules that participate in many functionally unrelated reactions in the network. We also define a score that quantifies one pathway’s downstream influence on another, which can be calculated as B-relaxation distance gradually relaxes the connectivity constraint in hypergraphs. Computing this score across all pairs of 34 Reactome pathways reveals pairs of pathways with statistically significant influence. We present two such case studies, and we describe the specific reactions that contribute to the large influence score. Finally, we investigate the ability for connectivity measures to capture functional relationships among proteins, and use the evidence channels in the STRING database as a benchmark dataset. STRING interactions whose proteins are B-connected in Reactome have statistically significantly higher scores than interactions connected in the bipartite graph representation. Our method lays the groundwork for other generalizations of graph-theoretic concepts to hypergraphs in order to facilitate signaling pathway analysis.

Signaling pathways describe how cells respond to external signals through molecular interactions. As we gain a deeper understanding of these signaling reactions, it is important to understand how molecules may influence downstream responses and how pathways may affect each other. As the amount of information in signaling pathway databases continues to grow, we have the opportunity to analyze properties about pathway structure. We pose an intuitive question about signaling pathways: when are two molecules “connected” in a pathway? This answer varies dramatically based on the assumptions we make about how reactions link molecules. Here, examine four approaches for modeling the structural topology of signaling pathways, and present methods to quantify whether two molecules are “connected” in a pathway database. We find that existing approaches are either too permissive (molecules are connected to many others) or restrictive (molecules are connected to a handful of others), and we present a new measure that offers a continuum between these two extremes. We then expand our question to ask when an entire signaling pathway is “downstream” of another pathway, and show two case studies from the Reactome pathway database that uncovers pathway influence. Finally, we show that the strict notion of connectivity can capture functional relationships among proteins using an independent benchmark dataset. Our approach to quantify connectivity in pathways considers a biologically-motivated definition of connectivity, laying the foundation for more sophisticated analyses that leverage the detailed information in pathway databases.

MOOMIN - Mathematical explOration of 'Omics data on a MetabolIc Network

MOTIVATION

Analysis of differential expression of genes is often performed to understand how the metabolic activity of an organism is impacted by a perturbation. However, because the system of metabolic regulation is complex and all changes are not directly reflected in the expression levels, interpreting these data can be difficult.

RESULTS

In this work, we present a new algorithm and computational tool that uses a genome-scale metabolic reconstruction to infer metabolic changes from differential expression data. Using the framework of constraint-based analysis, our method produces a qualitative hypothesis of a change in metabolic activity. In other words, each reaction of the network is inferred to have increased, decreased, or remained unchanged in flux. In contrast to similar previous approaches, our method does not require a biological objective function and does not assign on/off activity states to genes. An implementation is provided and it is available online. We apply the method to three published datasets to show that it successfully accomplishes its two main goals: confirming or rejecting metabolic changes suggested by differentially expressed genes based on how well they fit in as parts of a coordinated metabolic change, as well as inferring changes in reactions whose genes did not undergo differential expression.

AVAILABILITY AND IMPLEMENTATION

github.com/htpusa/moomin.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Effect of Inter-layer Coupling on Multilayer Network Centrality Measures

The study of networks has been evolving because of its applications in diverse fields. Many complex systems involve multiple types of interactions and such systems are better modeled as multilayer networks.The question "which are the most (or least) important nodes in a given network?", has gained substantial attention in the network science community. The importance of a node is known as centrality and there are multiple ways to define it. Extending the centrality measure to multilayer networks is challenging since the relative contribution of intra-layer edges vs. that of inter-layer edges to multilayer centrality is not straight-forward. With the growing applications of multilayer networks, several attempts have been made to define centrality in multilayer networks in recent years. There are different ways of tuning the inter-layer couplings which may lead to different classes of centrality measures. In this article, we provide an overview of the recent works related to centrality in multilayer networks with a focus on key use cases and implications of the type of inter-layer coupling on centrality and subsequent uses of the different centrality measures. We discuss the effect of three popular interlayer coupling methods viz. diagonal coupling between adjacent layers, diagonal coupling and cross coupling. We hope the colloquial tone of this article would make it a pleasant read for understanding the theoretical as well as experimental aspects of the work.

Exploring Plant Sesquiterpene Diversity by Generating Chemical Networks

Plants produce a diverse portfolio of sesquiterpenes that are important in their response to herbivores and the interaction with other plants. Their biosynthesis from farnesyl diphosphate depends on the sesquiterpene synthases that admit different cyclizations and rearrangements to yield a blend of sesquiterpenes. Here, we investigate to what extent sesquiterpene biosynthesis metabolic pathways can be reconstructed just from the knowledge of the final product and the reaction mechanisms catalyzed by sesquiterpene synthases. We use the software package MedØlDatschgerl (MØD) to generate chemical networks and to elucidate pathways contained in them. As examples, we successfully consider the reachability of the important plant sesquiterpenes β -caryophyllene, α -humulene, and β -farnesene. We also introduce a graph database to integrate the simulation results with experimental biological evidence for the selected predicted sesquiterpenes biosynthesis.

Information Loss in Network Pharmacology

With the advent of increasing computational power and large-scale data acquisition, network analysis has become an attractive tool to study the organisation of complex systems and the interrelation of their constituent entities in various scientific domains. In many cases, relations only occur between entities of two different subsets, thereby forming a bipartite network. Often, the analysis of such bipartite networks involves the consideration of its two monopartite projections in order to focus on each entity subset individually as a means to deduce properties of the underlying original network. Although it is broadly acknowledged that this type of projection is not lossless, the inherent limitations of their interpretability are rarely discussed. In this work, we introduce two approaches for measuring the information loss associated with bipartite network projection. Application to two structurally distinct cases in network pharmacology, namely, drug-target and disease-gene bipartite networks, confirms that the major determinant of information loss is the degree of vertices omitted during the monopartite projection.

Formal structure of periodic system of elements

For more than 150 years, the structure of the periodic system of the chemical elements has intensively motivated research in different areas of chemistry and physics. However, there is still no unified picture of what a periodic system is. Herein, based on the relations of order and similarity, we report a formal mathematical structure for the periodic system, which corresponds to an ordered hypergraph. It is shown that the current periodic system of chemical elements is an instance of the general structure. The definition is used to devise a tailored periodic system of polarizability of single covalent bonds, where order relationships are quantified within subsets of similar bonds and among these classes. The generalized periodic system allows envisioning periodic systems in other disciplines of science and humanities.

Creation and analysis of biochemical constraint-based models using the COBRA Toolbox v.3.0

Constraint-based reconstruction and analysis (COBRA) provides a molecular mechanistic framework for integrative analysis of experimental molecular systems biology data and quantitative prediction of physicochemically and biochemically feasible phenotypic states. The COBRA Toolbox is a comprehensive desktop software suite of interoperable COBRA methods. It has found widespread application in biology, biomedicine, and biotechnology because its functions can be flexibly combined to implement tailored COBRA protocols for any biochemical network. This protocol is an update to the COBRA Toolbox v.1.0 and v.2.0. Version 3.0 includes new methods for quality-controlled reconstruction, modeling, topological analysis, strain and experimental design, and network visualization, as well as network integration of chemoinformatic, metabolomic, transcriptomic, proteomic, and thermochemical data. New multi-lingual code integration also enables an expansion in COBRA application scope via high-precision, high-performance, and nonlinear numerical optimization solvers for multi-scale, multi-cellular, and reaction kinetic modeling, respectively. This protocol provides an overview of all these new features and can be adapted to generate and analyze constraint-based models in a wide variety of scenarios. The COBRA Toolbox v.3.0 provides an unparalleled depth of COBRA methods.

A genome-scale metabolic network alignment method within a hypergraph-based framework using a rotational tensor-vector product

Biological network alignment aims to discover important similarities and differences and thus find a mapping between topological and/or functional components of different biological molecular networks. Then, the mapped components can be considered to correspond to both their places in the network topology and their biological attributes. Development and evolution of biological network alignment methods has been accelerated by the rapidly increasing availability of such biological networks, yielding a repertoire of tens of methods based upon graph theory. However, most biological processes, especially the metabolic reactions, are more sophisticated than simple pairwise interactions and contain three or more participating components. Such multi-lateral relations are not captured by graphs, and computational methods to overcome this limitation are currently lacking. This paper introduces hypergraphs and association hypergraphs to describe metabolic networks and their potential alignments, respectively. Within this framework, metabolic networks are aligned by identifying the maximal Z-eigenvalue of a symmetric tensor. A shifted higher-order power method was utilized to identify a solution. A rotational strategy has been introduced to accelerate the tensor-vector product by 250-fold on average and reduce the storage cost by up to 1,000-fold. The algorithm was implemented on a spark-based distributed computation cluster to significantly increase the convergence rate further by 50- to 80-fold. The parameters have been explored to understand their impact on alignment accuracy and speed. In particular, the influence of initial value selection on the stationary point has been simulated to ensure an accurate approximation of the global optimum. This framework was demonstrated by alignments among the genome-wide metabolic networks of Escherichia coli MG-1655 and Halophilic archaeon DL31. To our knowledge, this is the first genome-wide metabolic network alignment at both the metabolite level and the enzyme level. These results demonstrate that it can supply quite a few valuable insights into metabolic networks. First, this method can access the driving force of organic reactions through the chemical evolution of metabolic network. Second, this method can incorporate the chemical information of enzymes and structural changes of compounds to offer new way defining reaction class and module, such as those in KEGG. Third, as a vertex-focused treatment, this method can supply novel structural and functional annotation for ill-defined molecules. The related source code is available on request.

Human-like layout algorithms for signalling hypergraphs: outlining requirements

The use of signalling pathway hypergraphs represented as process description diagrams is steadily becoming more pervasive in the field of biology. This makes ever more evident the necessity for an effective automated layout that can replicate high-quality manually drawn diagrams. The complexity and idiosyncrasies of these diagrams, as well as the specific tasks the end users perform with them, mean that a layout must meet many requirements beyond the simple metrics used in existing automated computational approaches. In this paper we outline these requirements, examine existing ones and describe new ones. We demonstrate state-of-the-art layout techniques enhanced with novel functionalities to meet part of the requirements. For comparatively small signalling pathways our enhanced algorithm provides results close to manually drawn layouts. In addition, we suggest technical approaches that may be suited for fulfilling the identified requirements currently not covered.

Higher-order molecular organization as a source of biological function

Motivation

Molecular interactions have widely been modelled as networks. The local wiring patterns around molecules in molecular networks are linked with their biological functions. However, networks model only pairwise interactions between molecules and cannot explicitly and directly capture the higher-order molecular organization, such as protein complexes and pathways. Hence, we ask if hypergraphs (hypernetworks), that directly capture entire complexes and pathways along with protein-protein interactions (PPIs), carry additional functional information beyond what can be uncovered from networks of pairwise molecular interactions. The mathematical formalism of a hypergraph has long been known, but not often used in studying molecular networks due to the lack of sophisticated algorithms for mining the underlying biological information hidden in the wiring patterns of molecular systems modelled as hypernetworks.

Results

We propose a new, multi-scale, protein interaction hypernetwork model that utilizes hypergraphs to capture different scales of protein organization, including PPIs, protein complexes and pathways. In analogy to graphlets, we introduce hypergraphlets, small, connected, non-isomorphic, induced sub-hypergraphs of a hypergraph, to quantify the local wiring patterns of these multi-scale molecular hypergraphs and to mine them for new biological information. We apply them to model the multi-scale protein networks of bakers yeast and human and show that the higher-order molecular organization captured by these hypergraphs is strongly related to the underlying biology. Importantly, we demonstrate that our new models and data mining tools reveal different, but complementary biological information compared with classical PPI networks. We apply our hypergraphlets to successfully predict biological functions of uncharacterized proteins.

Availability and implementation

Code and data are available online at http://www0.cs.ucl.ac.uk/staff/natasa/hypergraphlets.

BRANE Clust: Cluster-Assisted Gene Regulatory Network Inference Refinement

Discovering meaningful gene interactions is crucial for the identification of novel regulatory processes in cells. Building accurately the related graphs remains challenging due to the large number of possible solutions from available data. Nonetheless, enforcing a priori on the graph structure, such as modularity, may reduce network indeterminacy issues. BRANE Clust (Biologically-Related A priori Network Enhancement with Clustering) refines gene regulatory network (GRN) inference thanks to cluster information. It works as a post-processing tool for inference methods (i.e., CLR, GENIE3). In BRANE Clust, the clustering is based on the inversion of a system of linear equations involving a graph-Laplacian matrix promoting a modular structure. Our approach is validated on DREAM4 and DREAM5 datasets with objective measures, showing significant comparative improvements. We provide additional insights on the discovery of novel regulatory or co-expressed links in the inferred Escherichia coli network evaluated using the STRING database. The comparative pertinence of clustering is discussed computationally (SIMoNe, WGCNA, X-means) and biologically (RegulonDB). BRANE Clust software is available at: http://www-syscom.univ-mlv.fr/~pirayre/Codes-GRN-BRANE-clust.html.

A two-tiered unsupervised clustering approach for drug repositioning through heterogeneous data integration

Background

Drug repositioning is the process of identifying new uses for existing drugs. Computational drug repositioning methods can reduce the time, costs and risks of drug development by automating the analysis of the relationships in pharmacology networks. Pharmacology networks are large and heterogeneous. Clustering drugs into small groups can simplify large pharmacology networks, these subgroups can also be used as a starting point for repositioning drugs. In this paper, we propose a two-tiered drug-centric unsupervised clustering approach for drug repositioning, integrating heterogeneous drug data profiles: drug-chemical, drug-disease, drug-gene, drug-protein and drug-side effect relationships.

Results

The proposed drug repositioning approach is threefold; (i) clustering drugs based on their homogeneous profiles using the Growing Self Organizing Map (GSOM); (ii) clustering drugs based on drug-drug relation matrices based on the previous step, considering three state-of-the-art graph clustering methods; and (iii) inferring drug repositioning candidates and assigning a confidence value for each identified candidate. In this paper, we compare our two-tiered clustering approach against two existing heterogeneous data integration approaches with reference to the Anatomical Therapeutic Chemical (ATC) classification, using GSOM. Our approach yields Normalized Mutual Information (NMI) and Standardized Mutual Information (SMI) of 0.66 and 36.11, respectively, while the two existing methods yield NMI of 0.60 and 0.64 and SMI of 22.26 and 33.59. Moreover, the two existing approaches failed to produce useful cluster separations when using graph clustering algorithms while our approach is able to identify useful clusters for drug repositioning. Furthermore, we provide clinical evidence for four predicted results (Chlorthalidone, Indomethacin, Metformin and Thioridazine) to support that our proposed approach can be reliably used to infer ATC code and drug repositioning.

Conclusion

The proposed two-tiered unsupervised clustering approach is suitable for drug clustering and enables heterogeneous data integration. It also enables identifying reliable repositioning drug candidates with reference to ATC therapeutic classification. The repositioning drug candidates identified consistently by multiple clustering algorithms and with high confidence have a higher possibility of being effective repositioning candidates.

Electronic supplementary material

The online version of this article (10.1186/s12859-018-2123-4) contains supplementary material, which is available to authorized users.

A graph-based approach to analyze flux-balanced pathways in metabolic networks

An elementary flux mode (EFM) is a pathway with minimum set of reactions that are functional in steady-state constrained space. Due to the high computational complexity of calculating EFMs, different approaches have been proposed to find these flux-balanced pathways. In this paper, an approach to find a subset of EFMs is proposed based on a graph data model. The given metabolic network is mapped to the graph model and decisions for reaction inclusion can be made based on metabolites and their associated reactions. This notion makes the approach more convenient to categorize the output pathways. Implications of the proposed method on metabolic networks are discussed.

A review of computational tools for design and reconstruction of metabolic pathways

Metabolic pathways reflect an organism's chemical repertoire and hence their elucidation and design have been a primary goal in metabolic engineering. Various computational methods have been developed to design novel metabolic pathways while taking into account several prerequisites such as pathway stoichiometry, thermodynamics, host compatibility, and enzyme availability. The choice of the method is often determined by the nature of the metabolites of interest and preferred host organism, along with computational complexity and availability of software tools. In this paper, we review different computational approaches used to design metabolic pathways based on the reaction network representation of the database (i.e., graph or stoichiometric matrix) and the search algorithm (i.e., graph search, flux balance analysis, or retrosynthetic search). We also put forth a systematic workflow that can be implemented in projects requiring pathway design and highlight current limitations and obstacles in computational pathway design.

Cyclic decomposition explains a photosynthetic down regulation for Chlamydomonas reinhardtii

The regulation of metabolic networks has been shown to be distributed and shared through the action of metabolic cycles. Biochemical cycles play important roles in maintaining flux and substrate availability for multiple pathways to supply cellular energy and contribute to dynamic stability. By understanding the cyclic and acyclic flows of matter through a network, we are closer to understanding how complex dynamic systems distribute flux along interconnected pathways. In this work, we have applied a cycle decomposition algorithm to a genome-scale metabolic model of Chlamydomonas reinhardtii to analyse how acetate supply affects the distribution of fluxes that sustain cellular activity. We examined the role of metabolic cycles which explain the down regulation of photosynthesis that is observed when cells are grown in the presence of acetate. Our results suggest that acetate modulates changes in global metabolism, with the pentose phosphate pathway, the Calvin-Benson cycle and mitochondrial respiration activity being affected whilst reducing photosynthesis. These results show how the decomposition of metabolic flux into cyclic and acyclic components helps to understand the impact of metabolic cycling on organismal behaviour at the genome scale.

Pathway Analysis with Signaling Hypergraphs

Signaling pathways play an important role in the cell's response to its environment. Signaling pathways are often represented as directed graphs, which are not adequate for modeling reactions such as complex assembly and dissociation, combinatorial regulation, and protein activation/inactivation. More accurate representations such as directed hypergraphs remain underutilized. In this paper, we present an extension of a directed hypergraph that we call a signaling hypergraph. We formulate a problem that asks what proteins and interactions must be involved in order to stimulate a specific response downstream of a signaling pathway. We relate this problem to computing the shortest acyclic B-hyperpath in a signaling hypergraph-an NP-hard problem-and present a mixed integer linear program to solve it. We demonstrate that the shortest hyperpaths computed in signaling hypergraphs are far more informative than shortest paths, Steiner trees, and subnetworks containing many short paths found in corresponding graph representations. Our results illustrate the potential of signaling hypergraphs as an improved representation of signaling pathways and motivate the development of novel hypergraph algorithms.

Identification of Conserved Moieties in Metabolic Networks by Graph Theoretical Analysis of Atom Transition Networks

Conserved moieties are groups of atoms that remain intact in all reactions of a metabolic network. Identification of conserved moieties gives insight into the structure and function of metabolic networks and facilitates metabolic modelling. All moiety conservation relations can be represented as nonnegative integer vectors in the left null space of the stoichiometric matrix corresponding to a biochemical network. Algorithms exist to compute such vectors based only on reaction stoichiometry but their computational complexity has limited their application to relatively small metabolic networks. Moreover, the vectors returned by existing algorithms do not, in general, represent conservation of a specific moiety with a defined atomic structure. Here, we show that identification of conserved moieties requires data on reaction atom mappings in addition to stoichiometry. We present a novel method to identify conserved moieties in metabolic networks by graph theoretical analysis of their underlying atom transition networks. Our method returns the exact group of atoms belonging to each conserved moiety as well as the corresponding vector in the left null space of the stoichiometric matrix. It can be implemented as a pipeline of polynomial time algorithms. Our implementation completes in under five minutes on a metabolic network with more than 4,000 mass balanced reactions. The scalability of the method enables extension of existing applications for moiety conservation relations to genome-scale metabolic networks. We also give examples of new applications made possible by elucidating the atomic structure of conserved moieties.

Conserved moieties are transferred between metabolites in internal reactions of a metabolic network but are not synthesised, degraded or exchanged with the environment. The total amount of a conserved moiety in the metabolic network is therefore constant over time. Metabolites that share a conserved moiety have interdependent concentrations because their total amount is constant. Identification of conserved moieties results in a concise description of all concentration dependencies in a metabolic network. The problem of identifying conserved moieties has previously been formulated in terms of the stoichiometry of metabolic reactions. Methods based on this formulation are computationally intractable for large networks. We show that reaction stoichiometry alone gives insufficient information to identify conserved moieties. By first incorporating additional data on the fate of atoms in metabolic reactions, we developed and implemented a computationally tractable algorithm to identify conserved moieties and their atomic structure.

Tailored parameter optimization methods for ordinary differential equation models with steady-state constraints

BACKGROUND

Ordinary differential equation (ODE) models are widely used to describe (bio-)chemical and biological processes. To enhance the predictive power of these models, their unknown parameters are estimated from experimental data. These experimental data are mostly collected in perturbation experiments, in which the processes are pushed out of steady state by applying a stimulus. The information that the initial condition is a steady state of the unperturbed process provides valuable information, as it restricts the dynamics of the process and thereby the parameters. However, implementing steady-state constraints in the optimization often results in convergence problems.

RESULTS

In this manuscript, we propose two new methods for solving optimization problems with steady-state constraints. The first method exploits ideas from optimization algorithms on manifolds and introduces a retraction operator, essentially reducing the dimension of the optimization problem. The second method is based on the continuous analogue of the optimization problem. This continuous analogue is an ODE whose equilibrium points are the optima of the constrained optimization problem. This equivalence enables the use of adaptive numerical methods for solving optimization problems with steady-state constraints. Both methods are tailored to the problem structure and exploit the local geometry of the steady-state manifold and its stability properties. A parameterization of the steady-state manifold is not required. The efficiency and reliability of the proposed methods is evaluated using one toy example and two applications. The first application example uses published data while the second uses a novel dataset for Raf/MEK/ERK signaling. The proposed methods demonstrated better convergence properties than state-of-the-art methods employed in systems and computational biology. Furthermore, the average computation time per converged start is significantly lower. In addition to the theoretical results, the analysis of the dataset for Raf/MEK/ERK signaling provides novel biological insights regarding the existence of feedback regulation.

CONCLUSION

Many optimization problems considered in systems and computational biology are subject to steady-state constraints. While most optimization methods have convergence problems if these steady-state constraints are highly nonlinear, the methods presented recover the convergence properties of optimizers which can exploit an analytical expression for the parameter-dependent steady state. This renders them an excellent alternative to methods which are currently employed in systems and computational biology.

VisualGraphX: interactive graph visualization within Galaxy

MOTIVATION

We developed VisualGraphX, a web-based, interactive visualization tool for large-scale graphs. Current graph visualization tools that follow the rich-internet paradigm lack an interactive and scalable visualization of graph-based data. VisualGraphX aims to provide a universal graph visualization tool that empowers the users to efficiently explore the data for themselves at a large scale. It is available as a visualization plugin for the Galaxy platform, such that VisualGraphX can be integrated into custom analysis pipelines.

AVAILABILITY AND IMPLEMENTATION

VisualGraphX has been released as a visualization plugin for the Galaxy platform under AFL 3.0 and is available with instructions and application data at http://gitlab.com/comptrans/VisualGraphX/ CONTACT: bjoern.voss@ibvt.uni-stuttgart.de.

Complexity and robustness in hypernetwork models of metabolism

Metabolic reaction data is commonly modelled using a complex network approach, whereby nodes represent the chemical species present within the organism of interest, and connections are formed between those nodes participating in the same chemical reaction. Unfortunately, such an approach provides an inadequate description of the metabolic process in general, as a typical chemical reaction will involve more than two nodes, thus risking oversimplification of the system of interest in a potentially significant way. In this paper, we employ a complex hypernetwork formalism to investigate the robustness of bacterial metabolic hypernetworks by extending the concept of a percolation process to hypernetworks. Importantly, this provides a novel method for determining the robustness of these systems and thus for quantifying their resilience to random attacks/errors. Moreover, we performed a site percolation analysis on a large cohort of bacterial metabolic networks and found that hypernetworks that evolved in more variable environments displayed increased levels of robustness and topological complexity.

Logical Modeling and Dynamical Analysis of Cellular Networks

The logical (or logic) formalism is increasingly used to model regulatory and signaling networks. Complementing these applications, several groups contributed various methods and tools to support the definition and analysis of logical models. After an introduction to the logical modeling framework and to several of its variants, we review here a number of recent methodological advances to ease the analysis of large and intricate networks. In particular, we survey approaches to determine model attractors and their reachability properties, to assess the dynamical impact of variations of external signals, and to consistently reduce large models. To illustrate these developments, we further consider several published logical models for two important biological processes, namely the differentiation of T helper cells and the control of mammalian cell cycle.

SIS Epidemic Propagation on Hypergraphs

Mathematical modelling of epidemic propagation on networks is extended to hypergraphs in order to account for both the community structure and the nonlinear dependence of the infection pressure on the number of infected neighbours. The exact master equations of the propagation process are derived for an arbitrary hypergraph given by its incidence matrix. Based on these, moment closure approximation and mean-field models are introduced and compared to individual-based stochastic simulations. The simulation algorithm, developed for networks, is extended to hypergraphs. The effects of hypergraph structure and the model parameters are investigated via individual-based simulation results.

Computational methods to identify metabolic sub-networks based on metabolomic profiles

Untargeted metabolomics makes it possible to identify compounds that undergo significant changes in concentration in different experimental conditions. The resulting metabolomic profile characterizes the perturbation concerned, but does not explain the underlying biochemical mechanisms. Bioinformatics methods make it possible to interpret results in light of the whole metabolism. This knowledge is modelled into a network, which can be mined using algorithms that originate in graph theory. These algorithms can extract sub-networks related to the compounds identified. Several attempts have been made to adapt them to obtain more biologically meaningful results. However, there is still no consensus on this kind of analysis of metabolic networks. This review presents the main graph approaches used to interpret metabolomic data using metabolic networks. Their advantages and drawbacks are discussed, and the impacts of their parameters are emphasized. We also provide some guidelines for relevant sub-network extraction and also suggest a range of applications for most methods.

Correlation-Based Network Analysis of Metabolite and Enzyme Profiles Reveals a Role of Citrate Biosynthesis in Modulating N and C Metabolism in Zea mays

To investigate the natural variability of leaf metabolism and enzymatic activity in a maize inbred population, statistical and network analyses were employed on metabolite and enzyme profiles. The test of coefficient of variation showed that sugars and amino acids displayed opposite trends in their variance within the population, consistently with their related enzymes. The overall higher CV values for metabolites as compared to the tested enzymes are indicative for their greater phenotypic plasticity. H(2) tests revealed galactinol (1) and asparagine (0.91) as the highest scorers among metabolites and nitrate reductase (0.73), NAD-glutamate dehydrogenase (0.52), and phosphoglucomutase (0.51) among enzymes. The overall low H(2) scores for metabolites and enzymes are suggestive for a great environmental impact or gene-environment interaction. Correlation-based network generation followed by community detection analysis, partitioned the network into three main communities and one dyad, (i) reflecting the different levels of phenotypic plasticity of the two molecular classes as observed for the CV values and (ii) highlighting the concerted changes between classes of chemically related metabolites. Community 1 is composed mainly of enzymes and specialized metabolites, community 2' is enriched in N-containing compounds and phosphorylated-intermediates. The third community contains mainly organic acids and sugars. Cross-community linkages are supported by aspartate, by the photorespiration amino acids glycine and serine, by the metabolically related GABA and putrescine, and by citrate. The latter displayed the strongest node-betweenness value (185.25) of all nodes highlighting its fundamental structural role in the connectivity of the network by linking between different communities and to the also strongly connected enzyme aldolase.

Rational design of efficient modular cells

The modular cell design principle is formulated to devise modular (chassis) cells. These cells can be assembled with exchangeable production modules in a plug-and-play fashion to build microbial cell factories for efficient combinatorial biosynthesis of novel molecules, requiring minimal iterative strain optimization steps. A modular cell is designed to be auxotrophic, containing core metabolic pathways that are necessary but insufficient to support cell growth and maintenance. To be functional, it must tightly couple with an exchangeable production module containing auxiliary metabolic pathways that not only complement cell growth but also enhance production of targeted molecules. We developed a MODCELL (modular cell) framework based on metabolic pathway analysis to implement the modular cell design principle. MODCELL identifies genetic modifications and requirements to construct modular cell candidates and their associated exchangeable production modules. By defining the degree of similarity and coupling metrics, MODCELL can evaluate which exchangeable production module(s) can be tightly coupled with a modular cell candidate. We first demonstrated how MODCELL works in a step-by-step manner for example metabolic networks, and then applied it to design modular Escherichia coli cells for efficient combinatorial biosynthesis of five alcohols (ethanol, propanol, isopropanol, butanol and isobutanol) and five butyrate esters (ethyl butyrate, propyl butyrate, isopropyl butyrate, butyl butyrate and isobutyl butyrate) from pentose sugars (arabinose and xylose) and hexose sugars (glucose, mannose, and galactose) under anaerobic conditions. We identified three modular cells, MODCELL1, MODCELL2 and MODCELL3, that can couple well with Group 1 of modules (ethanol, isobutanol, butanol, ethyl butyrate, isobutyl butyrate, butyl butyrate), Group 2 (isopropanol, isopropyl butyrate), and Group 3 (propanol, isopropanol), respectively. We validated the design of MODCELL1 for anaerobic production of ethanol, butanol, and ethyl butyrate using experimental data available in literature.

TENET: topological feature-based target characterization in signalling networks

MOTIVATION

Target characterization for a biochemical network is a heuristic evaluation process that produces a characterization model that may aid in predicting the suitability of each molecule for drug targeting. These approaches are typically used in drug research to identify novel potential targets using insights from known targets. Traditional approaches that characterize targets based on their molecular characteristics and biological function require extensive experimental study of each protein and are infeasible for evaluating larger networks with poorly understood proteins. Moreover, they fail to exploit network connectivity information which is now available from systems biology methods. Adopting a network-based approach by characterizing targets using network features provides greater insights that complement these traditional techniques. To this end, we present Tenet (Target charactErization using NEtwork Topology), a network-based approach that characterizes known targets in signalling networks using topological features.

RESULTS

Tenet first computes a set of topological features and then leverages a support vector machine-based approach to identify predictive topological features that characterizes known targets. A characterization model is generated and it specifies which topological features are important for discriminating the targets and how these features should be combined to quantify the likelihood of a node being a target. We empirically study the performance of Tenet from a wide variety of aspects, using several signalling networks from BioModels with real-world curated outcomes. Results demonstrate its effectiveness and superiority in comparison to state-of-the-art approaches.

AVAILABILITY AND IMPLEMENTATION

Our software is available freely for non-commercial purposes from: https://sites.google.com/site/cosbyntu/softwares/tenet

CONTACT

hechua@ntu.edu.sg or assourav@ntu.edu.sg

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Xtalk: a path-based approach for identifying crosstalk between signaling pathways

MOTIVATION

Cells communicate with their environment via signal transduction pathways. On occasion, the activation of one pathway can produce an effect downstream of another pathway, a phenomenon known as crosstalk. Existing computational methods to discover such pathway pairs rely on simple overlap statistics.

RESULTS

We present Xtalk, a path-based approach for identifying pairs of pathways that may crosstalk. Xtalk computes the statistical significance of the average length of multiple short paths that connect receptors in one pathway to the transcription factors in another. By design, Xtalk reports the precise interactions and mechanisms that support the identified crosstalk. We applied Xtalk to signaling pathways in the KEGG and NCI-PID databases. We manually curated a gold standard set of 132 crosstalking pathway pairs and a set of 140 pairs that did not crosstalk, for which Xtalk achieved an area under the receiver operator characteristic curve of 0.65, a 12% improvement over the closest competing approach. The area under the receiver operator characteristic curve varied with the pathway, suggesting that crosstalk should be evaluated on a pathway-by-pathway level. We also analyzed an extended set of 658 pathway pairs in KEGG and to a set of more than 7000 pathway pairs in NCI-PID. For the top-ranking pairs, we found substantial support in the literature (81% for KEGG and 78% for NCI-PID). We provide examples of networks computed by Xtalk that accurately recovered known mechanisms of crosstalk.

AVAILABILITY AND IMPLEMENTATION

The XTALK software is available at http://bioinformatics.cs.vt.edu/~murali/software. Crosstalk networks are available at http://graphspace.org/graphs?tags=2015-bioinformatics-xtalk.

CONTACT

ategge@vt.edu, murali@cs.vt.edu

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Biological data analysis as an information theory problem: multivariable dependence measures and the shadows algorithm

Information theory is valuable in multiple-variable analysis for being model-free and nonparametric, and for the modest sensitivity to undersampling. We previously introduced a general approach to finding multiple dependencies that provides accurate measures of levels of dependency for subsets of variables in a data set, which is significantly nonzero only if the subset of variables is collectively dependent. This is useful, however, only if we can avoid a combinatorial explosion of calculations for increasing numbers of variables.

 The proposed dependence measure for a subset of variables,τ, differential interaction information, Δ(τ), has the property that for subsets ofτ some of the factors of Δ(τ) are significantly nonzero, when the full dependence includes more variables. We use this property to suppress the combinatorial explosion by following the “shadows” of multivariable dependency on smaller subsets. Rather than calculating the marginal entropies of all subsets at each degree level, we need to consider only calculations for subsets of variables with appropriate “shadows.” The number of calculations for n variables at a degree level of d grows therefore, at a much smaller rate than the binomial coefficient (n, d), but depends on the parameters of the “shadows” calculation. This approach, avoiding a combinatorial explosion, enables the use of our multivariable measures on very large data sets. We demonstrate this method on simulated data sets, and characterize the effects of noise and sample numbers. In addition, we analyze a data set of a few thousand mutant yeast strains interacting with a few thousand chemical compounds.

Differential metabolic and coexpression networks of plant metabolism

Recent analyses have demonstrated that plant metabolic networks do not differ in their structural properties and that genes involved in basic metabolic processes show smaller coexpression than genes involved in specialized metabolism. By contrast, our analysis reveals differences in the structure of plant metabolic networks and patterns of coexpression for genes in (non)specialized metabolism. Here we caution that conclusions concerning the organization of plant metabolism based on network-driven analyses strongly depend on the computational approaches used.

Distance closures on complex networks

To expand the toolbox available to network science, we study the isomorphism between distance and Fuzzy (proximity or strength) graphs. Distinct transitive closures in Fuzzy graphs lead to closures of their isomorphic distance graphs with widely different structural properties. For instance, the All Pairs Shortest Paths (APSP) problem, based on the Dijkstra algorithm, is equivalent to a metric closure, which is only one of the possible ways to calculate shortest paths in weighted graphs. We show that different closures lead to different distortions of the original topology of weighted graphs. Therefore, complex network analyses that depend on the calculation of shortest paths on weighted graphs should take into account the closure choice and associated topological distortion. We characterize the isomorphism using the max-min and Dombi disjunction/conjunction pairs. This allows us to: (1) study alternative distance closures, such as those based on diffusion, metric, and ultra-metric distances; (2) identify the operators closest to the metric closure of distance graphs (the APSP), but which are logically consistent; and (3) propose a simple method to compute alternative path length measures and corresponding distance closures using existing algorithms for the APSP. In particular, we show that a specific diffusion distance is promising for community detection in complex networks, and is based on desirable axioms for logical inference or approximate reasoning on networks; it also provides a simple algebraic means to compute diffusion processes on networks. Based on these results, we argue that choosing different distance closures can lead to different conclusions about indirect associations on network data, as well as the structure of complex networks, and are thus important to consider.

Using bioconductor package BiGGR for metabolic flux estimation based on gene expression changes in brain

Predicting the distribution of metabolic fluxes in biochemical networks is of major interest in systems biology. Several databases provide metabolic reconstructions for different organisms. Software to analyze flux distributions exists, among others for the proprietary MATLAB environment. Given the large user community for the R computing environment, a simple implementation of flux analysis in R appears desirable and will facilitate easy interaction with computational tools to handle gene expression data. We extended the R software package BiGGR, an implementation of metabolic flux analysis in R. BiGGR makes use of public metabolic reconstruction databases, and contains the BiGG database and the reconstruction of human metabolism Recon2 as Systems Biology Markup Language (SBML) objects. Models can be assembled by querying the databases for pathways, genes or reactions of interest. Fluxes can then be estimated by maximization or minimization of an objective function using linear inverse modeling algorithms. Furthermore, BiGGR provides functionality to quantify the uncertainty in flux estimates by sampling the constrained multidimensional flux space. As a result, ensembles of possible flux configurations are constructed that agree with measured data within precision limits. BiGGR also features automatic visualization of selected parts of metabolic networks using hypergraphs, with hyperedge widths proportional to estimated flux values. BiGGR supports import and export of models encoded in SBML and is therefore interoperable with different modeling and analysis tools. As an application example, we calculated the flux distribution in healthy human brain using a model of central carbon metabolism. We introduce a new algorithm termed Least-squares with equalities and inequalities Flux Balance Analysis (Lsei-FBA) to predict flux changes from gene expression changes, for instance during disease. Our estimates of brain metabolic flux pattern with Lsei-FBA for Alzheimer’s disease agree with independent measurements of cerebral metabolism in patients. This second version of BiGGR is available from Bioconductor.