Algorithmic Bioprocesses (eBook)

Anne Condon, David Harel, Joost N. Kok, Arto Salomaa, Erik Winfree (Herausgeber)

eBook Download: PDF

2009
XX, 742 Seiten
Springer Berlin (Verlag)
978-3-540-88869-7 (ISBN)

Infos

A fundamental understanding of algorithmic bioprocesses is key to learning how information processing occurs in nature at the cell level. The field is concerned with the interactions between computer science on the one hand and biology, chemistry, and DNA-oriented nanoscience on the other. In particular, this book offers a comprehensive overview of research into algorithmic self-assembly, RNA folding, the algorithmic foundations for biochemical reactions, and the algorithmic nature of developmental processes.

The editors of the book invited 36 chapters, written by the leading researchers in this area, and their contributions include detailed tutorials on the main topics, surveys of the state of the art in research, experimental results, and discussions of specific research goals. The main subjects addressed are sequence discovery, generation, and analysis; nanoconstructions and self-assembly; membrane computing; formal models and analysis; process calculi and automata; biochemical reactions; and other topics from natural computing, including molecular evolution, regulation of gene expression, light-based computing, cellular automata, realistic modelling of biological systems, and evolutionary computing.

This subject is inherently interdisciplinary, and this book will be of value to researchers in computer science and biology who study the impact of the exciting mutual interaction between our understanding of bioprocesses and our understanding of computation.

The editors and contributors include most of the key researchers working on these topics worldwide.

Inhalt

