Biology Reference
In-Depth Information
constructed for organisms such as Homo sapiens, Saccha-
romyces cerevisiae (S. cerevisiae) Helicobacter pylori and
others
[10
e
20]
. Regulatory and metabolic networks have
also been successfully mapped for yeast, Escherichia coli
and various other organisms
[21
e
23]
. However, we still
lack data regarding other networks taking part in the
cellular processes, such as sRNA and RNAi-mediated
networks, about which we currently know little.
system using a regular undirected network. As a more
complicated system we refer to metabolic networks. These
systems can be conceptualized as networks on many levels
of abstraction. For instance, one can visualize the molecular
substrates as nodes, and the reactions transforming
substrates to products as links. In this case the links are
attributed by the enzyme catalyzing the reaction, and the
graph is directed. However, there are contexts in which it is
sufficient to use a simpler description, where the enzymes
are ignored and the links are undirected. In this case the
graph simply describes
BIOLOGICAL SYSTEMS AS GRAPHS
Although the foundations of graph theory were laid purely
out of mathematical curiosity, its applicability as a tool for
the characterization of complex systems has long been
appreciated. The notion is that the behavior of complex
systems arises from the coordinated actions of many
interacting components. The network abstraction can then
be used to reveal the underlying structure of these inter-
actions. The interacting components are signified by
a series of nodes, and the interactions between selected
pairs of these nodes are represented by the links (or edges)
drawn between them. This abstract description eliminates
some of the details associated with the specific nature of the
system at hand. However, it allows one to utilize the well-
established formalisms of graph theory, thus providing
a powerful tool for the analysis and understanding of these
complex systems. Moreover, this categorical representation
applied to various systems provides the grounds for
comparison between seemingly distinct networks. This
process has proven highly beneficial, as one of the most
important discoveries of recent years was that despite the
diversity of cellular networks, several important universal
properties are shared by them all
[5]
.
In some cases the network description of a cellular
system is straightforward and natural. Consider, for
instance, the set of physical binding reactions between pairs
of proteins or between proteins and other molecules, such
as nucleic acids or metabolites. Here it seems natural to use
a node for the representation of each molecular type, and an
edge to denote each potential binding reaction. However, in
other cases the network description is not unique, and may
differ according to the motivation of the study. A simple
example regards the transcriptional regulatory network. In
this network the edges link between transcription factors
and the genes that they regulate. Here the information flows
from the regulating gene to the regulated one, so that the
links are not symmetrical. The network is thus a directed
network. Moreover, the relationship between a pair of
interacting genes can be of an activating or of an inhibitory
nature. Thus two different types of directed edges exist,
which can be denoted by positive versus negative, or
graphically by
the interconnections between
metabolites,
leaving out
the detailed chemistry that
underlies these connections.
THE TOOLS OF GRAPH THEORY
In the basis of graph theory lies the insight that a complex
system could be reduced into a series of abstract components
tied together by a set of connections. The spark of this idea is
commonly attributed to the 18th-century mathematician
Leonhard Euler, who in 1735 used it to solve the problem of
the Seven Bridges of K¨nigsberg, a problem which back
then confused the residents of the Prussian town. To show
that one cannot visit all of the city's islands without crossing
at least one of the city's seven bridges twice, Euler con-
structed an abstract map of the city in which the islands were
represented by nodes and the bridges by edges. In doing so,
Euler mapped a realistic problem, in all of its complexities,
into a clean abstract mathematical representation, which
allowed him to focus strictly on the structural crux of the
problem. However, this spark remained dim and only re-
emerged as an elaborate, formalized mathematical theory
some 200 years later, in the 20th century, following the work
of Paul Erd˝s and Alfr´dR´nyi.
Erd˝ seR´nyi e The Benchmark Network
The most elementary network considered in graph theory, is
the Erd
˝
s
e
R
´
nyi random network, where each pair of nodes
is connected with equal probability
[24
e
26]
. The properties
of this prototypic network serve as a benchmark to which we
later compare the more realistic networks of cellular biology.
To construct an Erd
˝
s
e
R
´
nyi network, we consider a set of N
nodes. For each of the
N
2
pairs of nodes in the network
we assign an edge with probability p, typically chosen so that
p
ð
N
1
1. Simple as it may be, the Erd
˝
s
e
R
´
nyi network
features some surprising characteristics, commonly observed
in many real-world biological networks.
Degrees and Degree Distribution
To analyze the components of the network we introduce
some elementary network measures. For concreteness, we
. Nevertheless, in many
contexts the directed nature of the interactions, or their
sign, is not important, and it is sufficient to model the
versus
dj
/
