He M., Petoukhov S. Mathematics of Bioinformatics: Theory, Methods and Applications

Подождите немного. Документ загружается.

GRAPH THEORY PRELIMINARIES AND NETWORK TOPOLOGY 143

()

−

(6.6)

where λ is a constant.

Most networks in the real world, however, have degree distributions very

different from this. Most are highly right - skewed, meaning that a large major-

ity of nodes are of low degree, but a small number, known as hubs , are of

high degree. Some networks, notably the Internet, the World Wide Web, and

some social networks are found to have degree distributions that approxi-

mately follow a power law:

Pk k

()

≈

−λ

(6.7)

where λ is a constant. Such networks, called scale - free networks , have attracted

particular attention for their structural and dynamical properties.

Clustering Coefﬁ cient The clustering coefﬁ cient is a measure that gives

insight into the local structure of a network. Mathematically, we deﬁ ne the

clustering coefﬁ cient as follows. Let G = ( V , E ) be a graph with a set of vertices,

V , and a set of edges, E . An edge e

connects vertex i with vertex j . The neigh-

borhood N of vertex υ

is deﬁ ned as its immediately connected neighbors, as

follows:

NeEeE

i i ij ji

= ∈ ∨ ∈

{}

u :

(6.8)

Let k

be the degree (number of vertices) in its neighborhood N

. The clustering

coefﬁ cient C

for a vertex υ

is deﬁ ned as

Ne E

jk ijk

{}

−

()

∈∈

:, ;uu

(6.9)

representing the proportion of links between the vertices within its neigh-

borhood divided by the number of links that could possibly exist between

them.

For a directed graph, e

is distinct from e

, and therefore for each neighbor-

hood N

there are k

( k

− 1) links that could exist among the vertices within

the neighborhood ( k

is the total (in + out) degree of the vertex). An undi-

rected graph has the property that e

and e

are considered identical. Therefore,

if a vertex υ

has k

neighbours, edges could exist among the vertices within

the neighborhood. Thus, the clustering coefﬁ cient for undirected graphs can

be deﬁ ned as

Ne E

jk ijk

{}

−

()

∈∈

:, ;uu

(6.10)

144 BIOLOGICAL NETWORKS AND GRAPH THEORY

For a vertex that is a part of a fully interconnected graph, C

= 1; for a vertex

where none of its neighbors are interconnected, C

= 0. The clustering coefﬁ -

cient for the entire system is given by Watts and Strogatz (1998) as the average

of the clustering coefﬁ cient for each vertex:

∑

(6.11)

A graph is considered small - world if its average clustering coefﬁ cient is

signiﬁ cantly higher than a random graph constructed on the same vertex set.

For all metabolic networks available, the average clustering coefﬁ cient assem-

bles a power - law form as

−λ

(6.12)

This suggests the existence of a hierarchy of vertices with different degrees of

modularity.

Subgraphs and Motifs In graph theory, a subgraph of a graph G is a graph

whose vertex set is a subset of that of G , and whose adjacency relation is a

subset of that of G restricted to this subset. A subgraph H is a spanning sub-

graph , or factor , of a graph G if it has the same vertex set as G . We say that

H spans G .

In genetics, a sequence motif is a nucleotide or aminoacid sequence pattern

that is widespread and has, or is conjectured to have, biological signiﬁ cance.

For proteins, a sequence motif is distinguished from a structural motif , a motif

formed by the three - dimensional arrangement of amino acids, which may not

be adjacent.

A number of complex biological networks were recently found to contain

network motifs . In proteins, structure motifs usually consist of just a few ele-

ments; for example, a helix – turn – helix has just three. Note that while the

spatial sequence of elements is the same in all instances of a motif, they may

be encoded in any order within the underlying gene. Protein structural motifs

often include loops of variable length and unspeciﬁ ed structure, which in

effect create the “ slack ” necessary to bring together in space two elements

that are not encoded by immediately adjacent DNA sequences in a gene.

Note also that even when two genes encode secondary structural elements

