Hypergraphs and cellular networks

An application of node and edge nonlinear hypergraph centrality to a protein complex hypernetwork

The use of graph centrality measures applied to biological networks, such as protein interaction networks, underpins much research into identifying key players within biological processes. This approach however is restricted to dyadic interactions and it is well-known that in many instances interactions are polyadic. In this study we illustrate the merit of using hypergraph centrality applied to a hypernetwork as an alternative. Specifically, we review and propose an extension to a recently introduced node and edge nonlinear hypergraph centrality model which provides mutually dependent node and edge centralities. A Saccharomyces Cerevisiae protein complex hypernetwork is used as an example application with nodes representing proteins and hyperedges representing protein complexes. The resulting rankings of the nodes and edges are considered to see if they provide insight into the essentiality of the proteins and complexes. We find that certain variations of the model predict essentiality more accurately and that the degree-based variation illustrates that the centrality-lethality rule extends to a hypergraph setting. In particular, through exploitation of the models flexibility, we identify small sets of proteins densely populated with essential proteins. One of the key advantages of applying this model to a protein complex hypernetwork is that it also provides a classification method for protein complexes, unlike previous approaches which are only concerned with classifying proteins.

Robust Optimal Metabolic Factories

Perhaps the most fundamental model in synthetic and systems biology for inferring pathways in metabolic reaction networks is a metabolic factory: a system of reactions that starts from a set of source compounds and produces a set of target molecules, while conserving or not depleting intermediate metabolites. Finding a shortest factory-that minimizes a sum of real-valued weights on its reactions to infer the most likely pathway-is NP-complete. The current state-of-the-art for shortest factories solves a mixed-integer linear program with a major drawback: it requires the user to set a critical parameter, where too large a value can make optimal solutions infeasible, while too small a value can yield degenerate solutions due to numerical error. We present the first robust algorithm for optimal factories that is both parameter-free (relieving the user from determining a parameter setting) and degeneracy-free (guaranteeing it finds an optimal nondegenerate solution). We also give for the first time a complete characterization of the graph-theoretic structure of shortest factories, that reveals an important class of degenerate solutions which was overlooked and potentially output by the prior state-of-the-art. We show degeneracy is precisely due to invalid stoichiometries in reactions, and provide an efficient algorithm for identifying all such misannotations in a metabolic network. In addition we settle the relationship between the two established pathway models of hyperpaths and factories by proving hyperpaths actually comprise a subclass of factories. Comprehensive experiments over all instances from the standard metabolic reaction databases in the literature demonstrate our parameter-free exact algorithm is fast in practice, quickly finding optimal factories in large real-world networks containing thousands of reactions. A preliminary implementation of our robust algorithm for shortest factories in a new tool called Freeia is available free for research use at http://freeia.cs.arizona.edu.

Spaces of mathematical chemistry

In an effort to expand the domain of mathematical chemistry and inspire research beyond the realms of graph theory and quantum chemistry, we explore five mathematical chemistry spaces and their interconnectedness. These spaces comprise the chemical space, which encompasses substances and reactions; the space of reaction conditions, spanning the physical and chemical aspects involved in chemical reactions; the space of reaction grammars, which encapsulates the rules for creating and breaking chemical bonds; the space of substance properties, covering all documented measurements regarding substances; and the space of substance representations, composed of the various ontologies for characterising substances.

AFP: Finding pathways accounting for stoichiometry along with atom group tracking in metabolic network

Automatically finding novel pathways plays an important role in the initial designs of metabolic pathways in synthetic biology and metabolic engineering. Although path-finding methods have been successfully applied in identifying valuable synthetic pathways, few efforts have been made in fusing atom group tracking into building stoichiometry model to search metabolic pathways from arbitrary start compound via Mixed Integer Linear Programming (MILP). We propose a novel method called AFP to find metabolic pathways by incorporating atom group tracking into reaction stoichiometry via MILP. AFP tracks the movements of atom groups in the reaction stoichiometry to construct MILP model to search the pathways containing atom groups exchange in the reactions and adapts the MILP model to provide the options of searching pathways from an arbitrary or given compound to the target compound. Combining atom group tracking with reaction stoichiometry to build MILP model for pathfinding may promote the search of well-designed alternative pathways at the stoichiometric modeling level. The experimental comparisons to the known pathways show that our proposed method AFP is more effective to recover the known pathways than other existing methods and is capable of discovering biochemically feasible pathways producing the metabolites of interest.

