Condon / Harel / Kok Algorithmic Bioprocesses

1. Auflage 2009
ISBN: 978-3-540-88869-7
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 742 Seiten

Reihe: Natural Computing Series

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.

Autoren/Hrsg.

Condon, Anne

Harel, David

Salomaa, Arto

Winfree, Erik

Kok, Joost N.

Inhaltsverzeichnis

1;Preface;7
2;Contents;11
3;Contributors;15
4;Tribute;21
4.1;Grzegorz Rozenberg: A Magical Scientist and Brother;22
4.1.1;General;22
4.1.2;Personal Recollections;23
4.1.2.1;Grzegorz and Bolgani;23
4.1.2.2;Brother;25
4.1.3;Case Studies of Scientific Cooperation;27
4.1.3.1;Quasi-uniform Events and Mostowski;27
4.1.3.2;Developing Cells and Lindenmayer;28
4.1.3.3;Twin-Shuffle and Unisono Duet;28
4.1.4;Conclusion;29
4.1.5;References;29
5;Sequence Discovery, Generation, and Analysis;31
5.1;Monotony and Surprise;32
5.1.1;Introduction;33
5.1.2;Solid Patterns;35
5.1.3;Patterns with Mismatches;36
5.1.4;Patterns Within Bounded Levenshtein Distance;38
5.1.5;Patterns with Don't Cares;39
5.1.6;Saturated Associations and Rules;41
5.1.7;Compressing and Classifying ;42
5.1.8;Concluding Remarks ;44
5.1.9;References;44
5.2;Information Content of Sets of Biological Sequences Revisited;47
5.2.1;Introduction;47
5.2.2;The Model;48
5.2.3;Comparison of EC and IC on Residue Positions;50
5.2.4;Materials and Methods;52
5.2.4.1;Protein Complexes Dataset for Testing;52
5.2.4.2;Evaluation;52
5.2.4.3;alpha,beta, gamma Parameterization for the Entropy Function Applied to a Single Protein or to a Dataset;54
5.2.5;Discussion;56
5.2.6;References;57
5.3;Duplication in DNA Sequences;59
5.3.1;Introduction;59
5.3.2;Preliminaries;61
5.3.3;Closure Properties;62
5.3.4;Language Equations;66
5.3.5;Controlled Duplication;67
5.3.6;Conditions for L(C) to Be Regular;69
5.3.7;Duplication and Primitivity;75
5.3.8;Discussion;75
5.3.9;References;76
5.4;Sequence and Structural Analyses for Functional Non-coding RNAs;78
5.4.1;Introduction;78
5.4.2;RNA Sequence Alignment and Secondary Structure Prediction Using Stochastic Grammar;79
5.4.2.1;SCFG: Stochastic Context-Free Grammar;80
5.4.2.2;PHMMTS: Pair Hidden Markov Model on Tree Structure;81
5.4.2.3;RNA Secondary Structural Alignment with Conditional Random Fields;83
5.4.2.4;PSTAG: Pair Stochastic Tree Adjoining Grammars for Aligning and Predicting Pseudoknot RNA Structures;83
5.4.2.5;Structural RNA Sequence Alignment Based on Sankoff's Algorithm;84
5.4.2.6;SCARNA: Stem Candidate Aligner for RNAs;85
5.4.3;Discrimination of Functional RNA Sequences Using Support Vector Machines;86
5.4.3.1;String Kernel;86
5.4.3.2;Feature Space for RNA Sequences;87
5.4.3.3;Stem Kernels;88
5.4.3.4;Computational Experiments;89
5.4.3.4.1;Discriminations of Several RNA Families;89
5.4.3.4.2;Finding a Remote RNA Family;90
5.4.3.5;Marginalized Kernels on SCFGs;91
5.4.4;RNA Gene Finding Based on the Comparative Genomics Approach;92
5.4.5;References;93
6;Gene Assembly in Ciliates;95
6.1;Strategies for RNA-Guided DNA Recombination;96
6.1.1;Introduction;96
6.1.2;RNA-Guided DNA Recombination;98
6.1.3;Brief Summary of Experimental Conclusions;101
6.1.4;Assembly Graphs and Recombination Strategies;102
6.1.4.1;Toward an Abstract Model;102
6.1.4.2;Assembly Graphs;104
6.1.5;Successive Smoothings and Assembly Strategies;106
6.1.5.1;Smoothing;106
6.1.5.2;Strategies for Simultaneous Assemblies;107
6.1.6;Concluding Remarks;110
6.1.7;References;110
6.2;Reality-and-Desire in Ciliates;112
6.2.1;Introduction;112
6.2.2;Sorting by Reversal;113
6.2.3;Gene Assembly;115
6.2.4;Reality-and-Desire;116
6.2.5;The Form of Reduction Graphs;120
6.2.6;Different Strings, Same Graph;122
6.2.7;Intermediate Gene Patterns;123
6.2.8;Gene Assembly Operations;124
6.2.9;Cyclic Components;126
6.2.10;Discussion;128
6.2.11;References;128
6.3;Template-Guided Recombination: From Theory to Laboratory;129
6.3.1;Introduction;129
6.3.1.1;Relationship to Natural Computing;130
6.3.1.2;Outline;130
6.3.2;Conjugation in Ciliates;130
6.3.3;Formal Model;132
6.3.3.1;Origin of IESs;134
6.3.3.2;RNA Template Model;134
6.3.4;Formal Language Model;135
6.3.4.1;Formal Language Theory Basics;135
6.3.4.2;Formal Language Model for TGR;136
6.3.4.3;Iterated TGR;137
6.3.4.4;Classes of Languages Defined by TGR;137
6.3.4.5;Deletion Contexts in TGR;138
6.3.4.6;Intra-molecular TGR;138
6.3.5;Relation to Splicing Systems;139
6.3.6;Computational Power;141
6.3.6.1;Closure Properties;141
6.3.6.2;Closure Properties of Intra-molecular TGR;142
6.3.6.3;Closure Property Dependencies;143
6.3.7;Equivalence;144
6.3.8;Covering and Scaffolding;145
6.3.9;Experimental Results;147
6.3.10;Concluding Remarks;148
6.3.11;References;149
7;Nanoconstructions and Self-assembly;150
7.1;DNA Cages with Icosahedral Symmetry in Bionanotechnology;151
7.1.1;Introduction;151
7.1.2;Construction of Cages with Icosahedral Symmetry: General Principles;152
7.1.2.1;The Construction Procedure: Step I;154
7.1.2.2;The Construction Procedure: Step II;155
7.1.3;The Icosahedral Cage;156
7.1.4;The Dodecahedral Cage;160
7.1.5;The Icosidodecahedral Cage;165
7.1.6;Discussion;167
7.1.7;References;168
7.2;Applying Symmetric Enumeration Method to One-Dimensional Assembly of Rotatable Tiles;169
7.2.1;Introduction;169
7.2.2;Equilibrium of Hybridization Reaction System;171
7.2.3;Symmetric Enumeration Method (SEM);173
7.2.3.1;Hypergraphs;173
7.2.3.2;Symmetric Enumeration of Assemblies by Hypergraphs;175
7.2.3.3;Reducing Number of Variables by Symmetric Enumeration Scheme;176
7.2.4;One-Dimensional Assembly of Rotatable Tiles;177
7.2.5;Applying SEM to One-Dimensional Tile Assembly;179
7.2.5.1;Symmetric ES Under Assumption (T);180
7.2.5.2;Another Symmetric ES Under Assumption (T);185
7.2.5.3;Symmetric ES Under Assumption (T');190
7.2.6;Concluding Remarks;192
7.2.7;References;193
7.3;A Self-assembly Model of Time-Dependent Glue Strength;194
7.3.1;Introduction;194
7.3.1.1;Motivation;194
7.3.1.2;Prior Models for Tile Assembly;195
7.3.1.3;Needs for New Models for Tile Assembly;195
7.3.2;Tiling Assembly Models;196
7.3.2.1;The Abstract Tiling Assembly (ATA) Model;196
7.3.2.2;Our Time-Dependent Glue (TDG) Model;197
7.3.3;Implementation of Time-Dependent Glue Model;198
7.3.4;Catalysis;201
7.3.5;Self-replication;202
7.3.6;Tile Complexity Results;204
7.3.6.1;Tile Complexity Results for Thin Rectangles;204
7.3.6.2;Further Tiling Assemblies for Interesting Shapes;208
7.3.7;Discussion and Future Work;211
7.3.8;References;211
7.4;The Perils of Polynucleotides Revisited;214
7.4.1;Introduction;214
7.4.2;Old Rules and New Perspectives;215
7.4.2.1;[1] Symmetry Is Inimical to Control;215
7.4.2.2;[2] Non-Watson-Crick Pairing in Unusual Structures;215
7.4.2.3;[3] The Importance of Hybridization Protocols;216
7.4.2.4;[4] The Importance of DNA Concentration and Environment;216
7.4.2.5;[5] Proper Estimation of DNA Dimensions;216
7.4.2.6;[6] Experimental Determination of DNA Features;217
7.4.2.7;[7] The Fidelity of Ligation Is High, but Not Perfect;217
7.4.2.8;[8] DNA Molecules Breathe;217
7.4.2.9;[9] Long and Loose Closed DNA Molecules Form Topoisomers;218
7.4.2.10;[10] Affinity Binding Is a Filtration Process;218
7.4.2.11;[11] Complex Ligation Mixtures Can Lead to Complex Products;218
7.4.2.12;[12] Separation of Hydrogen-Bonded Molecules in Native Conditions Is Often Ineffective;218
7.4.2.13;[13] Restriction Endonucleases Often Produce Partial Digestion Products;219
7.4.2.14;[14] Multimerization of Cyclic Structures Can Occur;219
7.4.2.15;[15] Base Stacking Is Often the Determining Interaction;219
7.4.2.16;[16] Treat DNA as a Physical Chemical System;219
7.4.3;New Points;220
7.4.3.1;[17] Crude DNA Is Impure Material;220
7.4.3.2;[18] DX Cohesion Is More Effective than Simple Sticky-Ended Cohesion;220
7.4.3.3;[19] Robust Devices are Necessary for a Nanorobotics That Emulates Macro-scale Robotics;220
7.4.3.4;[20] Two Contexts That Are Not Identical Are Different;220
7.4.4;Concluding Comments;221
7.4.5;References;221
7.5;Algorithmic Control: The Assembly and Operation of DNA Nanostructures and Molecular Machinery;224
7.5.1;Algorithmic Assembly;224
7.5.2;Algorithmic Control of Molecular Machinery;228
7.5.3;Summary;231
7.5.4;References;232
8;Membrane Computing;235
8.1;On Nonuniversal Symport/Antiport P Systems;236
8.1.1;Introduction;236
8.1.2;SA P Systems with a Small Number of Objects;238
8.1.2.1;2-Symbol 1-Membrane SA P System Acceptors;238
8.1.2.2;1-Symbol 3-Membrane SA P System Acceptors;240
8.1.2.3;1-Symbol Multimembrane SA P System Acceptors;240
8.1.2.4;1-Symbol Multimembrane SA P System Generators;248
8.1.2.5;Prioritized 1-Symbol Multimembrane SA P System Acceptors;250
8.1.3;Bounded SA P Systems;253
8.1.3.1;1-Membrane Bounded SA P Systems;253
8.1.3.2;Multimembrane Special SA P Systems;259
8.1.3.3;1-Membrane Bounded SA P Systems Which Accept String Languages;262
8.1.4;SA P Systems and Semilinear Sets;264
8.1.4.1;Simple SA P Systems;265
8.1.4.2;Cascade SA P Systems;269
8.1.4.3;k-Membrane Extended Cascade SA P Systems;273
8.1.4.4;Restricted SA P System Generators;275
8.1.5;References;278
8.2;Spiking Neural P Systems. Recent Results, Research Topics;280
8.2.1;Forecast;280
8.2.2;Some (Neural) Generalities;281
8.2.3;Spiking Neural P Systems-An Informal Presentation;281
8.2.4;Some (More) Formal Definitions;284
8.2.5;Open Problems and Research Topics;287
8.2.6;Final Remarks;295
8.2.7;References;296
8.3;Membrane Computing Schema: A New Approach to Computation Using String Insertions;299
8.3.1;Introduction;299
8.3.2;Preliminaries;300
8.3.3;Membrane Computing Schema, Interpretation and Languages;302
8.3.3.1;Membrane Computing Schema;302
8.3.3.2;Interpretation of Pi;303
8.3.3.3;Transitions and Languages;304
8.3.4;Characterizations by Membrane Schema Pi0;306
8.3.5;Further Results on Some Variants of Membrane Schema;309
8.3.6;Concluding Remarks;313
8.3.7;References;314
9;Formal Models and Analysis;316
9.1;Finite Splicing: Generative Capacity, New Models and Complexity Aspects;317
9.1.1;Introduction;317
9.1.2;Formal Languages and Finite Splicing Systems;319
9.1.2.1;Constant Languages and Classes of Regular Splicing Languages;321
9.1.2.2;Decision Procedures;324
9.1.3;New Directions;324
9.1.3.1;Non-preserving Splicing;325
9.1.3.2;Complexity Aspects;326
9.1.3.2.1;Complexity Measures;326
9.1.3.2.2;Descriptional Complexity of Finite Splicing Systems;327
9.1.3.2.3;Decidability Questions;328
9.1.3.3;Accepting Splicing Systems;329
9.1.4;Open Questions and Further Research;330
9.1.5;References;332
9.2;Formal Models of the Calyx of Held;334
9.2.1;Introduction;334
9.2.2;Background;336
9.2.2.1;Neurons;337
9.2.2.2;The Calyx of Held;338
9.2.2.3;Deterministic Models of Biochemical Pathways;339
9.2.2.4;The Stochastic Simulation Algorithm;339
9.2.2.5;Process Calculi and the Stochastic Pi-calculus;341
9.2.3;Deterministic Models;343
9.2.3.1;The High Ca2+ Sensitivity of Vesicle Release;343
9.2.3.2;Pre-synaptic Facilitation;345
9.2.3.3;Pre-synaptic Potentiation;345
9.2.3.4;Pre-synaptic Depression;346
9.2.3.5;Post-synaptic Receptor Desensitization;347
9.2.4;A Process-Calculus Stochastic Model;347
9.2.4.1;Step- and Wave-Like Ca2+ Uncaging Pre-synaptic Model;348
9.2.4.2;Implementation of the Model;350
9.2.4.3;Short Term Plasticity: Facilitation, Potentiation, and Depression in the Pre-synaptic Terminal;353
9.2.4.3.1;Paired Pulse Facilitation;353
9.2.4.3.2;Implementation;353
9.2.4.3.3;Synaptic Potentiation;355
9.2.4.3.4;Implementation;355
9.2.4.3.5;Synaptic Depression;355
9.2.4.3.6;Implementation;359
9.2.4.4;Post-synaptic Membrane Receptor Activity;360
9.2.4.5;A Whole Synapse Model;361
9.2.4.5.1;Implementation;363
9.2.4.6;An Experiment on the Whole Synapse;363
9.2.5;Concluding Remarks;365
9.2.6;References;367
9.3;Understanding Network Behavior by Structured Representations of Transition Invariants;370
9.3.1;Motivation;370
9.3.2;Preliminaries;372
9.3.3;Biochemically Interpreted Petri Nets;374
9.3.4;Structuring Method;377
9.3.5;Computation;378
9.3.5.1;Computation of Invariants;379
9.3.5.2;Computation of Dependent Sets;380
9.3.6;Case Studies;381
9.3.6.1;Glycolysis;381
9.3.6.2;Apoptosis;383
9.3.6.3;Hypoxia;386
9.3.7;Tools;387
9.3.8;Related Work;388
9.3.9;Summary;390
9.3.10;References;390
9.4;Quantitative Verification Techniques for Biological Processes;393
9.4.1;Introduction;393
9.4.1.1;Outline;394
9.4.2;Probabilistic Model Checking;394
9.4.3;Case Study: MAPK Cascade;397
9.4.3.1;Specifying the Model;398
9.4.3.2;Specifying Rewards;402
9.4.3.3;Specifying Properties;403
9.4.3.4;Results and Analysis;404
9.4.4;Related Work;406
9.4.5;Conclusions;409
9.4.6;References;409
9.5;A New Mathematical Model for the Heat Shock Response;412
9.5.1;Introduction;412
9.5.2;A New Molecular Model for the Eukaryotic Heat Shock Response;413
9.5.3;The Mathematical Model;414
9.5.3.1;The Principle of Mass-Action;415
9.5.3.2;Our Mathematical Model;416
9.5.3.3;Fitting the Model to Experimental Data;420
9.5.4;Sensitivity Analysis;422
9.5.5;References;425
10;Process Calculi and Automata;427
10.1;Artificial Biochemistry;428
10.1.1;Introduction;428
10.1.1.1;Macromolecules;428
10.1.1.2;Molecules as Automata;429
10.1.1.3;Stochastic Automata Collectives;430
10.1.1.4;Paper Outline;430
10.1.2;Interacting Automata;431
10.1.2.1;Automata Reactions;431
10.1.2.2;Groupies and Celebrities;432
10.1.2.3;Mixed Populations;434
10.1.3;The Chemistry of Automata;436
10.1.3.1;Concentration;436
10.1.3.2;First-Order Reactions;437
10.1.3.3;Second-Order Reactions;438
10.1.3.4;Zero-Order Reactions;440
10.1.3.5;Ultrasensitivity;442
10.1.3.6;Positive Feedback Transitions;443
10.1.3.7;Excitation Cascades;445
10.1.3.8;Boolean Inverters;447
10.1.3.9;Boolean Circuits;449
10.1.3.10;Bistable Circuits;451
10.1.3.11;Discrete vs. Continuous Modeling;452
10.1.4;The Biochemistry of Automata;453
10.1.4.1;Beyond Simple Automata;453
10.1.4.2;Polyautomata;454
10.1.4.3;Complexation;455
10.1.4.4;Polymerization;456
10.1.5;Conclusions and Related Work;459
10.1.6;References;460
10.2;Process Calculi Abstractions for Biology;462
10.2.1;Introduction;462
10.2.2;A Simple Biological Scenario;463
10.2.2.1;Biochemical Interactions;463
10.2.2.2;The Running Example;464
10.2.3;Calculi for Biology;466
10.2.3.1;Process Calculi: The Approach;466
10.2.3.2;Biochemical pi-Calculus;468
10.2.3.3;BioAmbients;470
10.2.3.4;Brane Calculi;472
10.2.3.5;CCS-R;474
10.2.3.6;PEPA;475
10.2.3.7;Beta-binders;477
10.2.3.8;kappa-Calculus;478
10.2.4;Concluding Remarks;480
10.2.5;References;482
10.3;Deriving Differential Equations from Process Algebra Models in Reagent-Centric Style;486
10.3.1;Introduction;486
10.3.2;Reagent-Centric Modeling;487
10.3.3;Deriving ODEs;490
10.3.4;Example: Tumor Necrosis Factor alpha;492
10.3.5;More Powerful Reagent-Centric Modeling: Bio-PEPA;495
10.3.6;Related Work;499
10.3.7;Conclusions;500
10.3.8;References;501
10.4;Programmable DNA-Based Finite Automata;504
10.4.1;Introduction;504
10.4.2;Bio-molecular Finite Automata;505
10.4.2.1;2-Symbols-2-States Soluble DNA-Based Finite Automata;505
10.4.2.2;Immobilized DNA-Based Automata;509
10.4.2.3;DNA-Based Automaton with Bacterial Phenotype Output;510
10.4.2.4;Parallel Computation by DNA Array;512
10.4.3;Conclusions;514
10.4.4;References;515
11;Biochemical Reactions;516
11.1;A Multi-volume Approach to Stochastic Modeling with Membrane Systems;517
11.1.1;Introduction;517
11.1.2;Stochastic Approaches to Modeling and Simulation of Biological Systems;518
11.1.2.1;Stochasticity in Chemical and Biological Systems;519
11.1.2.2;Single-Volume Stochastic Simulation Algorithms;519
11.1.3;A Multi-volume Approach with Membrane Systems;522
11.1.3.1;Membrane Systems;522
11.1.3.2;DPP;523
11.1.3.3;tau-DPP;526
11.1.3.3.1;Internal and Communication Rules;526
11.1.3.3.2;The tau-DPP Algorithm;528
11.1.4;Application of tau-DPP to Coupled Genetic Oscillators;531
11.1.4.1;A Multi-volume Model for Coupled Genetic Oscillators;532
11.1.4.2;Results of Simulations;534
11.1.5;Discussion;538
11.1.6;References;539
11.2;Programmability of Chemical Reaction Networks;541
11.2.1;Introduction;541
11.2.2;Formalization of Chemistry;543
11.2.2.1;Stochastic Chemical Reaction Networks;543
11.2.2.2;Other Models of Chemical Computing;546
11.2.3;Bounded Models: Boolean Logic Circuits;546
11.2.4;Unordered Program Models: Petri Nets and VASs;547
11.2.4.1;Gate Implementability;550
11.2.4.2;Gate Implementability Is Equivalent to Reachability in Stochastic Chemical Reaction Networks;550
11.2.5;Almost Universal: Primitive Recursive Computation;552
11.2.5.1;Primitive Recursive Functions;553
11.2.5.2;A Primitive Recursive Bound on the Depth of the Tree of Reachable States;555
11.2.5.2.1;The Algorithm;556
11.2.5.2.2;The Data Structure;557
11.2.5.2.3;The Bound;559
11.2.5.3;The Max-Path Problem;560
11.2.5.3.1;SCRNs for Rows of the Ackermann Function;561
11.2.5.3.2;SCRNs for Primitive Recursive Functions;562
11.2.6;Ordered Program Models: Register Machines and Fractran;563
11.2.6.1;Computation in Stochastic Chemical Reaction Networks;566
11.2.6.1.1;Probability in SCRNs Is Undecidable;567
11.2.6.2;Eliminating Dependency on the Number of Molecules Disables Universal Computation;571
11.2.7;Efficiency of Computation by Stochastic Chemical Reaction Networks;572
11.2.7.1;Stochastic Chemical Reaction Networks Can Efficiently Simulate Turing Machines;572
11.2.7.1.1;The Exploding Computer;573
11.2.7.2;Turing Machines Can Efficiently Simulate Robust Stochastic Chemical Reaction Networks;578
11.2.8;Concluding Remarks;579
11.2.9;References;580
11.3;Log-gain Principles for Metabolic P Systems;583
11.3.1;Introduction;583
11.3.2;The Mass Partition Principle;585
11.3.3;Metabolic P Systems;587
11.3.4;MP Models and Differential Models;591
11.3.4.1;An MP Model of Mitotic Oscillator;592
11.3.5;Metabolic Log-gain Principles;594
11.3.6;Conclusions;600
11.3.7;References;601
11.4;Hybrid Method for Simulating Small-Number Molecular Systems;604
11.4.1;Introduction;604
11.4.2;Background;606
11.4.2.1;Gillespie's Stochastic Simulation Algorithm;606
11.4.2.1.1;Original SSA;606
11.4.2.1.2;tau-Leap Method;607
11.4.2.2;Simulations of Toggle Switches;607
11.4.2.2.1;Toggle Switch with SOS Pathway;607
11.4.2.2.2;Toggle Switch with Quorum-Sensing Signaling Pathway;609
11.4.3;Hybrid Simulation;612
11.4.3.1;Methods;613
11.4.3.1.1;Basic Approach;613
11.4.3.1.2;Iterative Approach;613
11.4.3.2;Results;615
11.4.3.2.1;Basic Approach;615
11.4.3.2.2;Iterative Approach;615
11.4.4;Conclusions;616
11.4.5;References;617
12;Broader Perspective;618
12.1;On Involutions Arising from Graphs;619
12.1.1;Introduction;619
12.1.2;Preliminaries;619
12.1.3;Involutions of Cyclic Groups;620
12.1.4;Involutions of Group Products;622
12.1.5;The set Delta2(Gamma,delta);624
12.1.6;Example: The Case of the Identity Involution;625
12.1.7;References;626
12.2;Parallel Computing by Xeroxing on Transparencies;627
12.2.1;Introduction;627
12.2.2;Constructing an n Variable Truth Table by Xeroxing onto Only n Transparencies;628
12.2.3;Evaluating a Clause over All Truth Settings Simultaneously;629
12.2.4;Completing the Solution;629
12.2.5;Extending the Scope and Observing the Flexibility of Computing by Xerography;630
12.2.6;The Immediate Future;631
12.2.7;References;632
12.3;Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata;634
12.3.1;Introduction;634
12.3.1.1;History and Brief Outline of the Results;634
12.3.1.2;Cellular Automata;635
12.3.1.3;Tilings;637
12.3.1.4;Turing Machines;639
12.3.2;The 2-Way Deterministic Tiling Problem with a Seed Tile;639
12.3.2.1;The Idea for the Undecidability Proof;639
12.3.2.2;The Tile Set for the Given Turing Machine;640
12.3.3;Tile Sets and Cellular Automata;645
12.3.3.1;Interpreting Tile Set as a Cellular Automaton;645
12.3.3.2;Universality of One-Dimensional Reversible Cellular Automata;646
12.3.4;Undecidability Results for Reversible Cellular Automata;647
12.3.4.1;Undecidability of the 2-Way Deterministic Tiling Problem;647
12.3.4.2;Some Undecidability Results for Cellular Automata;648
12.3.4.3;Left Expansivity is Undecidable;652
12.3.5;Discussion;653
12.3.6;References;654
12.4;On Using Divide and Conquer in Modeling Natural Systems;656
12.4.1;Introduction;656
12.4.2;Pancreatic Organogenesis;658
12.4.3;Methods;658
12.4.3.1;Modeling Approach;658
12.4.3.2;Modeling Molecular Interactions;659
12.4.3.3;Modeling Structural Formation;661
12.4.3.4;Combining the Two: The Simulation at Run-Time;661
12.4.4;Results;662
12.4.4.1;Behavior of Population Fits Simple Mathematical Model;662
12.4.4.2;The Emerging Structure Generates Histological Sections;663
12.4.4.3;The Need for Cross-scaling in Pancreatic Organogenesis;665
12.4.5;Discussion;666
12.4.6;References;667
12.5;No Molecule Is an Island: Molecular Evolution and the Study of Sequence Space;670
12.5.1;Introduction;670
12.5.2;The Delicate Clockwork Hypothesis of Molecular Evolution;672
12.5.3;Theory and Experiments with Unevolved Sequences;677
12.5.3.1;Prospects for a Protein Simplex and Exploring Protein Neutral Networks;688
12.5.3.2;No Molecule Is an Island;689
12.5.4;Sequenomics: Mapping the Universe of Sequence Possibilities;692
12.5.4.1;Theoretical Sequenomics;693
12.5.4.2;Sequenomics Visualization;694
12.5.4.3;The Sequenomics Database;694
12.5.4.4;Experimental Sequenomics;695
12.5.5;References;697
12.6;Niching Methods: Speciation Theory Applied for Multi-modal Function Optimization;700
12.6.1;Introduction;700
12.6.2;Motivation: Speciation Theory vs. Conceptual Designs;701
12.6.3;From DNA to Organic Diversity;702
12.6.3.1;A Preliminary Note on Terminology;702
12.6.3.2;Genetic Drift;702
12.6.3.3;Organic Diversity;703
12.6.3.3.1;Variations Within a Species;703
12.6.3.3.2;Speciation;705
12.6.4;Derandomized Evolution Strategies (DES);706
12.6.4.1;Evolutionary Algorithms;706
12.6.4.2;Canonical Evolution Strategies;707
12.6.4.2.1;General;708
12.6.4.2.2;Representation;708
12.6.4.2.3;Mutation;708
12.6.4.2.4;Selection;709
12.6.4.3;Derandomization;709
12.6.5;Introduction to Niching;710
12.6.5.1;Population Diversity in Evolution Strategies;710
12.6.5.2;Diversity Loss in Evolution Strategies;711
12.6.5.2.1;Selective Pressure: Fast Take-over;711
12.6.5.2.2;ES Genetic Drift;711
12.6.5.2.2.1;Recombination Drift;711
12.6.5.2.2.2;Selection Drift;712
12.6.5.3;Neutrality in ES Variations: Mutation Drift;712
12.6.5.3.1;Simulations;713
12.6.5.4;Niching Methods;713
12.6.5.4.1;GA Niching Methods;715
12.6.5.4.2;Niching in Evolution Strategies;715
12.6.6;Proposed Framework: Niching with DES Kernels;716
12.6.6.1;The Proposed Algorithm;716
12.6.6.2;Niching with (1 ,+ lambda) DES Kernels;716
12.6.6.2.1;Algorithm Dynamics;717
12.6.6.2.2;Sizing the Population;718
12.6.6.3;Niche Radius Calculation;718
12.6.7;Experimental Observation;719
12.6.7.1;Extending the Framework: Learning Niche-Shapes;720
12.6.8;Summary and Outlook;720
12.6.9;References;722
12.7;On the Concept of Cis-regulatory Information: From Sequence Motifs to Logic Functions;725
12.7.1;Introduction;725
12.7.2;A Case Study;726
12.7.3;The Gene Naming Problem;728
12.7.4;The Consensus Sequence Bottleneck Problem;730
12.7.4.1;Motif Finding;732
12.7.4.2;Evaluations of Motif-Finding;733
12.7.5;The Logic Function Inference Problem;733
12.7.6;Conclusion;735
12.7.7;References;735