Mathematical representation of biological networks is often referred as graphs, although a more plausible functional definition can be offered by hypergraphs. In a latest PLoS Computational Biology paper Klamt et al. provide an interesting perspective about notion of using hypergraphs instead of graphs as a modeling framework for network biology. Implementing hypergraphs to model different network analysis problems has several advantages over traditional graph models such as a more accurate representation of biological knowledge, for example a simple graph model can not capture details of multilateral relationships. A graph is nothing but a set of nodes connected by edges, in network biology nodes are described by biological entities such as genes, proteins, metabolites, while edges represent biological interactions between the nodes such as transformation, catalysis, complex formation or any other biological process. Network models such as a reaction with multiple reagents and multiple products, an enzymatic transformation with multiple effectors, a protein complex with more than two proteins, pose a problem of multilateral relationships, and by using hypergraphs one can overcome this conceptual limitation. Although it is always possible to represent these models using simple graphical representation but often it leads to information loss. A hypergraph is a generalization of a graph, where edges can connect any number of vertices. Unlike the graphs, visualization of hypergraphs is difficult, and often network analysis using hypergraphs is more theoretical (mostly using set theory) rather than pictorial. A typical hypergraph H=(V,E) consists of a set V of vertices or nodes and a set E of non-empty subsets of V called as hyperedges. For example V = {v1,v2,v3,v4,v5,v6,v7}, E = {e1,e2,e3,e4} = {{v1,v2,v3},{v2,v3}, {v3,v5,v6},{v4}}

Sperner hypergraph or clutter is a special type of hypergraph where no hyperedge is a subset of another hyperedge. Also,

While graph edges are pairs of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often useful to study hypergraphs where all hyperedges have the same cardinality: a k-uniform hypergraph is a hypergraph such that all its hyperedges have size k. (In other words, it is a collection of sets of size k.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of triples, and so on.

Following diagram explains 4 different scenarios where using hypergraph for network modeling offers advantage over graph- (A) Protein–protein interaction (PPI) networks (B) Minimal hitting sets (MHSs) (C) Reaction networks (D) Logical networks, where example (A,B) represent undirected hypergraphs while (C,D) represent directed hypergraphs.

Example A displays hypergraph (middle) and hypergraph projected onto graph (right) for a given ground set of proteins V={A,B,C,D,E} and a set of complexes. Complexes are nothing but subsets of the ground set of proteins or hyperedges in hypergraph terminology. Further

This representation [hypergraph converted to graph] still captures the information on pairs of proteins that occurred together in a complex; however, in contrast to the hypergraph, the complexes themselves cannot be reconstructed from this figure. This may lead to different results when computing network properties such as the k-core, a measure that is often used to identify the core proteome. In a graph, the k-core is the maximal node-induced sub-graph in which all nodes have a degree (defined as the number of edges a node participates in) equal to or larger than k. The maximum core of a graph corresponds to the highest k where the graph has a non-empty k-core. The maximum k-core of the graph in Figure [A] is a 3-core consisting of the nodes {A,B,C,D}. A similar definition of a k-core can be defined for (Sperner) hypergraphs, where k corresponds to the number of hyperedges each node participates in. The maximum k-core of the hypergraph in Figure [A] is a 2-core consisting of {A,C,E}. Thus, as one would intuitively expect, the maximum k-core of the hypergraph ranks A, C, and E as most important—in contrast to the graph model, whose maximum k-core would weight B and D stronger than E.

Normally many theorems, algorithms and concepts involving graphs also hold for hypergraphs. Graph and hypergraph behavior is particularly different for two types of problems, (1) algorithms finding a particular (e.g., optimal) solution such as shortest-path algorithms or algorithm for finding a maximal matching in a bipartite graph (2) enumeration problems. In case of hypergraphs finding a maximal matching in a bipartite graph or all minimal hitting sets in a hypergraph can be computationally hard while finding shortest-path can be easy if hyperedges are weighted and weight function is additive. Further hypergraph statistics can easily applied to problem of protein-protein interaction where one need to combine two types interactions.
In summary, hypergraphs offer a intuitive and powerful way to formulate biological networks leading more precise description of biological processes with multilateral relationships.
References: