Signaling hypergraphs

A Causal Regulation Modeling Algorithm for Temporal Events with Application to Escherichia coli's Aerobic to Anaerobic Transition

Time-series experiments are crucial for understanding the transient and dynamic nature of biological phenomena. These experiments, leveraging advanced classification and clustering algorithms, allow for a deep dive into the cellular processes. However, while these approaches effectively identify patterns and trends within data, they often need to improve in elucidating the causal mechanisms behind these changes. Building on this foundation, our study introduces a novel algorithm for temporal causal signaling modeling, integrating established knowledge networks with sequential gene expression data to elucidate signal transduction pathways over time. Focusing on Escherichia coli's (E. coli) aerobic to anaerobic transition (AAT), this research marks a significant leap in understanding the organism's metabolic shifts. By applying our algorithm to a comprehensive E. coli regulatory network and a time-series microarray dataset, we constructed the cross-time point core signaling and regulatory processes of E. coli's AAT. Through gene expression analysis, we validated the primary regulatory interactions governing this process. We identified a novel regulatory scheme wherein environmentally responsive genes, soxR and oxyR, activate fur, modulating the nitrogen metabolism regulators fnr and nac. This regulatory cascade controls the stress regulators ompR and lrhA, ultimately affecting the cell motility gene flhD, unveiling a novel regulatory axis that elucidates the complex regulatory dynamics during the AAT process. Our approach, merging empirical data with prior knowledge, represents a significant advance in modeling cellular signaling processes, offering a deeper understanding of microbial physiology and its applications in biotechnology.

Shortest Hyperpaths in Directed Hypergraphs for Reaction Pathway Inference

Signaling and metabolic pathways, which consist of chains of reactions that produce target molecules from source compounds, are cornerstones of cellular biology. Properly modeling the reaction networks that represent such pathways requires directed hypergraphs, where each molecule or compound maps to a vertex, and each reaction maps to a hyperedge directed from its set of input reactants to its set of output products. Inferring the most likely series of reactions that produces a given set of targets from a given set of sources, where for each reaction its reactants are produced by prior reactions in the series, corresponds to finding a shortest hyperpath in a directed hypergraph, which is NP-complete. We give the first exact algorithm for general shortest hyperpaths that can find provably optimal solutions for large, real-world, reaction networks. In particular, we derive a novel graph-theoretic characterization of hyperpaths, which we leverage in a new integer linear programming formulation of shortest hyperpaths that for the first time handles cycles, and develop a cutting-plane algorithm that can solve this integer linear program to optimality in practice. Through comprehensive experiments over all of the thousands of instances from the standard Reactome and NCI-PID reaction databases, we demonstrate that our cutting-plane algorithm quickly finds an optimal hyperpath-inferring the most likely pathway-with a median running time of under 10 seconds, and a maximum time of less than 30 minutes, even on instances with thousands of reactions. We also explore for the first time how well hyperpaths infer true pathways, and show that shortest hyperpaths accurately recover known pathways, typically with very high precision and recall. Source code implementing our cutting-plane algorithm for shortest hyperpaths is available free for research use in a new tool called Mmunin.

First-order transition to oscillation death in coupled oscillators with higher-order interactions

We investigate the dynamical evolution of Stuart-Landau oscillators globally coupled through conjugate or dissimilar variables on simplicial complexes. We report a first-order explosive phase transition from an oscillatory state to oscillation death, with higher-order (2-simplex triadic) interactions, as opposed to the second-order transition with only pairwise (1-simplex) interactions. Moreover, the system displays four distinct homogeneous steady states in the presence of triadic interactions, in contrast to the two homogeneous steady states observed with dyadic interactions. We calculate the backward transition point analytically, confirming the numerical results and providing the origin of the dynamical states in the transition region. The results are robust against the application of noise. The study will be useful in understanding complex systems, such as ecological and epidemiological, having higher-order interactions and coupling through conjugate variables.

Hypergraph geometry reflects higher-order dynamics in protein interaction networks