of a motif in the same order, they may specify somewhat different sequences

of amino acids.

Centrality and Essentiality Within graph theory and network analysis, there

are various measures of the centrality of a vertex within a graph that deter-

mine the relative importance of a vertex within the graph. There are four

measures of centrality that are widely used in network analysis: degree central-

ity, closeness, betweenness, and eigenvector centrality.

GRAPH THEORY PRELIMINARIES AND NETWORK TOPOLOGY 145

Degree centrality is the most basic of the centrality measures. It is deﬁ ned

as the number of links incident upon a node (i.e., the number of ties that a

node has). Degree is often interpreted in terms of the immediate risk of a node

for catching whatever is ﬂ owing through the network (such as a virus, or some

information). If the network is directed, we usually deﬁ ne two separate mea-

sures of degree centrality, in - degree and out - degree. In - degree is a count of the

number of ties directed to the node, and out - degree is the number of ties that

the node directs to others. For a graph G : = ( V , E ) with n vertices, the degree

centrality C

( υ ) for vertex υ is

()

−

deg

(6.13)

Closeness is a centrality measure of a vertex within a graph. Vertices that

are “ shallow ” to other vertices (i.e., those that tend to have short geodesic

distances to other vertices within the graph) have higher closeness. Closeness

is preferred in network analysis to mean shortest path length, as it gives higher

values to more central vertices, and so is usually positively associated with

other measures, such as degree. It is deﬁ ned as the mean geodesic distance

(i.e., the shortest path) between a vertex υ and all other vertices reachable

from it:

()

−

∈

∑

(6.14)

where n > 1 is the size of the network ’ s connectivity component V reachable

from υ . Closeness can be regarded as a measure of how long it will take infor-

mation to spread from a given vertex to other reachable vertices in the network.

Betweenness is a centrality measure of a vertex within a graph. Vertices that

occur on many shortest paths between other vertices have higher betweenness

than those that do not. For a graph G : = ( V , E ) with n vertices, the between-

ness C

( υ ) for vertex υ is

()

≠≠

∑

(6.15)

where σ

is the number of shortest geodesic paths from s to t , and σ

( υ ) is the

number of shortest geodesic paths from s to t that pass through a vertex υ .

This may be normalized by dividing through the number of pairs of vertices

not including υ , which is ( n − 1)( n − 2). Calculating the betweenness and close-

ness centralities of all the vertices in a graph involves calculating the shortest

paths between all pairs of vertices on a graph.

Eigenvector centrality is a measure of the importance of a node in a network.

It assigns relative scores to all nodes in the network based on the principle

146 BIOLOGICAL NETWORKS AND GRAPH THEORY

that connections to high - scoring nodes contribute more to the score of the

node in question than do equal connections to low - scoring nodes.

Let x

denote the score of the i th node. Let A

be the adjacency matrix of

the network. Hence, A

= 1 if the i th node is adjacent to the j th node, and

= 0 otherwise. More generally, the entries in A can be real numbers repre-

senting connection strengths. For the i th node, let the centrality score be

proportional to the sum of the scores of all nodes that are connected to it.

Hence,

xxAx

jMi

ij j

∈

()

∑∑

λλ

(6.16)

where M ( i ) is the set of nodes that are connected to the i th node, N is the total

number of nodes, and λ is a constant. In vector notation this can be

rewritten

XAX AXX==

λ,

(6.17)

In general, there will be many different eigenvalues λ for which an eigen-

vector solution exists. However, the additional requirement that all the entries

in the eigenvector be positive implies (by the Perron – Frobenius theorem) that

only the greatest eigenvalue results in the desired centrality measure. The i th

component of the related eigenvector then gives the centrality score of the i th

node in the network. Power iteration is one of many eigenvalue algorithms

that may be used to ﬁ nd this dominant eigenvector.

The network model is a database model conceived as a ﬂ exible way of

representing objects and their relationships. Where the hierarchical model

structures data as a tree of records, with each record having one parent record