Dynamical Fluctuations of Random Walks in Higher-Order Networks

Although higher-order interactions are known to affect the typical state of dynamical processes giving rise to new collective behavior, how they drive the emergence of rare events and fluctuations is still an open problem. We investigate how fluctuations of a dynamical quantity of a random walk exploring a higher-order network arise over time. In the quenched case, where the hypergraph structure is fixed, through large deviation theory we show that the appearance of rare events is hampered in nodes with many higher-order interactions, and promoted elsewhere. Dynamical fluctuations are further boosted in an annealed scenario, where both the diffusion process and higher-order interactions evolve in time. Here, extreme fluctuations generated by optimal higher-order configurations can be predicted in the limit of a saddle-point approximation. Our study lays the groundwork for a wide and general theory of fluctuations and rare events in higher-order networks.

Structure and inference in hypergraphs with node attributes

Many networked datasets with units interacting in groups of two or more, encoded with hypergraphs, are accompanied by extra information about nodes, such as the role of an individual in a workplace. Here we show how these node attributes can be used to improve our understanding of the structure resulting from higher-order interactions. We consider the problem of community detection in hypergraphs and develop a principled model that combines higher-order interactions and node attributes to better represent the observed interactions and to detect communities more accurately than using either of these types of information alone. The method learns automatically from the input data the extent to which structure and attributes contribute to explain the data, down weighing or discarding attributes if not informative. Our algorithmic implementation is efficient and scales to large hypergraphs and interactions of large numbers of units. We apply our method to a variety of systems, showing strong performance in hyperedge prediction tasks and in selecting community divisions that correlate with attributes when these are informative, but discarding them otherwise. Our approach illustrates the advantage of using informative node attributes when available with higher-order data.

Current and future directions in network biology

Summary

Network biology is an interdisciplinary field bridging computational and biological sciences that has proved pivotal in advancing the understanding of cellular functions and diseases across biological systems and scales. Although the field has been around for two decades, it remains nascent. It has witnessed rapid evolution, accompanied by emerging challenges. These stem from various factors, notably the growing complexity and volume of data together with the increased diversity of data types describing different tiers of biological organization. We discuss prevailing research directions in network biology, focusing on molecular/cellular networks but also on other biological network types such as biomedical knowledge graphs, patient similarity networks, brain networks, and social/contact networks relevant to disease spread. In more detail, we highlight areas of inference and comparison of biological networks, multimodal data integration and heterogeneous networks, higher-order network analysis, machine learning on networks, and network-based personalized medicine. Following the overview of recent breakthroughs across these five areas, we offer a perspective on future directions of network biology. Additionally, we discuss scientific communities, educational initiatives, and the importance of fostering diversity within the field. This article establishes a roadmap for an immediate and long-term vision for network biology.

Availability and implementation

Not applicable.

Higher-order correlations reveal complex memory in temporal hypergraphs

Many real-world complex systems are characterized by interactions in groups that change in time. Current temporal network approaches, however, are unable to describe group dynamics, as they are based on pairwise interactions only. Here, we use time-varying hypergraphs to describe such systems, and we introduce a framework based on higher-order correlations to characterize their temporal organization. The analysis of human interaction data reveals the existence of coherent and interdependent mesoscopic structures, thus capturing aggregation, fragmentation and nucleation processes in social systems. We introduce a model of temporal hypergraphs with non-Markovian group interactions, which reveals complex memory as a fundamental mechanism underlying the emerging pattern in the data.

Framework to generate hypergraphs with community structure

In recent years hypergraphs have emerged as a powerful tool to study systems with multibody interactions which cannot be trivially reduced to pairs. While highly structured methods to generate synthetic data have proved fundamental for the standardized evaluation of algorithms and the statistical study of real-world networked data, these are scarcely available in the context of hypergraphs. Here we propose a flexible and efficient framework for the generation of hypergraphs with many nodes and large hyperedges, which allows specifying general community structures and tune different local statistics. We illustrate how to use our model to sample synthetic data with desired features (assortative or disassortative communities, mixed or hard community assignments, etc.), analyze community detection algorithms, and generate hypergraphs structurally similar to real-world data. Overcoming previous limitations on the generation of synthetic hypergraphs, our work constitutes a substantial advancement in the statistical modeling of higher-order systems.

Higher-Order Components Dictate Higher-Order Contagion Dynamics in Hypergraphs