Preface 7
Contents 11
Contributors 15
Tribute 21
Grzegorz Rozenberg: A Magical Scientist and Brother 22
General 22
Personal Recollections 23
Grzegorz and Bolgani 23
Brother 25
Case Studies of Scientific Cooperation 27
Quasi-uniform Events and Mostowski 27
Developing Cells and Lindenmayer 28
Twin-Shuffle and Unisono Duet 28
Conclusion 29
References 29
Sequence Discovery, Generation, and Analysis 31
Monotony and Surprise 32
Introduction 33
Solid Patterns 35
Patterns with Mismatches 36
Patterns Within Bounded Levenshtein Distance 38
Patterns with Don't Cares 39
Saturated Associations and Rules 41
Compressing and Classifying 42
Concluding Remarks 44
References 44
Information Content of Sets of Biological Sequences Revisited 47
Introduction 47
The Model 48
Comparison of EC and IC on Residue Positions 50
Materials and Methods 52
Protein Complexes Dataset for Testing 52
Evaluation 52
alpha,beta, gamma Parameterization for the Entropy Function Applied to a Single Protein or to a Dataset 54
Discussion 56
References 57
Duplication in DNA Sequences 59
Introduction 59
Preliminaries 61
Closure Properties 62
Language Equations 66
Controlled Duplication 67
Conditions for L(C) to Be Regular 69
Duplication and Primitivity 75
Discussion 75
References 76
Sequence and Structural Analyses for Functional Non-coding RNAs 78
Introduction 78
RNA Sequence Alignment and Secondary Structure Prediction Using Stochastic Grammar 79
SCFG: Stochastic Context-Free Grammar 80
PHMMTS: Pair Hidden Markov Model on Tree Structure 81
RNA Secondary Structural Alignment with Conditional Random Fields 83
PSTAG: Pair Stochastic Tree Adjoining Grammars for Aligning and Predicting Pseudoknot RNA Structures 83
Structural RNA Sequence Alignment Based on Sankoff's Algorithm 84
SCARNA: Stem Candidate Aligner for RNAs 85
Discrimination of Functional RNA Sequences Using Support Vector Machines 86
String Kernel 86
Feature Space for RNA Sequences 87
Stem Kernels 88
Computational Experiments 89
Discriminations of Several RNA Families 89
Finding a Remote RNA Family 90
Marginalized Kernels on SCFGs 91
RNA Gene Finding Based on the Comparative Genomics Approach 92
References 93
Gene Assembly in Ciliates 95
Strategies for RNA-Guided DNA Recombination 96
Introduction 96
RNA-Guided DNA Recombination 98
Brief Summary of Experimental Conclusions 101
Assembly Graphs and Recombination Strategies 102
Toward an Abstract Model 102
Assembly Graphs 104
Successive Smoothings and Assembly Strategies 106
Smoothing 106
Strategies for Simultaneous Assemblies 107
Concluding Remarks 110
References 110
Reality-and-Desire in Ciliates 112
Introduction 112
Sorting by Reversal 113
Gene Assembly 115
Reality-and-Desire 116
The Form of Reduction Graphs 120
Different Strings, Same Graph 122
Intermediate Gene Patterns 123
Gene Assembly Operations 124
Cyclic Components 126
Discussion 128
References 128
Template-Guided Recombination: From Theory to Laboratory 129
Introduction 129
Relationship to Natural Computing 130
Outline 130
Conjugation in Ciliates 130
Formal Model 132
Origin of IESs 134
RNA Template Model 134
Formal Language Model 135
Formal Language Theory Basics 135
Formal Language Model for TGR 136
Iterated TGR 137
Classes of Languages Defined by TGR 137
Deletion Contexts in TGR 138
Intra-molecular TGR 138
Relation to Splicing Systems 139
Computational Power 141
Closure Properties 141
Closure Properties of Intra-molecular TGR 142
Closure Property Dependencies 143
Equivalence 144
Covering and Scaffolding 145
Experimental Results 147
Concluding Remarks 148
References 149
Nanoconstructions and Self-assembly 150
DNA Cages with Icosahedral Symmetry in Bionanotechnology 151
Introduction 151
Construction of Cages with Icosahedral Symmetry: General Principles 152
The Construction Procedure: Step I 154
The Construction Procedure: Step II 155
The Icosahedral Cage 156
The Dodecahedral Cage 160
The Icosidodecahedral Cage 165
Discussion 167
References 168
Applying Symmetric Enumeration Method to One-Dimensional Assembly of Rotatable Tiles 169
Introduction 169
Equilibrium of Hybridization Reaction System 171
Symmetric Enumeration Method (SEM) 173
Hypergraphs 173
Symmetric Enumeration of Assemblies by Hypergraphs 175
Reducing Number of Variables by Symmetric Enumeration Scheme 176
One-Dimensional Assembly of Rotatable Tiles 177
Applying SEM to One-Dimensional Tile Assembly 179
Symmetric ES Under Assumption (T) 180
Another Symmetric ES Under Assumption (T) 185
Symmetric ES Under Assumption (T') 190
Concluding Remarks 192
References 193
A Self-assembly Model of Time-Dependent Glue Strength 194
Introduction 194
Motivation 194
Prior Models for Tile Assembly 195
Needs for New Models for Tile Assembly 195
Tiling Assembly Models 196
The Abstract Tiling Assembly (ATA) Model 196
Our Time-Dependent Glue (TDG) Model 197
Implementation of Time-Dependent Glue Model 198
Catalysis 201
Self-replication 202
Tile Complexity Results 204
Tile Complexity Results for Thin Rectangles 204
Further Tiling Assemblies for Interesting Shapes 208
Discussion and Future Work 211
References 211
The Perils of Polynucleotides Revisited 214
Introduction 214
Old Rules and New Perspectives 215
[1] Symmetry Is Inimical to Control 215
[2] Non-Watson-Crick Pairing in Unusual Structures 215
[3] The Importance of Hybridization Protocols 216
[4] The Importance of DNA Concentration and Environment 216
[5] Proper Estimation of DNA Dimensions 216
[6] Experimental Determination of DNA Features 217
[7] The Fidelity of Ligation Is High, but Not Perfect 217
[8] DNA Molecules Breathe 217
[9] Long and Loose Closed DNA Molecules Form Topoisomers 218
[10] Affinity Binding Is a Filtration Process 218
[11] Complex Ligation Mixtures Can Lead to Complex Products 218
[12] Separation of Hydrogen-Bonded Molecules in Native Conditions Is Often Ineffective 218
[13] Restriction Endonucleases Often Produce Partial Digestion Products 219
[14] Multimerization of Cyclic Structures Can Occur 219
[15] Base Stacking Is Often the Determining Interaction 219
[16] Treat DNA as a Physical Chemical System 219
New Points 220
[17] Crude DNA Is Impure Material 220
[18] DX Cohesion Is More Effective than Simple Sticky-Ended Cohesion 220
[19] Robust Devices are Necessary for a Nanorobotics That Emulates Macro-scale Robotics 220
[20] Two Contexts That Are Not Identical Are Different 220
Concluding Comments 221
References 221
Algorithmic Control: The Assembly and Operation of DNA Nanostructures and Molecular Machinery 224
Algorithmic Assembly 224
Algorithmic Control of Molecular Machinery 228
Summary 231
References 232
Membrane Computing 235
On Nonuniversal Symport/Antiport P Systems 236
Introduction 236
SA P Systems with a Small Number of Objects 238
2-Symbol 1-Membrane SA P System Acceptors 238
1-Symbol 3-Membrane SA P System Acceptors 240
1-Symbol Multimembrane SA P System Acceptors 240
1-Symbol Multimembrane SA P System Generators 248
Prioritized 1-Symbol Multimembrane SA P System Acceptors 250
Bounded SA P Systems 253
1-Membrane Bounded SA P Systems 253
Multimembrane Special SA P Systems 259
1-Membrane Bounded SA P Systems Which Accept String Languages 262
SA P Systems and Semilinear Sets 264
Simple SA P Systems 265
Cascade SA P Systems 269
k-Membrane Extended Cascade SA P Systems 273
Restricted SA P System Generators 275
References 278
Spiking Neural P Systems. Recent Results, Research Topics 280
Forecast 280
Some (Neural) Generalities 281
Spiking Neural P Systems-An Informal Presentation 281
Some (More) Formal Definitions 284
Open Problems and Research Topics 287
Final Remarks 295
References 296
Membrane Computing Schema: A New Approach to Computation Using String Insertions 299
Introduction 299
Preliminaries 300
Membrane Computing Schema, Interpretation and Languages 302
Membrane Computing Schema 302
Interpretation of Pi 303
Transitions and Languages 304
Characterizations by Membrane Schema Pi0 306
Further Results on Some Variants of Membrane Schema 309
Concluding Remarks 313
References 314
Formal Models and Analysis 316
Finite Splicing: Generative Capacity, New Models and Complexity Aspects 317
Introduction 317
Formal Languages and Finite Splicing Systems 319
Constant Languages and Classes of Regular Splicing Languages 321
Decision Procedures 324
New Directions 324
Non-preserving Splicing 325
Complexity Aspects 326
Complexity Measures 326
Descriptional Complexity of Finite Splicing Systems 327
Decidability Questions 328
Accepting Splicing Systems 329
Open Questions and Further Research 330
References 332
Formal Models of the Calyx of Held 334
Introduction 334
Background 336
Neurons 337
The Calyx of Held 338
Deterministic Models of Biochemical Pathways 339
The Stochastic Simulation Algorithm 339
Process Calculi and the Stochastic Pi-calculus 341
Deterministic Models 343
The High Ca2+ Sensitivity of Vesicle Release 343
Pre-synaptic Facilitation 345
Pre-synaptic Potentiation 345
Pre-synaptic Depression 346
Post-synaptic Receptor Desensitization 347
A Process-Calculus Stochastic Model 347
Step- and Wave-Like Ca2+ Uncaging Pre-synaptic Model 348
Implementation of the Model 350
Short Term Plasticity: Facilitation, Potentiation, and Depression in the Pre-synaptic Terminal 353
Paired Pulse Facilitation 353
Implementation 353
Synaptic Potentiation 355
Implementation 355
Synaptic Depression 355
Implementation 359
Post-synaptic Membrane Receptor Activity 360
A Whole Synapse Model 361
Implementation 363
An Experiment on the Whole Synapse 363
Concluding Remarks 365
References 367
Understanding Network Behavior by Structured Representations of Transition Invariants 370
Motivation 370
Preliminaries 372
Biochemically Interpreted Petri Nets 374
Structuring Method 377
Computation 378
Computation of Invariants 379
Computation of Dependent Sets 380
Case Studies 381
Glycolysis 381
Apoptosis 383
Hypoxia 386
Tools 387
Related Work 388
Summary 390
References 390
Quantitative Verification Techniques for Biological Processes 393
Introduction 393
Outline 394
Probabilistic Model Checking 394
Case Study: MAPK Cascade 397
Specifying the Model 398
Specifying Rewards 402
Specifying Properties 403
Results and Analysis 404
Related Work 406
Conclusions 409
References 409
A New Mathematical Model for the Heat Shock Response 412
Introduction 412
A New Molecular Model for the Eukaryotic Heat Shock Response 413
The Mathematical Model 414
The Principle of Mass-Action 415
Our Mathematical Model 416
Fitting the Model to Experimental Data 420
Sensitivity Analysis 422
References 425
Process Calculi and Automata 427
Artificial Biochemistry 428
Introduction 428
Macromolecules 428
Molecules as Automata 429
Stochastic Automata Collectives 430
Paper Outline 430
Interacting Automata 431
Automata Reactions 431
Groupies and Celebrities 432
Mixed Populations 434
The Chemistry of Automata 436
Concentration 436
First-Order Reactions 437
Second-Order Reactions 438
Zero-Order Reactions 440
Ultrasensitivity 442
Positive Feedback Transitions 443
Excitation Cascades 445
Boolean Inverters 447
Boolean Circuits 449
Bistable Circuits 451
Discrete vs. Continuous Modeling 452
The Biochemistry of Automata 453
Beyond Simple Automata 453
Polyautomata 454
Complexation 455
Polymerization 456
Conclusions and Related Work 459
References 460
Process Calculi Abstractions for Biology 462
Introduction 462
A Simple Biological Scenario 463
Biochemical Interactions 463
The Running Example 464
Calculi for Biology 466
Process Calculi: The Approach 466
Biochemical pi-Calculus 468
BioAmbients 470
Brane Calculi 472
CCS-R 474
PEPA 475
Beta-binders 477
kappa-Calculus 478
Concluding Remarks 480
References 482
Deriving Differential Equations from Process Algebra Models in Reagent-Centric Style 486
Introduction 486
Reagent-Centric Modeling 487
Deriving ODEs 490
Example: Tumor Necrosis Factor alpha 492
More Powerful Reagent-Centric Modeling: Bio-PEPA 495
Related Work 499
Conclusions 500
References 501
Programmable DNA-Based Finite Automata 504
Introduction 504
Bio-molecular Finite Automata 505
2-Symbols-2-States Soluble DNA-Based Finite Automata 505
Immobilized DNA-Based Automata 509
DNA-Based Automaton with Bacterial Phenotype Output 510
Parallel Computation by DNA Array 512
Conclusions 514
References 515
Biochemical Reactions 516
A Multi-volume Approach to Stochastic Modeling with Membrane Systems 517
Introduction 517
Stochastic Approaches to Modeling and Simulation of Biological Systems 518
Stochasticity in Chemical and Biological Systems 519
Single-Volume Stochastic Simulation Algorithms 519
A Multi-volume Approach with Membrane Systems 522
Membrane Systems 522
DPP 523
tau-DPP 526
Internal and Communication Rules 526
The tau-DPP Algorithm 528
Application of tau-DPP to Coupled Genetic Oscillators 531
A Multi-volume Model for Coupled Genetic Oscillators 532
Results of Simulations 534
Discussion 538
References 539
Programmability of Chemical Reaction Networks 541
Introduction 541
Formalization of Chemistry 543
Stochastic Chemical Reaction Networks 543
Other Models of Chemical Computing 546
Bounded Models: Boolean Logic Circuits 546
Unordered Program Models: Petri Nets and VASs 547
Gate Implementability 550
Gate Implementability Is Equivalent to Reachability in Stochastic Chemical Reaction Networks 550
Almost Universal: Primitive Recursive Computation 552
Primitive Recursive Functions 553
A Primitive Recursive Bound on the Depth of the Tree of Reachable States 555
The Algorithm 556
The Data Structure 557
The Bound 559
The Max-Path Problem 560
SCRNs for Rows of the Ackermann Function 561
SCRNs for Primitive Recursive Functions 562
Ordered Program Models: Register Machines and Fractran 563
Computation in Stochastic Chemical Reaction Networks 566
Probability in SCRNs Is Undecidable 567
Eliminating Dependency on the Number of Molecules Disables Universal Computation 571
Efficiency of Computation by Stochastic Chemical Reaction Networks 572
Stochastic Chemical Reaction Networks Can Efficiently Simulate Turing Machines 572
The Exploding Computer 573
Turing Machines Can Efficiently Simulate Robust Stochastic Chemical Reaction Networks 578
Concluding Remarks 579
References 580
Log-gain Principles for Metabolic P Systems 583
Introduction 583
The Mass Partition Principle 585
Metabolic P Systems 587
MP Models and Differential Models 591
An MP Model of Mitotic Oscillator 592
Metabolic Log-gain Principles 594
Conclusions 600
References 601
Hybrid Method for Simulating Small-Number Molecular Systems 604
Introduction 604
Background 606
Gillespie's Stochastic Simulation Algorithm 606
Original SSA 606
tau-Leap Method 607
Simulations of Toggle Switches 607
Toggle Switch with SOS Pathway 607
Toggle Switch with Quorum-Sensing Signaling Pathway 609
Hybrid Simulation 612
Methods 613
Basic Approach 613
Iterative Approach 613
Results 615
Basic Approach 615
Iterative Approach 615
Conclusions 616
References 617
Broader Perspective 618
On Involutions Arising from Graphs 619
Introduction 619
Preliminaries 619
Involutions of Cyclic Groups 620
Involutions of Group Products 622
The set Delta2(Gamma,delta) 624
Example: The Case of the Identity Involution 625
References 626
Parallel Computing by Xeroxing on Transparencies 627
Introduction 627
Constructing an n Variable Truth Table by Xeroxing onto Only n Transparencies 628
Evaluating a Clause over All Truth Settings Simultaneously 629
Completing the Solution 629
Extending the Scope and Observing the Flexibility of Computing by Xerography 630
The Immediate Future 631
References 632
Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata 634
Introduction 634
History and Brief Outline of the Results 634
Cellular Automata 635
Tilings 637
Turing Machines 639
The 2-Way Deterministic Tiling Problem with a Seed Tile 639
The Idea for the Undecidability Proof 639
The Tile Set for the Given Turing Machine 640
Tile Sets and Cellular Automata 645
Interpreting Tile Set as a Cellular Automaton 645
Universality of One-Dimensional Reversible Cellular Automata 646
Undecidability Results for Reversible Cellular Automata 647
Undecidability of the 2-Way Deterministic Tiling Problem 647
Some Undecidability Results for Cellular Automata 648
Left Expansivity is Undecidable 652
Discussion 653
References 654
On Using Divide and Conquer in Modeling Natural Systems 656
Introduction 656
Pancreatic Organogenesis 658
Methods 658
Modeling Approach 658
Modeling Molecular Interactions 659
Modeling Structural Formation 661
Combining the Two: The Simulation at Run-Time 661
Results 662
Behavior of Population Fits Simple Mathematical Model 662
The Emerging Structure Generates Histological Sections 663
The Need for Cross-scaling in Pancreatic Organogenesis 665
Discussion 666
References 667
No Molecule Is an Island: Molecular Evolution and the Study of Sequence Space 670
Introduction 670
The Delicate Clockwork Hypothesis of Molecular Evolution 672
Theory and Experiments with Unevolved Sequences 677
Prospects for a Protein Simplex and Exploring Protein Neutral Networks 688
No Molecule Is an Island 689
Sequenomics: Mapping the Universe of Sequence Possibilities 692
Theoretical Sequenomics 693
Sequenomics Visualization 694
The Sequenomics Database 694
Experimental Sequenomics 695
References 697
Niching Methods: Speciation Theory Applied for Multi-modal Function Optimization 700
Introduction 700
Motivation: Speciation Theory vs. Conceptual Designs 701
From DNA to Organic Diversity 702
A Preliminary Note on Terminology 702
Genetic Drift 702
Organic Diversity 703
Variations Within a Species 703
Speciation 705
Derandomized Evolution Strategies (DES) 706
Evolutionary Algorithms 706
Canonical Evolution Strategies 707
General 708
Representation 708
Mutation 708
Selection 709
Derandomization 709
Introduction to Niching 710
Population Diversity in Evolution Strategies 710
Diversity Loss in Evolution Strategies 711
Selective Pressure: Fast Take-over 711
ES Genetic Drift 711
Recombination Drift 711
Selection Drift 712
Neutrality in ES Variations: Mutation Drift 712
Simulations 713
Niching Methods 713
GA Niching Methods 715
Niching in Evolution Strategies 715
Proposed Framework: Niching with DES Kernels 716
The Proposed Algorithm 716
Niching with (1 ,+ lambda) DES Kernels 716
Algorithm Dynamics 717
Sizing the Population 718
Niche Radius Calculation 718
Experimental Observation 719
Extending the Framework: Learning Niche-Shapes 720
Summary and Outlook 720
References 722
On the Concept of Cis-regulatory Information: From Sequence Motifs to Logic Functions 725
Introduction 725
A Case Study 726
The Gene Naming Problem 728
The Consensus Sequence Bottleneck Problem 730
Motif Finding 732
Evaluations of Motif-Finding 733
The Logic Function Inference Problem 733
Conclusion 735
References 735

Produkt-Details

• Erscheint lt. Verlag: 14.8.2009
• Reihe/Serie: Natural Computing Series
• Reihe/Serie: Natural Computing Series
• Zusatzinfo: XX, 742 p. 247 illus., 109 illus. in color.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik
• Themenwelt: Naturwissenschaften ► Biologie
• Themenwelt: Technik
• Schlagworte: Algorithmic bioprocesses • Algorithmic botany • Algorithmic self-assembly • biochemical reactions • Bioinformatics • Cell Biology • Developmental processes • Grammatical models • Information Processing • Live Sequence Charts • molecular computing • Nanosc • Nanoscience • Natu
• ISBN-10: 3-540-88869-1 / 3540888691
• ISBN-13: 978-3-540-88869-7 / 9783540888697