and many children, the network model allows each record to have multiple

parent and child records, forming a lattice structure. Next, we describe three

models that can be seen as network paradigms.

Random Network Graph theory focused initially on regular graphs. Since the

1950s, large networks with no apparent design principles were described by

random graphs as the simplest model of a complex network (Bollobas, 1985 ).

A random network is obtained by starting with a set of n vertices and adding

edges between them at random. Different random graph models produce dif-

ferent probability distributions on graphs. Most commonly studied is the

Erd ö s – R é nyi model (Erd ö s and R é nyi, 1960 ), denoted G ( n , p ), in which every

possible edge occurs independently with probability p . This process generates

a graph with approximately pN ( N − 1)/2 randomly distributed edges. A closely

related model, denoted G ( n , M ), assigns equal probability to all graphs with

exactly M edges. The latter model can be viewed as a snapshot at a particular

GRAPH THEORY PRELIMINARIES AND NETWORK TOPOLOGY 147

time of the random graph process, which is a stochastic process that starts with

n vertices and no edges and at each step adds one new edge chosen uniformly

from the set of missing edges. The theory of random graphs studies typical

properties of random graphs, those that hold with high probability for graphs

drawn from a particular distribution. For example, we might ask, for a given

value of n and p , what the probability is that G ( n , p ) is connected. In studying

such questions, researchers often concentrate on the asymptotic behavior of

random graphs — the values that various probabilities converge to as n grows

very large.

Scale - Free Network A scale - free network is a network whose degree distribu-

tion follows a power law, at least asymptotically. That is, the fraction P ( k ) of

nodes in the network having k connections to other nodes goes for large values

of k as P ( k ) ∼ k

− γ

, where γ is a constant whose value is typically in the range

2 < γ < 3, although occasionally it may lie outside these bounds. Scale - free

networks are noteworthy because many empirically observed networks appear

to be scale - free, including the World Wide Web, protein networks, citation

networks, and some social networks.

The power - law distribution strongly inﬂ uences the network topology. It

turns out that the major hubs are closely followed by smaller ones. These, in

turn, are followed by other nodes with an even smaller degree, and so on.

This hierarchy allows for a fault - tolerant behavior. Since failures occur at

random and the vast majority of nodes are those with small degree, the likeli-

hood that a hub would be affected is almost negligible. Even if such an event

occurs, the network will not lose its connectedness, which is guaranteed by

the remaining hubs. On the other hand, if we choose a few major hubs and

take them out of the network, it simply falls apart and is turned into a set

of rather isolated graphs. Thus, hubs are scale - free networks. Another impor-

tant characteristic of scale - free networks is the clustering coefﬁ cient distribu-

tion, which decreases as the node degree increases. This distribution also

follows a power law. That means that the low - degree nodes belong to very

dense subgraphs and those subgraphs are connected to each other through

hubs.

Hierarchical Network A Hierarchical network is a network topology in which

a central “ root ” node (the top level of the hierarchy) is connected to one or

more other nodes that are one level lower in the hierarchy (i.e., the second

level) with a point - to - point link between each of the second - level nodes and

the top - level central root node. At the same time, each of the second - level

nodes that are connected to the top - level central root node will also have one

or more other nodes that are one level lower in the hierarchy (i.e., the third

level) connected to it, also with a point - to - point link, the top - level central root

node being the only node that has no other node above it in the hierarchy.

(The hierarchy of the tree is symmetrical.)

148 BIOLOGICAL NETWORKS AND GRAPH THEORY

6.3 MODELS OF BIOLOGICAL NETWORKS

A network model can be used to present a synthetic view of the current state

of biological knowledge on a given network and can be used to simulate the

process it represents. A biological network model allows a variety of analyses,

ranging from statistical properties of its topology to predictions of features of

its dynamic behavior, or even prediction of cellular phenotypes. If these pre-

dictions can be compared with experimental results, they should allow either

conﬁ rmation of the model ’ s accuracy or, better yet, correction of the model.