The presence of the giant component is a necessary condition for the emergence of collective behavior in complex networked systems. Unlike networks, hypergraphs have an important native feature that components of hypergraphs might be of higher order, which could be defined in terms of the number of common nodes shared between hyperedges. Although the extensive higher-order component (HOC) could be witnessed ubiquitously in real-world hypergraphs, the role of the giant HOC in collective behavior on hypergraphs has yet to be elucidated. In this Letter, we demonstrate that the presence of the giant HOC fundamentally alters the outbreak patterns of higher-order contagion dynamics on real-world hypergraphs. Most crucially, the giant HOC is required for the higher-order contagion to invade globally from a single seed. We confirm it by using synthetic random hypergraphs containing adjustable and analytically calculable giant HOC.

Triadic Approximation Reveals the Role of Interaction Overlap on the Spread of Complex Contagions on Higher-Order Networks

Contagion processes relying on the exposure to multiple sources are prevalent in social systems, and are effectively represented by hypergraphs. In this Letter, we derive a mean-field model that goes beyond node- and pair-based approximations. We reveal how the stability of the contagion-free state is decided by either two- or three-body interactions, and how this is strictly related to the degree of overlap between these interactions. Our findings demonstrate the dual effect of increased overlap: it lowers the invasion threshold, yet produces smaller outbreaks. Corroborated by numerical simulations, our results emphasize the significance of the chosen representation in describing a higher-order process.

Filtration evolution of hypergraphs: A novel approach to studying multidimensional datasets

The rapid growth of large datasets has led to a demand for novel approaches to extract valuable insights from intricate information. Graph theory provides a natural framework to model these relationships, but standard graphs may not capture the complex interdependence between components. Hypergraphs are a powerful extension of graphs that can represent higher-order relationships in the data. In this paper, we propose a novel approach to studying the structure of a dataset using hypergraph theory and a filtration method. Our method involves building a set of hypergraphs based on a variable distance parameter, enabling us to infer qualitative and quantitative information about the data structure. We apply our method to various sets of points, dynamical systems, signal models, and real electrophysiological data. Our results show that the proposed method can effectively differentiate between varying datasets, demonstrating its potential utility in a range of scientific applications.

Percolation and Topological Properties of Temporal Higher-Order Networks

Many complex systems that exhibit temporal nonpairwise interactions can be represented by means of generative higher-order network models. Here, we propose a hidden variable formalism to analytically characterize a general class of higher-order network models. We apply our framework to a temporal higher-order activity-driven model, providing analytical expressions for the main topological properties of the time-integrated hypergraphs, depending on the integration time and the activity distributions characterizing the model. Furthermore, we provide analytical estimates for the percolation times of general classes of uncorrelated and correlated hypergraphs. Finally, we quantify the extent to which the percolation time of empirical social interactions is underestimated when their higher-order nature is neglected.

Hypergraphs and centrality measures identifying key features in gene expression data

Multidisciplinary approaches can significantly advance our understanding of complex systems. For instance, gene co-expression networks align prior knowledge of biological systems with studies in graph theory, emphasising pairwise gene to gene interactions. In this paper, we extend these ideas, promoting hypergraphs as an investigative tool for studying multi-way interactions in gene expression data. Additional freedoms are achieved by representing individual genes with hyperedges, and simultaneously testing each gene against many features/vertices. Further gene/hyperedge interactions can be captured and explored using the line graph representations, a technique that reduces the complexity of dense hypergraphs. Such an approach provides access to graph centrality measures, which identifies salient features within a data set. For instance dominant or hub-like hyperedges, leading to key knowledge on gene expression. The validity of this approach is established through the study of gene expression data for the plant species Senecio lautus and results will be interpreted within this biological setting.

Percolation Theories for Quantum Networks

Quantum networks have experienced rapid advancements in both theoretical and experimental domains over the last decade, making it increasingly important to understand their large-scale features from the viewpoint of statistical physics. This review paper discusses a fundamental question: how can entanglement be effectively and indirectly (e.g., through intermediate nodes) distributed between distant nodes in an imperfect quantum network, where the connections are only partially entangled and subject to quantum noise? We survey recent studies addressing this issue by drawing exact or approximate mappings to percolation theory, a branch of statistical physics centered on network connectivity. Notably, we show that the classical percolation frameworks do not uniquely define the network's indirect connectivity. This realization leads to the emergence of an alternative theory called "concurrence percolation", which uncovers a previously unrecognized quantum advantage that emerges at large scales, suggesting that quantum networks are more resilient than initially assumed within classical percolation contexts, offering refreshing insights into future quantum network design.

