Bonchev D., Rouvray D.H. (editors) Complexity in Chemistry, Biology, and Ecology
Подождите немного. Документ загружается.
The Circle That Never Ends: Can Complexity be Made Simple? 151
66. D. C. Mikulecky, E. G. Huf, and S. R. Thomas, Biophys. J. 25, 87-105 (1979).
67. Mintz, S. R. Thomas, and D. C. Mikulecky, J. Theor. Biol. 123, 1-19 (1986).
68. E. Mintz, S. R. Thomas, and D. C. Mikulecky, J. Theor. Bio.l 123, 21-34 (1986).
69. L. Peusner, D. C. Mikulecky, S. R. Caplan, and B. Bunow, J. Chem. Phys. 83, 5559-
5566 (1985).
70. D. E. Oken, S. R. Thomas, and D. C. Mikulecky, Kidney Int. 19, 359-373 (1981).
71. R. L. Seither, D. F. Trent, D. C. Mikulecky, T. J. Rape, and I. D. Goldman, J. Biol.
Chem. 264, 17016-17023 (1989).
72. R. L. Seither, D. F. Trent, D. C. Mikulecky, T. J. Rape and I. D. Goldman, J. Biol.
Chem. 266, 4112-4118 (1991).
73. R. L. Seither, D. Hearne, D. Trent, D. C. Mikulecky, and I. D. Goldman, Computers
Math. Appl. 20, 87-101 (1990).
74. D. B. Talley, J. P. Ornato, and A. M. Clarke, Biomed. Inst. Tech. July/August, 283-288
(1990).
75. K. M. Thakker, J. H. Wood, and D. C. Mikulecky, Comp. Prog. Biomed. 15, 61-72
(1982).
76. K. M. Thakker and D. C. Mikulecky, Math. Modeling. 7, 1181-1186 (1985).
77. D. Walz, Biochim. Biophys. Acta 1019, 171-224 (1990).
78. D. Walz, S. R. Caplan, D. R. L. Scriven, and D. C. Mikulecky, Methods of Bioelectro-
chemical Modeling, in Treatise on Bioelectrochemistry, G Millazzo (ed.), Birkhauser
(1992).
79. J. C. White, J. Biol. Chem. 254, 10889-10895 (1979).
80. J. C. White, Bull. Math. Biol. 48, 353-380 (1986).
81. J. C. White and D. C. Mikulecky, Pharmacol. Ther. 15, 251-291 (1981).
82. M. B. Cable, J. J. Feher, and F. N. Briggs, Biochem. 24, 5612-5619 (1985).
83. J. J. Feher, J. Biol. Chem. 257, 10191-10199 (1982).
84. J. J. Feher, C. S. Fullmer, and R. H. Wasserman, Amer. J. Physiol. 262, C517-C526
1992.
85. M. L. Fidelman and S. Mierson, Am. J. Physiol. 257, G475-G487 (1989).
86. S. Mierson and M. L. Fidelman, The Role of Epithelial Ion Transportin TasteTransduc-
tion: A Network Thermodynamic Model, in Advances in Mathematics and Computers
in Medicine, Vol. 6, DC Mikulecky and M Witten (eds.), Pergamon Press (1992) p.
119-134.
87. M. Fidelman and D. C. Mikulecky, Am. J. Physiol. 250, C978-C991 (1986).
88. M. L. Fidelman and D. C. Mikulecky, J. Theor. Biol.
130, 73-93 (1988).
89. P. Cruziat and R. Thomas, Agronomie 8, 613-623., 1988.
90. L. J. Goldstein and E. B. Rypins, Comp. Methods. Prog. Biomed. 29, 161-172
(1989).
91. J. C. Horno, F. Gonzalez-Fernandez, A. Hayas, and F. Gonzalez-Caballero, Biophys.
J. 55, 527-535 (1989).
152 Chapter 3
92. J. C. Horno, F. Gonzalez-Fernandez, A. Hayas, and F. Gonzalez-Caballero, J. Memb.
Sci. 42, 1-12 (1989).
93. E. G. Huf and J. R. Howell, J. Memb. Biol. 15, 47-66 (1974).
94. E. G. Huf and D. C. Mikulecky, J. Theor. Biol. 112, 193-220 (1985).
95. E. G. Huf and D. C. Mikulecky, Am. J. Physiol. 250, F1107-F1118 (1986).
96. J. M. May and D. C. Mikulecky, J. Biol. Chem. 258, 4771-4777 (1983).
97. J. M. May and D. C. Mikulecky, J. Biol. Chem. 257, 11601-11608 (1982).
98. D. C. Mikulecky and M. Thellier.C. R. Acad. Sci. III 316, 1399-1403 (1993).
99. J. Prideaux,. Acta Biotheoretica 44, 219-233 (1996).
100. R. Abraham and C. D. Shaw, Dynamics: The Geometry of Behavior; Part 1, Periodic
Behavior, Aerial Press, Santa Cruz, CA (1982).
101. R. Abraham and C. D. Shaw, Dynamics: The Geometry of Behavior; Part 2, Chaotic
Behavior, Aerial Press, Santa Cruz, CA (1983).
102. R. Abraham and C. D. Shaw, Dynamics: The Geometry of Behavior; Part 3, Global
Behavior, Aerial Press, Santa Cruz, CA (1984).
103. R. Abraham and C. D. Shaw, Dynamics: The Geometry of Behavior; Part 4, Bifurcation
Behavior, Aerial Press, Santa Cruz, CA (1988).
104. R. Abraham, R. and C. D. Shaw, Dynamics: A Visual Introduction, in Self-Organizing
Systems: The Emergence of Order, FE Yates (ed.), Plenum Press, NY (1987).
105. M. Arbib and E. G. Manes, Arrows, Structures, and Functors: The Categorical Im-
perative, Academic Press, New York (1975) pp. 93-106.
106. R. Abraham and J. E. Marsden, Foundations of Mechanics, Benjamin/Cummings,
Reading, MA (1978).
107. H. Branin Jr, The Algebraic-Topological Basis for Network Analogies and the Vector
Calculus, in: Proceedings of the Symposium on Generalized Networks, J Fox, Ed,
Polytechnic Press, Brooklyn, NY (1966) pp. 453-491.
108. D. C. Mikulecky, Comput. Chem. 25, 369-392 (2001).
109. D. H. Tellegen, Phillips Res. Rep. 7, 259-269 (1952).
110. B. Callen, Thermodynamics, Wiley, NY (1960).
111. G. N. Hatsapoulos and J. H. Keenan, Principles of General Thermodynamics, Wiley,
NY (1965).
112. Prigogine and R. Defay, Chemical Thermodynamics
, Longmans Green, London
(1965).
113. L. Tisza, Generalized Thermodynamics, MIT Press, Cambridge, MA (1977).
114. Truesdell, Rational Thermodynamics, McGraw-Hill, NY (1969).
115. S. R. deGroot and P. Mazur, Non-Equilibrium Thermodynamics, North-Holland,
Amsterdam (1962).
116. Fitts, Non-Equilibrium Thermodynamics, McGraw-Hill, NY (1962).
117. I .Prigogine, Thermodynamics of Irreversible Processes, Wiley, NY (1961).
118. S. R. Caplan and A. Essig, Bioenergetics and Linear Non-Equilibrium Thermodynam-
ics: The Steady State, Harvard, Cambridge, MA (1983).
The Circle That Never Ends: Can Complexity be Made Simple? 153
119. C. Mikulecky, WA Wiegand, and JS Shiner, J. Theoret. Biol. 69, 47l-5l0 (1977).
120. L. O. Chua, IEEE Trans. Cir. Theory CT-18, 507-519 (1961).
121. R. Kirchhoff, On the Solution of the Equations Obtained from the Investigation of the
Linear Distribution of Galvanic Currents, 1847, English translation in Graph. Theory
1736-1936, N. L. Biggs, E. K. Lloyd, and R. J. Wilson (eds.), Oxford (1976).
122. D. C. Mikulecky and S. R. Thomas, J. Franklin Inst. 308, 309-325 (1979).
123. P. W. Tuinenga, SPICE: A Guide to Circuit Simulation and Analysis Using PSPICE.
Prentice Hall, NJ (1988).
124. P. M. DeRusso, R. J. Roy, and C. M. Close, State Variables for Engineers, Wiley, NY
(1965).
125. L. O. Chua, Introduction to Nonlinear Network Theory, McGraw-Hill, NY (1969).
126. L. O. Chua and P. Lin, Computer -Aided Analysis of Electronic Circuits: Algorithms
and Computational Techniques, Prentice-Hall, Englewood Cliffs, NJ (1975).
127. L. O. Chua and Y. Lam, IEEE Trans. Cir. Theory CT-20, 370-381 (1973).
128. D. C. Mikulecky, Math. Comp. Modeling 19, 99-118 (1994).
129. S. R .Thomas and D. C. Mikulecky, Am. J. Physiol. 235, F638-F648 (1978).
130. L. Onsager, Phys. Rev. 37, 405-426 (1931).
131. Onsager, Phys. Rev. 38, 2265-2279 (1931).
132. S. J. Mason and H. J. Zimmermann, Electronic Circuits, Signals, and Systems, Wiley,
NY (1960).
133. Kedem and A. Katchalsky, Trans. Faraday Soc. 59, 1918-1930 (1963).
134. O. Kedem and A. Katchalsky, Trans. Faraday. Soc. 59, 1931-1940 (1963).
135. O. Kedem and A. Katchalsky, Trans. Faraday. Soc. 59, 1941-1953 (1963).
136. B. Callen, Asymmetry Interpretation of Thermodynamics, in Foundations of Contin-
uum Thermodynamics, J. J. D. Domingos, M. N. R. Nina, and J. H. Whitelaw (eds.),
Wiley, NY (1973) pp. 61-79. (See comment by L. Tisza, p 79).
137. O. Kedem and S. R. Caplan, Trans. Faraday. Soc. 61, 1897-1911 (1965).
138. D. G. Miller, Chem. Revs. 60, 15 (1960).
139. D. G .Miller, The Experimental Verification of the Onsager Reciprocal Relations,
in Transport Phenomena in Fluids, H. J. M. Hanley (ed.), Dekker, NY (1969) pp.
377-432.
140. O. Kedem and A. Katchalsky, Bioch. Biophys. Acta 27, 229-246 (1958).
141. O. Kedem and A. Katchalsky, J. Gen. Physio. 45, 143-179 (1961).
142. A. DeSimone and S. R. Caplan, Biochem 12, 3032-3039 (1973).
143. A. DeSimone and S. R. Caplan,
J. Theo. Biol. 39, 523-544 (1973).
144. S. W. Kercel and D. C. Mikulecky, Why do people behave religiously?
Evolution and Cognition, in press.
145. J. Barwise and L. Moss, Vicious Circles, CSLI Publications, Stanford, CA (1996).
Chapter 4
GRAPHS AS MODELS OF LARGE-SCALE
BIOCHEMICAL ORGANIZATION
Pau Fern´andez
ICREA-Complex Systems Lab, Universitat Pompeu Fabra (GRIB), Dr Aiguader 80,
08003 Barcelona, Spain
Ricard V. Sol´e
ICREA-Complex Systems Lab, Universitat Pompeu Fabra (GRIB), Dr Aiguader 80,
08003 Barcelona, Spain
Santa Fe Institute, 1399 Hyde Park Road, Santa Fe NM 87501, USA
1. Introduction
Cells have many different types of molecules interacting in space and
time to produce the coordinated behavior we observe. They are a beautiful
example of complex systems, which are difficult to study in their entirety
due to the overwhelming number of components they have. However, al-
lowing for a certain degree of simplification, one can always start looking at
these systems by simply measuring what pairs of units in these multicom-
ponent systems engage in some form of interaction. This crude, discrete
information can be a very informative first step towards an understanding
of cells as an integrated whole, and provides the most simple global picture
one can obtain of these systems: their underlying network.
Networks pervade biology, and they are present at many different spatial
and temporal scales, from molecular biology to large-scale evolution. By
understanding the possible scenarios responsible for the emergence of their
architecture, great insight can be gained on their evolutionary origins [1].
As a first example, we can consider the case of protein molecules. On the
one hand, they can be viewed simply as the units on top of which a complex
system like the cell is built. But on the other hand, they count as complex
systems in their own right, given the complexity of their structure and
folding process. A three-dimensional structure of a linear biopolymer like
a protein can, in fact, be roughly described by its contact structure, that is,
by the list of all pairs of monomers that are spatial neighbors, given some
155
156 Chapter 4
A
BC
Figure 4.1. (A) A fragment of the structure for the human blood coagulation factor Xa (pdb
1xka); (B) The associated contact matrix. Black dots represent above threshold proximity
between alpha carbons in the sequence, which are arranged as rows and columns in the
order of the backbone; (C) The associated graph in which nodes represent amino acids, and
links represent contact between them.
cut-off distance. Figure 4.1A shows the structure of a portion of a protein,
and Figure 4.1B shows its contact matrix, the simplest way to quickly view
the contact pairs. In this matrix, rows and columns represent each amino
acid in the sequence, and a square is drawn black when the corresponding
amino acids are in close proximity in the three dimensional structure.
Using this matrix, one can actually construct a network, shown in Figure
4.1C, in which the vertices (or nodes) representamino acids, and an edge (or
link) is present whenever these two amino acids are in contact. A network
such as this, as we will see throughout the chapter, can give us many hints
about the system it is representing. To start with, the network in Figure
4.1C tells us that this protein is modular. Although we already see that
this protein is modular from the examination of its structure, the important
point to emphasize is that the network alone mirrors this modularity, and
this is especially relevant whenever we don’t have a clear picture of the
system for which the network was measured.
Many other properties are in fact measurable just from the networks,
which describe other equally interesting features. Applying various con-
cepts which can be defined on graphs, we can examine the networks of
Graphs as Models of Large-Scale Biochemical Organization 157
different systems trying to understand their overall features, and we can
try to make sense of their connection patterns. In this chapter we will see
how some of the properties of complex systems can be approached through
the study of the properties of their corresponding networks, the so-called
complex networks.
2. Basic Properties of Random Graphs
A graph G is defined by a set of N vertices (or nodes) V = {v
1
,
v
2
, ...,v
N
} and a set of L edges (or links) E = {e
1
, e
2
, ...,e
L
}, which
connect pairs of vertices. Depending on the existence of directionality in
the edges, graphs can be either directed or undirected. Figure 4.2 depicts
two graphs, one directed and one undirected, using arrows as a represen-
tation of directed edges. A certain graph G can, by this simple definition,
represent the structure of a given system, in which, nodes correspond to
units and edges to interactions. In the following, we will be concerned with
graphs in which edges have no weights attached, although many interesting
results exist for weighted graphs.
The number of edges k that arrive to vertex v is called degree, and it
is divided, in the case of directed graphs into k
i
, the in-degree, and k
o
,
Figure 4.2. (A) An example of undirected graph G with V ={a,b,c,d,e} and E ={(a, c), (b,
c), (b,d), (b,e), (d,e)}; (B) Example of a directed network with the same V and E = {(a,b),
(b,c), (c,a), (d,b), (d,e)}; (C) A node with degree k = 5 and indegree k
i
= 2 and outdegree
k
o
= 3; (D) An undirected graph with two components.
158 Chapter 4
the out-degree, with k = k
i
+ k
o
, as shown in Figure 4.2C. The average
degree is, then, z =
k
= 2L/N , since every edge is attached to two dif-
ferent vertices. The distance between two vertices in the graph d(v
i
, v
j
)is
defined as the shortest number of links that have to be crossed to reach v
j
from v
i
, and since we are not dealing with weighted edges, it is an inte-
ger number. As an example, in the graph of Figure 4.2A, d(a, e) = 3 and
d(c, d) = 2.
A random graph is a graph in which the pairs of connected vertices
have been selected uniformly at random between all the possible pairs
of vertices. Basically, this is equivalent to consider that every edge in
the graph is present with an independent probability p, and absent with
probability 1 − p. In fact, there is a whole ensemble of graphs for a
single value of p, and random graph theory deals with the average
properties of these ensembles. The average number of edges in these
graphs is thus
L
=
N (N−1)
2
p and accordingly, the average degree is, then
z =
2
L
N
≈ Np, the last equality being valid only for large N . This kind
of random graph were first studied by Erd¨os and R´enyi, and many of their
average properties are have been solved analytically [2] in the limit for
large N . Random graphs are important because they represent the null
hypothesis about systems that can be modeled as graphs. The study of their
properties is thus crucial to understand real graphs, since the comparison
between random graphs and real ones tells us what is relevant about the
latter.
2.1. Degree distribution
One of the first interesting aggregate measures to consider is the degree
distribution, P(k)orp
k
. This function describes the graph by giving the
fraction of nodes that have a certain degree k. As an example, we can
calculate p
k
for a random graph, given the probability of linking two of its
vertices, p, which is
p
k
=
N − 1
k
p
k
(1 − p)
N −1−k
≈
z
k
e
−z
k!
. (2.1)
The second equality becomes exact in the limit of large N , when a finite
average degree z = p/N makes p necessarily very small. This is, in fact,
the Poisson distribution, an important fact to remember, as we will see.
Graphs as Models of Large-Scale Biochemical Organization 159
2.2. Components
Depending on the exact organization of the L edges, a certain graph can
have different components. Components are defined as the subsets of V in
which all vertices of the subset can be reached from other members of the
subset, but not from any other vertices. Figure 4.2D depicts a graph with
two components. In random graphs, components have an important role.
Basically, as z grows, a random graph shows a phase transition at which
the so-called giant component forms.
For small values of z, the few edges present in the graph are unable to
connect the vertices, and the result is a graph with many small components,
having an average size that remains constant with larger N . However, for a
critical value of z, a given fraction α of vertices form a single component,
therefore having a size αN which scales linearly as N grows. This is the
giant component, and it goes with all the rest of smaller components, which
still remain constant in size as the graph grows. The first appearance of the
giant component occurs, in fact, at z = 1.
2.3. Average path length
Another important average quantity in graphs is the average path
length,
=
1
N (N − 1)
∀i, j
d(v
i
, v
j
) (2.2)
which actually represents the average distance between any pair of ver-
tices. For graphs with given degree distribution, we can calculate in the
following way [3]. Let’s consider a certain vertex v, such as the one shown
in Figure 4.3. First, we can calculate the average number of first neighbors,
z
1
. This is, in fact, the same as z, since the degree measures the number of
neighbors of a vertex. Now we can calculate the number of second neigh-
bors, z
2
. To do this, we first need the distribution p
k
of number of remaining
edges of a certain vertex, given that we arrive from one of them, chosen at
random.
First, we must take into account the fact that a vertex with more degree
has a greater probability of being accessed, i.e., proportional to its degree.
Second, we also have to take into account the edge we arrived along, and
160 Chapter 4
Figure 4.3. A vertex v surrounded by its first neighbors, on average z
1
, and its second
neighbors, on average z
2
.
remove it from the counting. The result is, then,
p
k−1
=
kp
k
N
i=0
kp
i
, (2.3)
including the proper normalization. On average, then, we will find that
following a random edge, the number of remaining edges which we can
follow is
∞
k=1
(k − 1)p
k−1
=
∞
k=0
(k − 1)kp
k
N
i=0
kp
i
=
k
2
−
k
k
(2.4)
That tells us the average of second neighbors found by following one of
our first neighbors, but if we follow an average of k
1
= k first neighbors,
we have the total number of second neighbors from vertex v, that is,
z
2
=
k
2
−
k
. (2.5)
For the case of a random graph, with a Poisson distributed p
k
,wehave
z
2
=
k
2
, so the mean number of second neighbors in the special case of
a random graph is just the mean number of first neighbors squared, which
doesn’t hold in general.
We can now extend this calculation to further neighbors. The distribution
p
k
also tells us how many neighbors a second neighbor has, and in fact it
is true for neighbors at distance m in general. In brief, the average number
Graphs as Models of Large-Scale Biochemical Organization 161
of neighbors at distance m of v is
z
m
=
k
2
−
k
k
z
m−1
=
z
2
z
1
z
m−1
=
z
2
z
1
m−1
z
1
. (2.6)
Depending of the factor z
2
/z
1
, the number of accessible neighbors can be
infinite, something which reminds us about the phase transition mentioned
above. The critical point for this transition is then, z
2
= z
1
, which in the
case of random graphs translates to z = 1, as already mentioned. In general,
though, we can derive an expression for the equation z
2
− z
1
= 0 making
use of Eq. (2.5), which gives us
k
2
− 2
k
=
∞
k=0
k(k − 2)p
k
= 0. (2.7)
To return to our previous discussion, we can now calculate the average
path length making use of Eq. (2.6). Basically, at some m in Eq. (2.6) the
number of accessible neighbors will be N , and that is precisely , since it
is the average number of steps at which an average node reaches the whole
graph. Taking logarithms for equation N = z
and reorganizing, we arrive
at
=
log(N/z
1
)
log(z
2
/z
1
)
+ 1. (2.8)
For the special case of Er´´ods-R´enyi random graph, in which z
2
= z
2
,
the expression reduces to = log N /log z. This is an important result, in
fact. It says that, in random graphs, grows rather slowly with the size of
the graph, and that a big graph with N = 1000 and z = 4 will have ≈ 5.
2.4. Clustering
Graphs can also display structure at the local scale, and one of the easiest
ways to describe it is by measuring of the average clustering coefficient, or
C. This coefficient is a measure applied to a given vertex v
i
, and it measures
how far a vertex is of being part of a clique. A clique is basically a small
graph with full connectivity; every vertex is connected to every other. It
is clear that if a certain vertex v
i
is part of a clique, the number of edges
between its k
i
neighbors must be k
i
(k
i
− 1)/2. If instead of that we find E
i
edges, the corresponding fraction is precisely C
i
, the clustering coefficient,