Several mathematical framework structures, such as a system of differential

equations and Boolean networks for biological networks are discussed in this

section.

Gene Regulatory Networks

A gene regulatory network (GRN) or genetic regulatory network is a collection

of dna segments in a cell which interact with each other and with other sub-

stances in the cell, thereby governing the rates at which genes in the network

are transcribed into m rna . As we see here, a GRN involves interactions among

DNA, RNA, proteins, and other molecules. In general, each mRNA molecule

goes on to make a speciﬁ c protein (or set of proteins). These mRNA molecules

and proteins interact with each other with various degrees of speciﬁ city. Some

diffuse around the cell. Others are bound to cell membranes, interacting with

molecules in the environment. These molecules and their interactions com-

prise a gene regulatory network.

A gene regulatory network can be viewed as a directed graph: a pair ( V ,

E ), where V is a set of vertices (genes) and E a set of directed edges (regula-

tory inﬂ uences), and a pair ( A , B ) of vertices, where A is the source vertex and

B the target vertex. A gene A directly regulates a gene B if the protein that is

encoded by A is a transcription factor for gene B . This simple model can be

improved by adding an additional attribute on vertices or edges: for example,

“ + ” or “ − ” labels on edges may indicate positive or negative regulatory

inﬂ uence.

Genes can be viewed as nodes in the network, with input being proteins

such as transcription factors, and outputs being the level of gene expression.

The node itself can also be viewed as a function that can be obtained by com-

bining basic functions upon the inputs (in the Boolean network described

below these are Boolean functions, typically AND, OR, and NOT). These

functions have been interpreted as performing a type of information process-

ing within the cell, which determines cellular behavior. The basic drivers within

cells are concentrations of some proteins, which determine both spatial (loca-

tion within the cell or tissue) and temporal (cell cycle or developmental stage)

coordinates of the cell, as a kind of “ cellular memory. ”

MODELS OF BIOLOGICAL NETWORKS 149

Mathematical models of GRNs have been developed to capture the behav-

ior of the system being modeled, and in some cases generate predictions cor-

responding to experimental observations. In other cases, models have proven

to make accurate novel predictions, which can be tested experimentally, thus

suggesting new approaches to explore in an experiment that sometimes

wouldn ’ t be considered in the design of the protocol of an experimental labo-

ratory. The most common modeling technique involves the use of coupled

ordinary differential equations. Several other promising modeling techniques

have been used, including Boolean networks, Petri nets, Bayesian networks,

and graphical Gaussian models.

Typically, a gene regulatory network is modeled as a system of rate equa-

tions describing the reaction kinetics of the constituent parts and governing

the evolution of mRNA and protein concentrations. Suppose that our regula-

tory network has N nodes, and let S

( t ), S

( t ), … , S

( t ) represent the concen-

trations of the N corresponding substances at time t . Then the temporal

evolution of the system can be described approximately by

fStS S t

() ( ) ()

()

2,,,…

(6.18)

where the functions f

express the dependence of S

on the concentrations of

other substances present in the cell. The functions f

are ultimately derived

from basic principles of chemical kinetics or simple expressions derived from

these (e.g., Michaelis – Menten enzymatic kinetics). Hence, the functional forms

of the f

are usually chosen as low - order polynomials that serve as an ansatz

for the real molecular dynamics. Such models are then studied using the math-

ematics of nonlinear dynamics.

By solving for the ﬁ xed point of the system,

= 0

(6.19)

for all j , one obtains (possibly several) concentration proﬁ les of proteins and

mRNAs that are theoretically sustainable (although not necessarily stable).

Steady states of kinetic equations thus correspond to potential cell types, and

oscillatory solutions to equation (6.19) correspond to naturally cyclic cell

types. Mathematical stability of these attractors can usually be characterized

by the sign of higher derivatives at critical points and then correspond to the

biochemical stability of the concentration proﬁ le. Critical points and bifurca-

tions in the equations correspond to critical cell states in which small state or

parameter perturbations could switch the system between one of several