Robustness and Complexity of Directed and Weighted Metabolic Hypergraphs

Metabolic networks are probably among the most challenging and important biological networks. Their study provides insight into how biological pathways work and how robust a specific organism is against an environment or therapy. Here, we propose a directed hypergraph with edge-dependent vertex weight as a novel framework to represent metabolic networks. This hypergraph-based representation captures higher-order interactions among metabolites and reactions, as well as the directionalities of reactions and stoichiometric weights, preserving all essential information. Within this framework, we propose the communicability and the search information as metrics to quantify the robustness and complexity of directed hypergraphs. We explore the implications of network directionality on these measures and illustrate a practical example by applying them to a small-scale E. coli core model. Additionally, we compare the robustness and the complexity of 30 different models of metabolism, connecting structural and biological properties. Our findings show that antibiotic resistance is associated with high structural robustness, while the complexity can distinguish between eukaryotic and prokaryotic organisms.

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.

Kernel-based joint independence tests for multivariate stationary and non-stationary time series

Multivariate time-series data that capture the temporal evolution of interconnected systems are ubiquitous in diverse areas. Understanding the complex relationships and potential dependencies among co-observed variables is crucial for the accurate statistical modelling and analysis of such systems. Here, we introduce kernel-based statistical tests of joint independence in multivariate time series by extending the d-variable Hilbert-Schmidt independence criterion to encompass both stationary and non-stationary processes, thus allowing broader real-world applications. By leveraging resampling techniques tailored for both single- and multiple-realization time series, we show how the method robustly uncovers significant higher-order dependencies in synthetic examples, including frequency mixing data and logic gates, as well as real-world climate, neuroscience and socio-economic data. Our method adds to the mathematical toolbox for the analysis of multivariate time series and can aid in uncovering high-order interactions in data.

Contagion dynamics on hypergraphs with nested hyperedges

In complex social systems encoded as hypergraphs, higher-order (i.e., group) interactions taking place among more than two individuals are represented by hyperedges. One of the higher-order correlation structures native to hypergraphs is the nestedness: Some hyperedges can be entirely contained (that is, nested) within another larger hyperedge, which itself can also be nested further in a hierarchical manner. Yet the effect of such hierarchical structure of hyperedges on the dynamics has remained unexplored. In this context, here we propose a random nested-hypergraph model with a tunable level of nestedness and investigate the effects of nestedness on a higher-order susceptible-infected-susceptible process. By developing an analytic framework called the facet approximation, we obtain the steady-state fraction of infected nodes on the random nested-hypergraph model more accurately than existing methods. Our results show that the hyperedge-nestedness affects the phase diagram significantly. Monte Carlo simulations support the analytical results.

Community detection in large hypergraphs

Hypergraphs, describing networks where interactions take place among any number of units, are a natural tool to model many real-world social and biological systems. Here, we propose a principled framework to model the organization of higher-order data. Our approach recovers community structure with accuracy exceeding that of currently available state-of-the-art algorithms, as tested in synthetic benchmarks with both hard and overlapping ground-truth partitions. Our model is flexible and allows capturing both assortative and disassortative community structures. Moreover, our method scales orders of magnitude faster than competing algorithms, making it suitable for the analysis of very large hypergraphs, containing millions of nodes and interactions among thousands of nodes. Our work constitutes a practical and general tool for hypergraph analysis, broadening our understanding of the organization of real-world higher-order systems.

Digital contact tracing on hypergraphs

The higher-order interactions emerging in the network topology affect the effectiveness of digital contact tracing (DCT). In this paper, we propose a mathematical model in which we use the hypergraph to describe the gathering events. In our model, the role of DCT is modeled as individuals carrying the app. When the individuals in the hyperedge all carry the app, epidemics cannot spread through this hyperedge. We develop a generalized percolation theory to investigate the epidemic outbreak size and threshold. We find that DCT can effectively suppress the epidemic spreading, i.e., decreasing the outbreak size and enlarging the threshold. DCT limits the spread of the epidemic to larger cardinality of hyperedges. On real-world networks, the inhibitory effect of DCT on the spread of epidemics is evident when the spread of epidemics is small.

Teasing out missing reactions in genome-scale metabolic networks through hypergraph learning

