2.1. Undirected Graphs

A biological interaction network may be represented by an undirected graph, a mathematical structure G(V,E) composed of a set of vertexes V and edges E ( E⊆[V]2 ); we denote the resulting graph as a biological structure graph (BSG). The vertex set consists of all the species that occur in the network; an edge connects two species that are biologically related.

Interesting matters to investigate about BSGs are, for example, determining whether they share the same topological properties of other types of networks (e.g. social or communication networks), their robustness (e.g. against viral attacks or mutations) and if they are self-organizing.

To this end, qualitative approaches based on statistical characteristics of network structure have been widely applied for studying the topology of large-scale networks Albert, R. & Barabasi, A.-L., 2002, Watts, D.J. & Strogatz, S.H., 1998, see Jeong et al., 2001 for a case study of protein-protein interaction networks). These methods try to exploit massive datasets in order to discover patterns that would otherwise be undetectable at smaller scales.

Among the most frequently used and perhaps most significant topological statistics are the average path length l, defined as the average number of links along the shortest paths for all possible pairs of network nodes and the average clustering coefficient

where the clustering coefficient Ci of node i provides a quantitative measure of how close to a clique is the subgraph obtained by considering the vertex i and all its neighbors.

In random networks Erdos, P. & Renyi, A., 1960, an edge connecting two arbitrary nodes is added to the graph as the result of a random experiment (the probability of accepting the edge is equal to a fixed p∈[0,1] )In these networks the statistics l and C¯ generally assume small values Albert, R. & Barabasi, A.-L., 2002. A small l implies that an arbitrary node can reach any other node in a few steps thus it is a measure of the efficiency of information flow (or processing) across the network (eg. it is useful for studying mass transfer in a metabolic network). On the other hand, with a small C¯ it is likely that the network does not contain clusters and groups.