stable differentiation fates. Trajectories correspond to the unfolding of biologi-

cal pathways and transients of the equations to short - term biological events.

For a more mathematical discussion, see the reference section for articles on

nonlinearity, dynamical systems, bifurcation theory, and chaos theory.

150 BIOLOGICAL NETWORKS AND GRAPH THEORY

The following example illustrates how a Boolean network can model a

GRN together with its gene products (the outputs) and the substances from

the environment that affect it (the inputs). Stuart Kauffman was among the

ﬁ rst biologists to use the metaphor of Boolean networks to model genetic

regulatory networks (Kauffman, 1993 ).

• Each gene, each input, and each output is represented by a node in a

directed graph in which there is an arrow from one node to another if

and only if there is a causal link between the two nodes.

• Each node in the graph can be in one of two states: on or off.

• For a gene, “ on ” corresponds to the gene being expressed; for inputs and

outputs, “ on ” corresponds to the substance being present.

• Time is viewed as proceeding in discrete steps. At each step, the new state

of a node is a Boolean function of the prior states of the nodes with

arrows pointing toward it.

The validity of the model can be tested by comparing simulation results

with time - series observations. Continuous network models of GRNs are an

extension of the Boolean networks described above. Nodes still represent

genes and connections between them, regulatory inﬂ uences on gene expres-

sion. Genes in biological systems display a continuous range of activity levels,

and it has been argued that using a continuous representation captures several

properties of gene regulatory networks not present in the Boolean model

(Vohradsky, 2001 ).

Recent experimental results (Blake et al., 2003 ; Elowitz et al., 2002 ) have

demonstrated that gene expression is a stochastic process. Thus, many authors

are now using stochastic formalism, after the work of Arkin and McAdams

(1998) . Works on single gene expression (Raser and O ’ Shea, 2005 ) and small

synthetic genetic networks (Elowitz and Leibler , 2000 ; Gardner et al., 2000 ),

such as the genetic toggle switch of Tim Gardner and Jim Collins, provided

additional experimental data on the phenotypic variability and the stochastic

nature of gene expression. The ﬁ rst versions of stochastic models of gene

expression involved only instantaneous reactions and were driven by the

Gillespie algorithm (Gillespie, 1976 ).

Since some processes, such as gene transcription, involve many reactions

and could not be modeled correctly as an instantaneous reaction in a single

step, it was proposed to model these reactions as single - step multiple delayed

reactions, to account for the time it takes for the entire process to be com-

pleted (Roussel and Zhu, 2006 ).

From here a set of reactions was proposed (Ribeiro et al., 2006 ) that allow

generating GRNs. These are then simulated using a modiﬁ ed version of the

Gillespie algorithm. It can simulate multiple time - delayed reactions.

For example, basic transcription of a gene can be represented by the fol-

lowing single - step reaction (RNAP is the RNA polymerase, RBS is the RNA

ribosome binding site, and Pro

is the promoter region of gene i ):

MODELS OF BIOLOGICAL NETWORKS 151

RNAP Pro Pro RBS RNAP+⎯→⎯⎯

()

K base

ii ii i

ττ τ

11 2

(6.20)

A recent work proposed a simulator (SGNSim, Stochastic Gene Networks

Simulator) (Ribeiro and Lloyd - Price, 2007 ) that can model GRNs where tran-

scription and translation are modeled as multiple time - delayed events, and its

dynamics is driven by a stochastic simulation algorithm able to deal with mul-

tiple time - delayed events. The time delays can be drawn from several distribu-

tions and the reaction rates from complex functions or from physical

parameters. SGNSim can generate ensembles of GRNs within a set of user -

deﬁ ned parameters, such as topology. It can also be used to model speciﬁ c

GRNs and systems of chemical reactions. Genetic perturbations such as gene

deletions, gene overexpression, insertions, and frame shift mutations can be

modeled as well.

The GRN is created from a graph with the desired topology, imposing in -

degree and out - degree distributions. Gene promoter activities are affected by