GEnome-scale Metabolic models (GEMs) are powerful tools to predict cellular metabolism and physiological states in living organisms. However, due to our imperfect knowledge of metabolic processes, even highly curated GEMs have knowledge gaps (e.g., missing reactions). Existing gap-filling methods typically require phenotypic data as input to tease out missing reactions. We still lack a computational method for rapid and accurate gap-filling of metabolic networks before experimental data is available. Here we present a deep learning-based method - CHEbyshev Spectral HyperlInk pREdictor (CHESHIRE) - to predict missing reactions in GEMs purely from metabolic network topology. We demonstrate that CHESHIRE outperforms other topology-based methods in predicting artificially removed reactions over 926 high- and intermediate-quality GEMs. Furthermore, CHESHIRE is able to improve the phenotypic predictions of 49 draft GEMs for fermentation products and amino acids secretions. Both types of validation suggest that CHESHIRE is a powerful tool for GEM curation to reveal unknown links between reactions and observed metabolic phenotypes.

Eigenvector localization in hypergraphs: Pairwise versus higher-order links

Localization behaviors of Laplacian eigenvectors of complex networks furnish an explanation to various dynamical phenomena of the corresponding complex systems. We numerically examine roles of higher-order and pairwise links in driving eigenvector localization of hypergraphs Laplacians. We find that pairwise interactions can engender localization of eigenvectors corresponding to small eigenvalues for some cases, whereas higher-order interactions, even being much much less than the pairwise links, keep steering localization of the eigenvectors corresponding to larger eigenvalues for all the cases considered here. These results will be advantageous to comprehend dynamical phenomena, such as diffusion, and random walks on a range of real-world complex systems having higher-order interactions in better manner.

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.

Generalizing p-Laplacian: spectral hypergraph theory and a partitioning algorithm

For hypergraph clustering, various methods have been proposed to define hypergraph p-Laplacians in the literature. This work proposes a general framework for an abstract class of hypergraph p-Laplacians from a differential-geometric view. This class includes previously proposed hypergraph p-Laplacians and also includes previously unstudied novel generalizations. For this abstract class, we extend current spectral theory by providing an extension of nodal domain theory for the eigenvectors of our hypergraph p-Laplacian. We use this nodal domain theory to provide bounds on the eigenvalues via a higher-order Cheeger inequality. Following our extension of spectral theory, we propose a novel hypergraph partitioning algorithm for our generalized p-Laplacian. Our empirical study shows that our algorithm outperforms spectral methods based on existing p-Laplacians.

Inference of hyperedges and overlapping communities in hypergraphs

Hypergraphs, encoding structured interactions among any number of system units, have recently proven a successful tool to describe many real-world biological and social networks. Here we propose a framework based on statistical inference to characterize the structural organization of hypergraphs. The method allows to infer missing hyperedges of any size in a principled way, and to jointly detect overlapping communities in presence of higher-order interactions. Furthermore, our model has an efficient numerical implementation, and it runs faster than dyadic algorithms on pairwise records projected from higher-order data. We apply our method to a variety of real-world systems, showing strong performance in hyperedge prediction tasks, detecting communities well aligned with the information carried by interactions, and robustness against addition of noisy hyperedges. Our approach illustrates the fundamental advantages of a hypergraph probabilistic model when modeling relational systems with higher-order interactions.

What makes a reaction network "chemical"?

BACKGROUND

Reaction networks (RNs) comprise a set X of species and a set [Formula: see text] of reactions [Formula: see text], each converting a multiset of educts [Formula: see text] into a multiset [Formula: see text] of products. RNs are equivalent to directed hypergraphs. However, not all RNs necessarily admit a chemical interpretation. Instead, they might contradict fundamental principles of physics such as the conservation of energy and mass or the reversibility of chemical reactions. The consequences of these necessary conditions for the stoichiometric matrix [Formula: see text] have been discussed extensively in the chemical literature. Here, we provide sufficient conditions for [Formula: see text] that guarantee the interpretation of RNs in terms of balanced sum formulas and structural formulas, respectively.

RESULTS