Recent studies have revealed that many complex systems present small-world and scale–free properties Albert, R. & Barabasi, A.-L., 2002. A small-world network has a significantly larger C¯ , with respect to a random graph constructed with the same vertex set, and a relatively small l Watts, D.J. & Strogatz, S.H., 1998. Scale-free networks, on the other hand, are characterised by the degree distribution following the Pareto or power-law distribution p(k)∼k⋎ ,meaning that the fraction p(k) of nodes in the network having k links to other nodes is proportional to k⋎ where ⋎ is a constant typically in the range ]2,3[ Albert, R. & Barabasi, A.-L., 2002.

It has been conjectured that a self-organizing mechanism based on the preferential attachment rule can explain the dynamics of scale-free networks. Preferential attachment, which naturally leads to the power-law degree distribution, implies that when a new node is added to the network it is attracted by the vertexes with the highest degree. This is in contrast to random graphs where the addition of nodes follows a pure probabilistic process, meaning that nodes are equally important in a statistical sense (no node is privileged).

Research has shown that the functions of a complex system may be affected to a large extent by its network topology Albert, R. & Barabasi, A.-L., 2002. For example, the greater tendency for clustering in metabolic networks appears related to the organization of functional modules in cells, which contribute to the behaviour and survival of organisms.

In a biological network this behaviour is plausible (and desirable) since the network converges toward a structure that favours the efficiency (low-energy reactions) of its functions (many real world networks ultimately exhibit this structure). Some researchers explain this behaviour as the evidence of evolutionary history; i.e., nodes with high degrees have resisted selective pressure since they are important for the survival of the organism (acting as hubs and thus are essential for the correct functioning of the network). It is this structure that makes such networks tolerant to random failure and errors (e.g. missense point mutations) but less vulnerable to targeted attacks (e.g. removal of nodes with highest degree) Holme et al., 2002, Bollobas & Riordan, 2003. However, while this a posteriori analysis seems consistent with observations of real biological networks there are still many open questions that naturally arise regarding the way they are actually formed.

2.2. Directed Graphs

When reactions are also represented as vertexes Vr , distinct from the set of vertexes Vs denoting species, we obtain a particular directed graph known as a bipartite directed graph G(Vs, Vr, E) where Vs∩Vr=∅ and E contains the arcs connecting species occurring within a specific reaction. Following the terminology introduced by other authors (BPGs, Ruths et al., 2006) we refer to such graphs as biological pathway graphs[1] -

BPGs based on bipartite graphs are characterised by the following properties (which immediately follow from the definition of bipartite graph):

the sets Vs , Vr form a partition of the vertex set V. Therefore a node in a BPG is either a molecule or a reaction but not both;

the edge set E⊆VsxVr∪VrxVs (the symbol x denotes the cartesian product between sets - a directed edge connecting the generic nodes u and v is denoted by uv uv; likewise, the directed edge connecting v to u is denoted by vu). This condition implies that Vs and Vr are independent sets. As the result, molecules point exclusively (are the input) to reactions while the latter are linked only to molecules;

the property r ∈ Vru,v∈Vss.t.uv,rvE implies that any reaction requires at least one molecule (products) in input and produces at least one molecule (substrate) in output.

The BPG directed graph-based formalism is appealing since:

The analysis of a BPG is essentially performed by working on the corresponding adjacency matrix A of size (|Vr|+|Vs|)2 (the notation |S| represents the number of elements in the set S, i.e. the cardinality of S); element A(i,j) is set to 1 if there exists an arc joining vertex i with vertex j (it is straightforward to verify that are |Vs|2 elements in the upper left triangular sub-matrix - above the main diagonal - and |Vs|2 elements in the lower triangular sub-matrix - below the main diagonal - are equal to zero).

An alternative representation is given by the adjacency list L; in this case the list of nodes (either molecules or reactions) for which there exists an arc originating from the i-th node are stored in the corresponding position of the array L(i). Graph analysis algorithms are often more efficient when implemented using adjacency lists.

Of notable interest are the sets ⋎(1)(s)={e∈ E |e=sr,r∈Vr} and ⋎(1)(s)={e∈Ee=rs,r∈Vr} which contain the arcs respectively departing from and entering into an arbitrary species node s, and the sets μ(1)(s)={r∈Vr|rs∈E} and μ(−1)(s)={r∈Vr|sr∈E} which contain respectively the child and parent vertexes (reactions) of an arbitrary node v . Analogous definitions can be set out for interaction s (i.e. for the sets ⋎(1)(r),⋎(−1)(r),μ(1)(r),μ(−1)(r)) .Also, for υ∈Vr∪s d+(v)=|⋎(1)(v)|=|μ(1)(υ)| and d−(υ)=|⋎(−1)(υ)|=|μ(−1)(υ)| are respectively the out degree and in degree of v, we have ∀r∈Vr d+(r)d−(r)  0

The in- and out-degrees of a molecule node are extremely informative since one can identify “source” molecules (with in-degree equal to 0 that act only as substrates) and “sink” molecules (with out-degree equal to 0 that act only as products). Nodes with large in/out-degrees (also called “hub” nodes) are typical of many reaction networks that exhibit the scale-free topology and small-world structure as discussed above.

It is interesting to explore a BPG by searching for the induced subgraph originating from a particular vertex set. The basic use of this algorithm is for identifying the reactions and substrates involved in the transformations between any two (or set of) molecules. In particular, the induced subgraph originating from a certain vertex v∈Vs with constraints specified in order to exclude a set of species nodes Xs⊆Vs and/or reaction nodes Xr⊆Vr from the search (i.e. vertexes that should not be visited by the algorithm). This can be useful for determining how inhibitors affect the overall functionality of the network.

Path enumeration algorithms identify the paths originating in a vertex v∈Vs and terminating in t∈Vs . Again the algorithm may be restricted to visiting (or excluding) certain nodes as above. To detect feedback loops incident on s it is sufficient to set s=t; such loops are worthy of interest from a biological point of view.

An interesting line of research was recently opened by (Ruths et al., 2006) who formulated two biologically significant problems on BPGs: the constrained downstream (CDP) and minimum knockout (MKP) problems. The CDP essentially searches a BPG for the set of reactions that leads from one set of species to another, with the constraint that the search algorithm must include and/or exclude a given set of reactions. An application of a CDP instance to a BPG would therefore be useful to design drugs that modify or inhibit certain biological functions while preserving others. From a topological point of view this amounts to identifying molecules or sets of molecules that have to be targeted to inhibit function of a sub-network while preserving connectivity (and thus information flow) to a different sub-network. On the other hand, the MKP seeks for a minimum-size set of molecules whose removal (knocking out) from the BPG disconnects given sets of source and target species thus making impossible the production of certain target molecules from the source set. An instance of the MDP may help solve the biological problem of identifying the optimal and minimal sets of molecules that have to be targeted to block network function. For example, in patients affected by cancer this could allow the development of therapeutics that can efficiently destroy cancer cells while preserving normal cells.

The above algorithms based on a depth-first search strategy usually require running times of O(|Vs −.. Xs|+|Vr −.. Xr|)

2.3. Relationship between directed and undirected graph representations

The transformation of the BPG G(Vs Vr, E) into an undirected bipartite graph Gu(Vs, Vr, Eu) can be simply obtained by duplicating all the arcs in E, i.e. Eu⊂ E∪{e=rs∈E|sr∈E,s∈Vs,r∈Vr} . It is straightforward to verify that the (symmetric) adjacency matrix B of the associated undirected graph G_u may be calculated by the matrix sum B=A+A’ (or A’+A, A’ denotes the transpose of A) where A is the adjacency matrix of the directed graph G.

Figure 1.

a) An example BPG, (b) the undirected BPG derived from (a) and (c) the BSG corresponding to (b).