other gene expression products that act as inputs, in the form of monomers or

combined into multimers and set as direct or indirect. Next, each direct input

is assigned to an operator site and different transcription factors can be

allowed, or not, to compete for the same operator site, while indirect inputs

are given a target. Finally, a function is assigned to each gene, deﬁ ning the

gene ’ s response to a combination of transcription factors (promoter state). The

transfer functions (i.e., how genes respond to a combination of inputs) can be

assigned to each combination of promoter states as desired.

In other recent work, multiscale models of gene regulatory networks have

been developed that focus on synthetic biology applications. Simulations have

been used that model all biomolecular interactions in transcription, transla-

tion, regulation, and induction of gene regulatory networks, guiding the design

of synthetic systems (Kaznessis, 2007 ).

Protein Interaction Networks

A key feature of the biological organization in all organisms is the tendency

of proteins with a common function to associate physically via stable protein -

to - protein interactions (PPIs) to form larger macromolecular assemblies.

These protein complexes are often linked together by extended networks of

weaker, transient PPIs, to form interaction networks that integrate pathways

mediating the major cellular processes. Consequently, the cell is viewed

increasingly as an assembly of interconnected functional modules that inte-

grate and coordinate the cell ’ s major biochemical activities and responses to

external and intrinsic signals. Given their broad signiﬁ cance, systematic analy-

ses of PPI networks have become a major experimental focus.

One of the ultimate goals of biological networks is to improve our under-

standing of the processes and events that lead to pathologies and diseases. The

analysis of biological pathways can provide a more efﬁ cient way of browsing

through biologically relevant information and offer a quick overview of under-

lying biological processes.

152 BIOLOGICAL NETWORKS AND GRAPH THEORY

Protein interactions help put biological processes in context, allowing

researchers to characterize speciﬁ c pathway biology. Hence, an analysis of

biological networks is crucial for an understanding of complex biological

systems and diseases. The analysis of protein interaction networks is an impor-

tant and very active research area in bioinformatics and computational biology

(Dyke, 1988 ).

Metabolic Networks

Metabolic networks comprise the chemical reactions of metabolism as well

as the regulatory interactions that guide these reactions. With the sequencing

of complete genomes, it is now possible to reconstruct the network of bio-

chemical reactions in many organisms, from bacteria to human beings. Several

of these networks are available online: Kyoto Encyclopedia of Genes and

Genomes, (a database resource for linking genome to life and the environment

developed by the Kanehisa Laboratories in the Kyoto University Bioinformatics

Center and the Human Genome Center of the University of Tokyo as part of

their research activities); EcoCyc, a scientiﬁ c database for the bacterium

Escherichia coli K - 12 MG1655 comprising literature - based descriptions of the

entire genome and of transcriptional regulation, transporters, and metabolic

pathways; and BioCyc, a collection of 376 Pathway/Genome Databases,

each of which describes the genome and metabolic pathways of a single

organism.

In the ﬁ nal analysis, the biological function of life is determined by the

organizational form of atoms and molecules, determined especially by the

conﬁ rmation changes and movements of proteins and nucleic acid molecules.

The self - organization phenomena are observed from the molecular to the cel-

lular to the ecological level. Biological networks are dynamic and dependent

on the cell environment. Based on networks, we are able to understand how

individual components are integrated together into a complete system to

perform some biological functions. As a fundamental element of the network,

the protein – protein interaction should be deduced by using the sequential,

structural, and evolutionary information on individual proteins.

6.4 CHALLENGES AND PERSPECTIVES

In network models, the relevant components in a system are identiﬁ ed as

vertices or nodes. The interactions between vertices are represented as edges

or links. A major challenge consists of identifying with reasonable accuracy

the complex molecular interactions that take place at different levels, from

genes to metabolites through proteins. Although an understanding of the

interactions of proteins continues to be important, an understanding of a

system ’ s structure and dynamics is the latest trend. The approach advocated

in systems biology requires a shift in our notion of what to look for in