Chemically plausible RNs allow neither a perpetuum mobile, i.e., a "futile cycle" of reactions with non-vanishing energy production, nor the creation or annihilation of mass. Such RNs are said to be thermodynamically sound and conservative. For finite RNs, both conditions can be expressed equivalently as properties of the stoichiometric matrix [Formula: see text]. The first condition is vacuous for reversible networks, but it excludes irreversible futile cycles and-in a stricter sense-futile cycles that even contain an irreversible reaction. The second condition is equivalent to the existence of a strictly positive reaction invariant. It is also sufficient for the existence of a realization in terms of sum formulas, obeying conservation of "atoms". In particular, these realizations can be chosen such that any two species have distinct sum formulas, unless [Formula: see text] implies that they are "obligatory isomers". In terms of structural formulas, every compound is a labeled multigraph, in essence a Lewis formula, and reactions comprise only a rearrangement of bonds such that the total bond order is preserved. In particular, for every conservative RN, there exists a Lewis realization, in which any two compounds are realized by pairwisely distinct multigraphs. Finally, we show that, in general, there are infinitely many realizations for a given conservative RN.

CONCLUSIONS

"Chemical" RNs are directed hypergraphs with a stoichiometric matrix [Formula: see text] whose left kernel contains a strictly positive vector and whose right kernel does not contain a futile cycle involving an irreversible reaction. This simple characterization also provides a concise specification of random models for chemical RNs that additionally constrain [Formula: see text] by rank, sparsity, or distribution of the non-zero entries. Furthermore, it suggests several interesting avenues for future research, in particular, concerning alternative representations of reaction networks and infinite chemical universes.

Dynamical systems defined on simplicial complexes: Symmetries, conjugacies, and invariant subspaces

We consider the general model for dynamical systems defined on a simplicial complex. We describe the conjugacy classes of these systems and show how symmetries in a given simplicial complex manifest in the dynamics defined thereon, especially with regard to invariant subspaces in the dynamics.

Topological data analysis of truncated contagion maps

The investigation of dynamical processes on networks has been one focus for the study of contagion processes. It has been demonstrated that contagions can be used to obtain information about the embedding of nodes in a Euclidean space. Specifically, one can use the activation times of threshold contagions to construct contagion maps as a manifold-learning approach. One drawback of contagion maps is their high computational cost. Here, we demonstrate that a truncation of the threshold contagions may considerably speed up the construction of contagion maps. Finally, we show that contagion maps may be used to find an insightful low-dimensional embedding for single-cell RNA-sequencing data in the form of cell-similarity networks and so reveal biological manifolds. Overall, our work makes the use of contagion maps as manifold-learning approaches on empirical network data more viable.

HyperGraphs.jl - representing high-order relationships in Julia

Summary

HyperGraphs.jl is a Julia package that implements hypergraphs. These are a generalization of graphs that allow us to represent n-ary relationships and not just binary, pairwise relationships. High-order interactions are commonplace in biological systems and are of critical importance to their dynamics; hypergraphs thus offer a natural way to accurately describe and model these systems.

Availability and implementation

HyperGraphs.jl is freely available under the MIT license. Source code and documentation can be found at https://github.com/lpmdiaz/HyperGraphs.jl.

Supplementary information

Supplementary data are available at Bioinformatics online.

Correlation-guided Network Integration (CoNI), an R package for integrating numerical omics data that allows multiform graph representations to study molecular interaction networks

Summary

Today's immense growth in complex biological data demands effective and flexible tools for integration, analysis and extraction of valuable insights. Here, we present CoNI, a practical R package for the unsupervised integration of numerical omics datasets. Our tool is based on partial correlations to identify putative confounding variables for a set of paired dependent variables. CoNI combines two omics datasets in an integrated, complex hypergraph-like network, represented as a weighted undirected graph, a bipartite graph, or a hypergraph structure. These network representations form a basis for multiple further analyses, such as identifying priority candidates of biological importance or comparing network structures dependent on different conditions.

Availability and implementation