As an example, following this procedure the BPG depicted in Figure 1-(a) is transformed into the undirected graph shown in Figure 1-(b), which is also bipartite. From a biological point of view, one must be aware that the undirected graph contains additional information since molecules that were reactants are now also products and vice versa; such newly introduced reactions are not necessarily biologically significant.

A further transformation step is illustrated in Figure 1-(c) where the undirected BPG is transformed into a BSR by cutting reaction nodes (all the information contained in the arcs entering and leaving the reaction is retained).

2.4. Petri Nets

In computer science, a Petri net (PN) is a graphical and mathematical modeling tool for the analysis and simulation of concurrent and/or stochastic systems Murata, 1989. A system is represented as a bipartite directed graph with a set of "place" nodes that contain resources (conditions), and a set of "event" nodes which generate and/or consume resources (transitions).

A PN models both the topology of the network as well as the dynamical behavior of the system. For this reason they have been employed to simulate biological networks Reddy et al., 1993, Tsavachidou & Liebman, 2002, Nagasaki et al., 2005, Chaouiya, 2007. In translating the biological network into a PN, each molecule and each interaction are described as a node. Each molecule is initialized with some number of “tokens,” which are then iteratively reallocated by the interactions to which they are connected.

3.1. SBML

The Systems Biology Markup Language (SBML) is an open XML-based schema for representing quantitative biological models such as regulatory and metabolic networks Hucka et al., 2003, Finney & Hucka, 2003. SBML specifies a formalism for representing biological entities by means of compartments and reacting species, as well as their dynamic behaviour, using reactions, events and arbitrary mathematical rules Hucka et al., 2008. The SBML file format and underlying network structure is widely accepted and supported by a large number of tools (http://sbml.org, 2009).

3.2. BioPAX

The Biological Pathway Exchange Format (BioPAX) is a collaborative effort to create a data exchange format for biological pathway data (http://www.biopax.org, 2009). The BioPAX specification provides an abstract object model, based on the web ontology language (OWL), for the representation of biological pathway concepts. Mapping the concepts defined in any custom data model to the semantically corresponding items in the BioPAX model provides a unified formalism for the representation of biological interaction networks.

3.3. PSI-MI

The Proteomics Standards Initiative (PSI-MI) provides an XML-based formalism for the representation of protein-protein interaction data

(http://psidev.sourceforge.net/mi/xml/doc/user/, 2009). Future developments are aimed at expanding the language to include other types of molecules (e.g. DNA, RNA, etc).

3.4. SBGN

Recently, the level 1 specification of the Systems Biology Graphical Notation (SBGN) was released (http://www.sbgn.org, 2009) in an effort to provide a standardised graphical notation to describe biological systems in a format comprehensible to humans. In this respect, it may be considered a natural complement to SBML and to the aforementioned formalisms.