Protein interactions form a complex dynamic molecular system that shapes cell phenotype and function; in this regard, network analysis is a powerful tool for studying the dynamics of cellular processes. Current models of protein interaction networks are limited in that the standard graph model can only represent pairwise relationships. Higher-order interactions are well-characterized in biology, including protein complex formation and feedback or feedforward loops. These higher-order relationships are better represented by a hypergraph as a generalized network model. Here, we present an approach to analyzing dynamic gene expression data using a hypergraph model and quantify network heterogeneity via Forman-Ricci curvature. We observe, on a global level, increased network curvature in pluripotent stem cells and cancer cells. Further, we use local curvature to conduct pathway analysis in a melanoma dataset, finding increased curvature in several oncogenic pathways and decreased curvature in tumor suppressor pathways. We compare this approach to a graph-based model and a differential gene expression approach.

Heuristic shortest hyperpaths in cell signaling hypergraphs

BACKGROUND

Cell signaling pathways, which are a series of reactions that start at receptors and end at transcription factors, are basic to systems biology. Properly modeling the reactions in such pathways requires directed hypergraphs, where an edge is now directed between two sets of vertices. Inferring a pathway by the most parsimonious series of reactions corresponds to finding a shortest hyperpath in a directed hypergraph, which is NP-complete. The current state-of-the-art for shortest hyperpaths in cell signaling hypergraphs solves a mixed-integer linear program to find an optimal hyperpath that is restricted to be acyclic, and offers no efficiency guarantees.

RESULTS

We present, for the first time, a heuristic for general shortest hyperpaths that properly handles cycles, and is guaranteed to be efficient. We show the heuristic finds provably optimal hyperpaths for the class of singleton-tail hypergraphs, and also give a practical algorithm for tractably generating all source-sink hyperpaths. The accuracy of the heuristic is demonstrated through comprehensive experiments on all source-sink instances from the standard NCI-PID and Reactome pathway databases, which show it finds a hyperpath that matches the state-of-the-art mixed-integer linear program on over 99% of all instances that are acyclic. On instances where only cyclic hyperpaths exist, the heuristic surpasses the state-of-the-art, which finds no solution; on every such cyclic instance, enumerating all source-sink hyperpaths shows the solution found by the heuristic was in fact optimal.

CONCLUSIONS

The new shortest hyperpath heuristic is both fast and accurate. This makes finding source-sink hyperpaths, which in general may contain cycles, now practical for real cell signaling networks.

AVAILABILITY

Source code for the hyperpath heuristic in a new tool we call Hhugin (as well as for hyperpath enumeration, and all dataset instances) is available free for non-commercial use at http://hhugin.cs.arizona.edu.

Analysis of Hypergraph Signals via High-Order Total Variation

Beyond pairwise relationships, interactions among groups of agents do exist in many real-world applications, but they are difficult to capture by conventional graph models. Generalized from graphs, hypergraphs have been introduced to describe such high-order group interactions. Inspired by graph signal processing (GSP) theory, an existing hypergraph signal processing (HGSP) method presented a spectral analysis framework relying on the orthogonal CP decomposition of adjacency tensors. However, such decomposition may not exist even for supersymmetric tensors. In this paper, we propose a high-order total variation (HOTV) form of a hypergraph signal (HGS) as its smoothness measure, which is a hyperedge-wise measure aggregating all signal values in each hyperedge instead of a pairwise one in most existing work. Further, we propose an HGS analysis framework based on the Tucker decomposition of the hypergraph Laplacian induced by the aforementioned HOTV. We construct an orthonormal basis from the HOTV, by which a new spectral transformation of the HGS is introduced. Then, we design hypergraph filters in both vertex and spectral domains correspondingly. Finally, we illustrate the advantages of the proposed framework by applications in label learning.

Knots and Knot-Hyperpaths in Hypergraphs

This paper deals with some theoretical aspects of hypergraphs related to hyperpaths and hypertrees. In ordinary graph theory, the intersecting or adjacent edges contain exactly one vertex; however, in the case of hypergraph theory, the adjacent or intersecting hyperedges may contain more than one vertex. This fact leads to the intuitive notion of knots, i.e., a collection of explicit vertices. The key idea of this manuscript lies in the introduction of the concept of the knot, which is a subset of the intersection of some intersecting hyperedges. We define knot-hyperpaths and equivalent knot-hyperpaths and study their relationships with the algebraic space continuity and the pseudo-open character of maps. Moreover, we establish a sufficient condition under which a hypergraph is a hypertree, without using the concept of the host graph.

OUP accepted manuscript

Motivation

A factory in a metabolic network specifies how to produce target molecules from source compounds through biochemical reactions, properly accounting for reaction stoichiometry to conserve or not deplete intermediate metabolites. While finding factories is a fundamental problem in systems biology, available methods do not consider the number of reactions used, nor address negative regulation.

Methods

We introduce the new problem of finding optimal factories that use the fewest reactions, for the first time incorporating both first- and second-order negative regulation. We model this problem with directed hypergraphs, prove it is NP-complete, solve it via mixed-integer linear programming, and accommodate second-order negative regulation by an iterative approach that generates next-best factories.

Results

This optimization-based approach is remarkably fast in practice, typically finding optimal factories in a few seconds, even for metabolic networks involving tens of thousands of reactions and metabolites, as demonstrated through comprehensive experiments across all instances from standard reaction databases.

Availability and implementation

Source code for an implementation of our new method for optimal factories with negative regulation in a new tool called Odinn, together with all datasets, is available free for non-commercial use at http://odinn.cs.arizona.edu.

Estimating cellular redundancy in networks of genetic expression

Networks of genetic expression can be modeled by hypergraphs with the additional structure that real coefficients are given to each vertex-edge incidence. The spectra, i.e. the multiset of the eigenvalues, of such hypergraphs, are known to encode structural information of the data. We show how these spectra can be used, in particular, in order to give an estimation of cellular redundancy, a novel measure of gene expression heterogeneity, of the network. We analyze some simulated and real data sets of gene expression for illustrating the new method proposed here.

Geometry and symmetry in biochemical reaction systems

Complex systems of intracellular biochemical reactions have a central role in regulating cell identities and functions. Biochemical reaction systems are typically studied using the language and tools of graph theory. However, graph representations only describe pairwise interactions between molecular species and so are not well suited to modelling complex sets of reactions that may involve numerous reactants and/or products. Here, we make use of a recently developed hypergraph theory of chemical reactions that naturally allows for higher-order interactions to explore the geometry and quantify functional redundancy in biochemical reactions systems. Our results constitute a general theory of automorphisms for oriented hypergraphs and describe the effect of automorphism group structure on hypergraph Laplacian spectra.

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.

Integrated querying and version control of context-specific biological networks

MOTIVATION

Biomolecular data stored in public databases is increasingly specialized to organisms, context/pathology and tissue type, potentially resulting in significant overhead for analyses. These networks are often specializations of generic interaction sets, presenting opportunities for reducing storage and computational cost. Therefore, it is desirable to develop effective compression and storage techniques, along with efficient algorithms and a flexible query interface capable of operating on compressed data structures. Current graph databases offer varying levels of support for network integration. However, these solutions do not provide efficient methods for the storage and querying of versioned networks.

RESULTS

We present VerTIoN, a framework consisting of novel data structures and associated query mechanisms for integrated querying of versioned context-specific biological networks. As a use case for our framework, we study network proximity queries in which the user can select and compose a combination of tissue-specific and generic networks. Using our compressed version tree data structure, in conjunction with state-of-the-art numerical techniques, we demonstrate real-time querying of large network databases.

CONCLUSION

Our results show that it is possible to support flexible queries defined on heterogeneous networks composed at query time while drastically reducing response time for multiple simultaneous queries. The flexibility offered by VerTIoN in composing integrated network versions opens significant new avenues for the utilization of ever increasing volume of context-specific network data in a broad range of biomedical applications.

AVAILABILITY AND IMPLEMENTATION

VerTIoN is implemented as a C++ library and is available at http://compbio.case.edu/omics/software/vertion and https://github.com/tjcowman/vertion.

CONTACT

tyler.cowman@case.edu.

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.

Querying of Disparate Association and Interaction Data in Biomedical Applications

In biomedical applications, network models are commonly used to represent interactions and higher-level associations among biological entities. Integrated analyses of these interaction and association data has proven useful in extracting knowledge, and generating novel hypotheses for biomedical research. However, since most datasets provide their own schema and query interface, opportunities for exploratory and integrative querying of disparate data are currently limited. In this study, we utilize RDF-based representations of biomedical interaction and association data to develop a querying framework that enables flexible specification and efficient processing of graph template matching queries. The proposed framework enables integrative querying of biomedical databases to discover complex patterns of associations among a diverse range of biological entities, including biomolecules, biological processes, organisms, and phenotypes. Our experimental results on the UniProt dataset show that the proposed framework can be used to efficiently process complex queries, and identify biologically relevant patterns of associations that cannot be readily obtained by querying each dataset independently.

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.

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.