Models and Algorithms for Biomolecules and Molecular Networks
Description
More details
Other editions
Additional editions
Persons
Content
List of Figures xiii
List of Tables xix
Foreword xxi
Acknowledgments xxiii
1 Geometric Models of Protein Structure and Function Prediction 1
1.1 Introduction 1
1.2 Theory and Model 2
1.2.1 Idealized Ball Model 2
1.2.2 Surface Models of Proteins 3
1.2.3 Geometric Constructs 4
1.2.4 Topological Structures 6
1.2.5 Metric Measurements 9
1.3 Algorithm and Computation 13
1.4 Applications 15
1.4.1 Protein Packing 15
1.4.2 Predicting Protein Functions from Structures 17
1.5 Discussion and Summary 20
References 22
Exercises 25
2 Scoring Functions for Predicting Structure and Binding of Proteins 29
2.1 Introduction 29
2.2 General Framework of Scoring Function and Potential Function 31
2.2.1 Protein Representation and Descriptors 31
2.2.2 Functional Form 32
2.2.3 Deriving Parameters of Potential Functions 32
2.3 Statistical Method 32
2.3.1 Background 32
2.3.2 Theoretical Model 33
2.3.3 Miyazawa--Jernigan Contact Potential 34
2.3.4 Distance-Dependent Potential Function 41
2.3.5 Geometric Potential Functions 45
2.4 Optimization Method 49
2.4.1 Geometric Nature of Discrimination 50
2.4.2 Optimal Linear Potential Function 52
2.4.3 Optimal Nonlinear Potential Function 53
2.4.4 Deriving Optimal Nonlinear Scoring Function 55
2.4.5 Optimization Techniques 55
2.5 Applications 55
2.5.1 Protein Structure Prediction 56
2.5.2 Protein--Protein Docking Prediction 56
2.5.3 Protein Design 58
2.5.4 Protein Stability and Binding Affinity 59
2.6 Discussion and Summary 60
2.6.1 Knowledge-Based Statistical Potential Functions 60
2.6.2 Relationship of Knowledge-Based Energy Functions and Further Development 64
2.6.3 Optimized Potential Function 65
2.6.4 Data Dependency of Knowledge-Based Potentials 66
References 67
Exercises 75
3 Sampling Techniques: Estimating Evolutionary Rates and Generating Molecular Structures 79
3.1 Introduction 79
3.2 Principles of Monte Carlo Sampling 81
3.2.1 Estimation Through Sampling from Target Distribution 81
3.2.2 Rejection Sampling 82
3.3 Markov Chains and Metropolis Monte Carlo Sampling 83
3.3.1 Properties of Markov Chains 83
3.3.2 Markov Chain Monte Carlo Sampling 85
3.4 Sequential Monte Carlo Sampling 87
3.4.1 Importance Sampling 87
3.4.2 Sequential Importance Sampling 87
3.4.3 Resampling 91
3.5 Applications 92
3.5.1 Markov Chain Monte Carlo for Evolutionary Rate Estimation 92
3.5.2 Sequentail Chain Growth Monte Carlo for Estimating Conformational Entropy of RNA Loops 95
3.6 Discussion and Summary 96
References 97
Exercises 99
4 Stochastic Molecular Networks 103
4.1 Introduction 103
4.2 Reaction System and Discrete Chemical Master Equation 104
4.3 Direct Solution of Chemical Master Equation 106
4.3.1 State Enumeration with Finite Buffer 106
4.3.2 Generalization and Multi-Buffer dCME Method 108
4.3.3 Calculation of Steady-State Probability Landscape 108
4.3.4 Calculation of Dynamically Evolving Probability Landscape 108
4.3.5 Methods for State Space Truncation for Simplification 109
4.4 Quantifying and Controlling Errors from State Space Truncation 111
4.5 Approximating Discrete Chemical Master Equation 114
4.5.1 Continuous Chemical Master Equation 114
4.5.2 Stochastic Differential Equation: Fokker-Planck Approach 114
4.5.3 Stochastic Differential Equation: Langevin Approach 116
4.5.4 Other Approximations 117
4.6 Stochastic Simulation 118
4.6.1 Reaction Probability 118
4.6.2 Reaction Trajectory 118
4.6.3 Probability of Reaction Trajectory 119
4.6.4 Stochastic Simulation Algorithm 119
4.7 Applications 121
4.7.1 Probability Landscape of a Stochastic Toggle Switch 121
4.7.2 Epigenetic Decision Network of Cellular Fate in Phage Lambda 123
4.8 Discussions and Summary 127
References 128
Exercises 131
5 Cellular Interaction Networks 135
5.1 Basic Definitions and Graph-Theoretic Notions 136
5.1.1 Topological Representation 136
5.1.2 Dynamical Representation 138
5.1.3 Topological Representation of Dynamical Models 139
5.2 Boolean Interaction Networks 139
5.3 Signal Transduction Networks 141
5.3.1 Synthesizing Signal Transduction Networks 142
5.3.2 Collecting Data for Network Synthesis 146
5.3.3 Transitive Reduction and Pseudo-node Collapse 147
5.3.4 Redundancy and Degeneracy of Networks 153
5.3.5 Random Interaction Networks and Statistical Evaluations 157
5.4 Reverse Engineering of Biological Networks 159
5.4.1 Modular Response Analysis Approach 160
5.4.2 Parsimonious Combinatorial Approaches 166
5.4.3 Evaluation of Quality of the Reconstructed Network 171
References 173
Exercises 178
6 Dynamical Systems and Interaction Networks 183
6.1 Some Basic Control-Theoretic Concepts 185
6.2 Discrete-Time Boolean Network Models 186
6.3 Artificial Neural Network Models 188
6.3.1 Computational Powers of ANNs 189
6.3.2 Reverse Engineering of ANNs 190
6.3.3 Applications of ANN Models in Studying Biological Networks 192
6.4 Piecewise Linear Models 192
6.4.1 Dynamics of PL Models 194
6.4.2 Biological Application of PL Models 195
6.5 Monotone Systems 200
6.5.1 Definition of Monotonicity 201
6.5.2 Combinatorial Characterizations and Measure of Monotonicity 203
6.5.3 Algorithmic Issues in Computing the Degree of Monotonicity ¿¿¿¿ 207
References 209
Exercises 214
7 Case Study of Biological Models 217
7.1 Segment Polarity Network Models 217
7.1.1 Boolean Network Model 218
7.1.2 Signal Transduction Network Model 218
7.2 ABA-Induced Stomatal Closure Network 219
7.3 Epidermal Growth Factor Receptor Signaling Network 220
7.4 C. elegans Metabolic Network 223
7.5 Network for T-Cell Survival and Death in Large Granular Lymphocyte Leukemia 223
References 224
Exercises 225
Glossary 227
Index 229
List of Figures
- 1.1 Geometric models of protein surfaces.
- 1.2 Geometry of a simplified two-dimensional model molecule.
- 1.3 The family of alpha shapes or dual simplicial complexes for a two-dimensional toy molecule.
- 1.4 An illustration of a family of alpha shapes of HIV-1 protease and flips.
- 1.5 An example of analytical area calculation.
- 1.6 Discrete flow of empty space illustrated for two-dimensional disks.
- 1.7 The computed surface pockets of binding sites on Ras21 protein and FtsZ protein.
- 1.8 An illustration of locally Delaunay edge and flips.
- 1.9 Voids and pockets for a set of 636 proteins representing most of the known protein folds, and the scaling behavior of the geometric properties of proteins.
- 1.10 Protein function prediction as illustrated by the example of alpha amylases.
- 2.1 The Miyazawa-Jernigan model of chemical reaction.
- 2.2 Schematic drawing of the Delaunay complex and the alpha shape of a two-dimensional molecule.
- 2.3 Schematic illustration of noninteracting pairs of residues.
- 2.4 Geometric views of the inequality requirement for the protein scoring function.
- 2.5 Recognition of binding surface patch of protein targets using the geometric potential function.
- 3.1 The Ising model of 30×30 size, with a total of 30 × 30 = 900 sites.
- 3.2 Illustration of rejection sampling.
- 3.3 Generating a self-avoiding chain by sequential importance sampling.
- 3.4 An example of a phylogenetic tree.
- 4.1 The stochastic network of a toggle switch.
- 4.2 The steady-state probability landscape of a toggle switch.
- 4.3 Different selection of cell fate of E. coli infected by phage lambda and a model of the epigenetic circuit for lysogeny maintenance.
- 4.4 The probability landscape of the epigenetic circuits of lysogeny maintenance in phage lambda.
- 4.5 Instability, shallow threshold, and switching inefficiency of the network against fluctuation in UV irradiation in mutant phage lambda.
- 5.1 Illustration of the labeled directed graph representation for a molecular interaction network. The arc B A indicates a negative influence of B on A; that is, an increase in the amount of protein B causes a decrease in the amount of protein A. The pathway B C A D induces a positive influence of B on D since the product of labels of its arcs is 1 × (- 1) × (- 1) = 1.
- 5.2 A Boolean circuit composed of logical AND, OR, and NOT gates that encode relationships between three proteins and two genes. For example, either Protein B must be absent or Protein C must be present (or both) to activate Gene Y .
- 5.3 (a) A Boolean network with three binary states s1, s2, s3. (b) The associated directed graph. A fixed point of the network is given by s=(s1,s2,s3)=(0,1,0).
- 5.4 An algorithmic framework for synthesizing signal transduction networks [5]. The optimization steps involving Tr and Pnc are explained in Section 5.3.3.
- 5.5 Dynamic programming algorithm to find all reachabilities.
- 5.6 Pictorial illustration of the iterative calculations of the dynamic programming algorithm in Fig. 5.5.
- 5.7 The transitive reduction (Tr) problem.
- 5.8 An example of obtaining a reduced network via transitive reduction. The obtained network is not minimal (see Exercise 5.4).
- 5.9 A greedy algorithm to solve Tr.
- 5.10 An example of a family of graphs for which the greedy algorithm has an approximation ratio of 2. The greedy algorithm may remove the arcs vivi+1 for i = 1, 2, ..., n - 1 providing a solution with 2n arcs, but an optimal solution with n + 1 arcs is possible by selecting the arcs v0v1, vivi+1 for i = 1, 2, ..., n - 1, and vnv0.
- 5.11 The pseudo-node collapse (Pnc) problem [5].
- 5.12 A system of seven elements.
- 5.13 Equivalence of dynamical properties may depend on node functions.
- 5.14 (a) The Markov-chain algorithm for generating random networks by arc swapping. (b) A pictorial illustration of arc swapping.
- 5.15 A schematic diagram for the overview of the Mra approach.
- 5.16 Linear algebraic formulation of the experimental design question for the Mra approach.
- 5.17 A combinatorially equivalent reformulation of (5.6).
- 5.18 Two well-known algorithms to solve SC1 [84].
- 5.19 Improved randomized approximation algorithm for SC? [14].
- 5.20 (a) Measurements of expression levels of 5 genes 1, 2, 3, 4, and 5 at two successive time steps; variable xi corresponds to gene i. (b) A causal relationship and Boolean formula that explains the causal relationship of other variables to x5 based only on the data shown in (a). (c) Another causal relationship and Boolean formula for 5 that is consistent with the data in (a).
- 5.21 (a) Data matrix X = (xi,j) (quantized to four values) for measurement of expression levels of m = 5 genes at n + 1 = 4 time points. (b) The universe and sets corresponding to gene 2 in the hitting set formulation of Fig. 5.22a.
- 5.22 (a) A hitting set formulation of the combinatorial approach for gene i. (b) A greedy algorithm for HS that iteratively selects a new element of the universe that hits a maximum number of sets not hit yet.
- 5.23 Two-dimensional Roc space obtained by plotting FPR versus TPR values.
- 5.24 Three n-node graphs (shown for n = 8) discussed in Exercise 5.6.
- 5.25 Contraction of a cycle of length 4.
- 6.1 A Boolean network of two species interaction.
- 6.2 (a) The threshold gate function. (b) The sigmoidal gate function.
- 6.3 A discrete-time sigmoidal neural network and its graphical representation.
- 6.4 (a) A continuous-state discrete-time ANN with a continuous gate function g. (b) The difference equation model corresponding to the ANN in (a). Ri is the maximum rate of synthesis of gene vi, ?i is the degradation rate of the product from gene vi, and the threshold ?i summarizes the effect of general transcription factors on gene vi. (c) The specific activation function g used by Kyoda et al. [62]. (d) The topological version of the model in (b) indicating excitory and inhibitory effects.
- 6.5 Rectangular partition of state space induced by system (6.7).
- 6.6 (a) An example of an Nfa. The input 0101 S* is accepted by the Nfa since there is a directed path from the initial state q0 to a final state q2 labeled 0101. (b) An example of a piecewise-linear hybrid automata (Plha) with two continuous-state variables and no inputs. A hypothetical trajectory of the dynamics is shown by thick black lines with arrows.
- 6.7 Hexagonal lattice of cells for Delta-Notch protein signaling. A cell with its six neighbors is shown amplified.
- 6.8 A system composed of five interconnected subsystems.
- 6.9 Two signed graphs. The graph in (a) is sign-consistent, but the graph in (b), which differs in just one edge from (a), is not sign-consistent since it has two paths in its undirected version with different parity between nodes x1 x4, namely a direct path of odd parity and a path of even parity transversing node x5. Self-loops, which in biochemical systems often represent degradation terms, are ignored in the definition.
- 6.10 Definition of the sign consistency problem.
- 6.11 Deletion of the arc (x2, x4) makes the given signed graph consistent. The node labels are shown besides the nodes.
- 7.1 A schematic diagram of the early development of a Drosophila embryo. Each hexagon represents a cell, and neighboring cells interact to form a collective behavior. In this figure, an initial striped pattern of the genes en and wg induces the production of the gene hh, but only in those cells that are producing en .
- 7.2 The Drosophila segment polarity regulatory network for one cell with the interpretation of the regulatory role of PTC on the reaction CI CN as PTC CN and PTC CI [8].
- 7.3 A one-dimensional...