The R package CoNI is available on the Comprehensive R Archive Network (https://cran.r-project.org/web/packages/CoNI/) and GitLab (https://gitlab.com/computational-discovery-research/coni). It is distributed under the GNU General Public License (version 3).

Supplementary information

Supplementary data are available at Bioinformatics Advances online.

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.

Hypergraph Learning: Methods and Practices

Hypergraph learning is a technique for conducting learning on a hypergraph structure. In recent years, hypergraph learning has attracted increasing attention due to its flexibility and capability in modeling complex data correlation. In this paper, we first systematically review existing literature regarding hypergraph generation, including distance-based, representation-based, attribute-based, and network-based approaches. Then, we introduce the existing learning methods on a hypergraph, including transductive hypergraph learning, inductive hypergraph learning, hypergraph structure updating, and multi-modal hypergraph learning. After that, we present a tensor-based dynamic hypergraph representation and learning framework that can effectively describe high-order correlation in a hypergraph. To study the effectiveness and efficiency of hypergraph generation and learning methods, we conduct comprehensive evaluations on several typical applications, including object and action recognition, Microblog sentiment prediction, and clustering. In addition, we contribute a hypergraph learning development toolkit called THU-HyperG.

A graph model of combination therapies

The simultaneous use of multiple medications causes drug-drug interactions (DDI) that impact therapeutic efficacy. Here, we argue that graph theory, in conjunction with game theory and ecosystem theory, can address this issue. We treat the coexistence of multiple drugs as a system in which DDI is modeled by game theory. We develop an ordinary differential equation model to characterize how the concentration of a drug changes as a result of its independent capacity and the dependent influence of other drugs through the metabolic response of the host. We coalesce all drugs into personalized and context-specific networks, which can reveal key DDI determinants of therapeutical efficacy. Our model can quantify drug synergy and antagonism and test the translational success of combination therapies to the clinic.

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.

Challenges for machine learning in RNA-protein interaction prediction

RNA-protein interactions have long being recognised as crucial regulators of gene expression. Recently, the development of scalable experimental techniques to measure these interactions has revolutionised the field, leading to the production of large-scale datasets which offer both opportunities and challenges for machine learning techniques. In this brief note, we will discuss some of the major stumbling blocks towards the use of machine learning in computational RNA biology, focusing specifically on the problem of predicting RNA-protein interactions from next-generation sequencing data.

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.

The Genomic Physics of COVID-19 Pathogenesis and Spread

Coronavirus disease (COVID-19) spreads mainly through close contact of infected persons, but the molecular mechanisms underlying its pathogenesis and transmission remain unknown. Here, we propose a statistical physics model to coalesce all molecular entities into a cohesive network in which the roadmap of how each entity mediates the disease can be characterized. We argue that the process of how a transmitter transforms the virus into a recipient constitutes a triad unit that propagates COVID-19 along reticulate paths. Intrinsically, person-to-person transmissibility may be mediated by how genes interact transversely across transmitter, recipient, and viral genomes. We integrate quantitative genetic theory into hypergraph theory to code the main effects of the three genomes as nodes, pairwise cross-genome epistasis as edges, and high-order cross-genome epistasis as hyperedges in a series of mobile hypergraphs. Charting a genome-wide atlas of horizontally epistatic hypergraphs can facilitate the systematic characterization of the community genetic mechanisms underlying COVID-19 spread. This atlas can typically help design effective containment and mitigation strategies and screen and triage those more susceptible persons and those asymptomatic carriers who are incubation virus transmitters.

The distance backbone of complex networks

Redundancy needs more precise characterization as it is a major factor in the evolution and robustness of networks of multivariate interactions. We investigate the complexity of such interactions by inferring a connection transitivity that includes all possible measures of path length for weighted graphs. The result, without breaking the graph into smaller components, is a distance backbone subgraph sufficient to compute all shortest paths. This is important for understanding the dynamics of spread and communication phenomena in real-world networks. The general methodology we formally derive yields a principled graph reduction technique and provides a finer characterization of the triangular geometry of all edges-those that contribute to shortest paths and those that do not but are involved in other network phenomena. We demonstrate that the distance backbone is very small in large networks across domains ranging from air traffic to the human brain connectome, revealing that network robustness to attacks and failures seems to stem from surprisingly vast amounts of redundancy.

Two classes of functional connectivity in dynamical processes in networks

The relationship between network structure and dynamics is one of the most extensively investigated problems in the theory of complex systems of recent years. Understanding this relationship is of relevance to a range of disciplines-from neuroscience to geomorphology. A major strategy of investigating this relationship is the quantitative comparison of a representation of network architecture (structural connectivity, SC) with a (network) representation of the dynamics (functional connectivity, FC). Here, we show that one can distinguish two classes of functional connectivity-one based on simultaneous activity (co-activity) of nodes, the other based on sequential activity of nodes. We delineate these two classes in different categories of dynamical processes-excitations, regular and chaotic oscillators-and provide examples for SC/FC correlations of both classes in each of these models. We expand the theoretical view of the SC/FC relationships, with conceptual instances of the SC and the two classes of FC for various application scenarios in geomorphology, ecology, systems biology, neuroscience and socio-ecological systems. Seeing the organisation of dynamical processes in a network either as governed by co-activity or by sequential activity allows us to bring some order in the myriad of observations relating structure and function of complex networks.

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.

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.

Understanding Changes in the Topology and Geometry of Financial Market Correlations during a Market Crash

In econophysics, the achievements of information filtering methods over the past 20 years, such as the minimal spanning tree (MST) by Mantegna and the planar maximally filtered graph (PMFG) by Tumminello et al., should be celebrated. Here, we show how one can systematically improve upon this paradigm along two separate directions. First, we used topological data analysis (TDA) to extend the notions of nodes and links in networks to faces, tetrahedrons, or k-simplices in simplicial complexes. Second, we used the Ollivier-Ricci curvature (ORC) to acquire geometric information that cannot be provided by simple information filtering. In this sense, MSTs and PMFGs are but first steps to revealing the topological backbones of financial networks. This is something that TDA can elucidate more fully, following which the ORC can help us flesh out the geometry of financial networks. We applied these two approaches to a recent stock market crash in Taiwan and found that, beyond fusions and fissions, other non-fusion/fission processes such as cavitation, annihilation, rupture, healing, and puncture might also be important. We also successfully identified neck regions that emerged during the crash, based on their negative ORCs, and performed a case study on one such neck region.

Classification in biological networks with hypergraphlet kernels

MOTIVATION

Biological and cellular systems are often modeled as graphs in which vertices represent objects of interest (genes, proteins and drugs) and edges represent relational ties between these objects (binds-to, interacts-with and regulates). This approach has been highly successful owing to the theory, methodology and software that support analysis and learning on graphs. Graphs, however, suffer from information loss when modeling physical systems due to their inability to accurately represent multiobject relationships. Hypergraphs, a generalization of graphs, provide a framework to mitigate information loss and unify disparate graph-based methodologies.

RESULTS

We present a hypergraph-based approach for modeling biological systems and formulate vertex classification, edge classification and link prediction problems on (hyper)graphs as instances of vertex classification on (extended, dual) hypergraphs. We then introduce a novel kernel method on vertex- and edge-labeled (colored) hypergraphs for analysis and learning. The method is based on exact and inexact (via hypergraph edit distances) enumeration of hypergraphlets; i.e. small hypergraphs rooted at a vertex of interest. We empirically evaluate this method on fifteen biological networks and show its potential use in a positive-unlabeled setting to estimate the interactome sizes in various species.

AVAILABILITY AND IMPLEMENTATION

https://github.com/jlugomar/hypergraphlet-kernels.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Betweenness centrality of teams in social networks

Betweenness centrality (BC) was proposed as an indicator of the extent of an individual's influence in a social network. It is measured by counting how many times a vertex (i.e., an individual) appears on all the shortest paths between pairs of vertices. A question naturally arises as to how the influence of a team or group in a social network can be measured. Here, we propose a method of measuring this influence on a bipartite graph comprising vertices (individuals) and hyperedges (teams). When the hyperedge size varies, the number of shortest paths between two vertices in a hypergraph can be larger than that in a binary graph. Thus, the power-law behavior of the team BC distribution breaks down in scale-free hypergraphs. However, when the weight of each hyperedge, for example, the performance per team member, is counted, the team BC distribution is found to exhibit power-law behavior. We find that a team with a widely connected member is highly influential.

Hypergraph models of biological networks to identify genes critical to pathogenic viral response

Background

Representing biological networks as graphs is a powerful approach to reveal underlying patterns, signatures, and critical components from high-throughput biomolecular data. However, graphs do not natively capture the multi-way relationships present among genes and proteins in biological systems. Hypergraphs are generalizations of graphs that naturally model multi-way relationships and have shown promise in modeling systems such as protein complexes and metabolic reactions. In this paper we seek to understand how hypergraphs can more faithfully identify, and potentially predict, important genes based on complex relationships inferred from genomic expression data sets.

Results

We compiled a novel data set of transcriptional host response to pathogenic viral infections and formulated relationships between genes as a hypergraph where hyperedges represent significantly perturbed genes, and vertices represent individual biological samples with specific experimental conditions. We find that hypergraph betweenness centrality is a superior method for identification of genes important to viral response when compared with graph centrality.

Conclusions

Our results demonstrate the utility of using hypergraphs to represent complex biological systems and highlight central important responses in common to a variety of highly pathogenic viruses.

Supplementary Information

The online version contains supplementary material available at 10.1186/s12859-021-04197-2.