Chemical programming to eploit chemical reaction systems for computation [Elektronische Ressource] / von Naoki Matsumaru

Sujets

• Informatik
• Mathematics

Informations

• Publié par: friedrich-schiller-universitat_jena
• Publié le: 01 janvier 2009
• Nombre de lectures: 5
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Chemical Programming
to Exploit Chemical Reaction Systems
for Computation
Dissertation
zur Erlangung des akademischen Grades
doctor rerum naturalium (Dr. rer. nat.)
vorgelegt dem Rat der Fakult at fur Mathematik und Informatik
der Friedrich-Schiller-Universit at Jena
von
Naoki Matsumaru
geboren am Aichi, Japan
in 28. Aug. 1974Gutachter
1. : PD Dr. habil. Peter Dittrich
2. : Prof. Dr.-Ing. Dietmar Fey
3. : Prof. Andy Adamatzky
Tag der letzten Prufung des Rigorosums: 20. Aug. 2009
Tag der o en tlichen Verteidigung: 27. Aug. 2009Chemical Programming
to Exploit Chemical Reaction Systems
for Computation
Dissertation
to receive the degree Dr. rer. nat. from the
Department of Mathematics and Computer Science
Friedrich-Schiller-University Jena
Germany
submitted by
Naoki Matsumaru
born in Aichi, Japan
on 28. Aug. 1974Committee members
1. : PD Dr. habil. Peter Dittrich
2. : Prof. Dr.-Ing. Dietmar Fey
3. : Prof. Andy Adamatzky
Date of the last examination: 20. Aug. 2009
Date of the public defense: 27. Aug. 2009Dedication
To my family.Table of Contents
Part I: Constructive Design 3
0.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.2 Motivations to Chemical Programming . . . . . . . . . . . . . . 4
1 Theory of Chemical Organizations 9
1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Terminology and Notation . . . . . . . . . . . . . . . . . . . . . 10
1.3 Core Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Dynamical Part . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Summary and Discussion . . . . . . . . . . . . . . . . . . . . . 15
2 Case Study of Chemical Organization Theory 17
2.1 HIV Immunological Population Dynamics Model . . . . . . . . 17
2.2 Comparison of HIV Models . . . . . . . . . . . . . . . . . . . . 21
3 Chemical Boolean Devices 29
3.1 A Recipe For A Chemical Logic Circuit . . . . . . . . . . . . . 30
3.2 Case Study I: A Chemical XOR . . . . . . . . . . . . . . . . . 32
3.3 Case II: Multiple Logic Gates . . . . . . . . . . . . . . . 36
3.4 Case Study III: A Chemical Flip-Flop . . . . . . . . . . . . . . 39
3.5 Case IV: An Oscillator . . . . . . . . . . . . . . . . . . . 42
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4 Maximal Independent Set Problem 47
4.1 Chemical Programming for the MIS problem . . . . . . . . . . 48
4.2 Proof of exact correspondence between MISs and organizations
of size N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3 Examples of Chemical Programming to Solve the MIS Problem 54
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5 Conclusion and Outlook 59
5.1 Organization-Oriented Programming . . . . . . . . . . . . . . . 60
5.2 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Part II: Autonomous Design 67
6 Comparing Evolved Reaction Networks with Constructed
Reaction Networks 69
6.1 Method of Evolutionary Design . . . . . . . . . . . . . . . . . . 70
iii TABLE OF CONTENTS
6.2 Evolutionary Process . . . . . . . . . . . . . . . . . . . . . . . . 71
6.3 Analysis of Evolved Network . . . . . . . . . . . . . . . . . . . 73
6.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7 Tracking Chemical Evolution 79
7.1 Two Levels of Chemical Evolution . . . . . . . . . . . . . . . . 80
7.2 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . 80
7.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.4 Discussion and Conclusion . . . . . . . . . . . . . . . . . . . . . 88
8 Scouting: an Exploration algorithm 91
8.1 Exploration as Design Approach . . . . . . . . . . . . . . . . . 91
8.2 Scouting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 92
8.3 The Self-adaptive Scouting Algorithm . . . . . . . . . . . . . . 94
8.4 Scouting an HIV-immune System Model . . . . . . . . . . . . . 96
8.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . 99
9 Further Applications of Scouting 103
9.1 Scouting Enzyme Behavior . . . . . . . . . . . . . . . . . . . . 103
9.2 Arti cial life as an Aid to Astrobiology . . . . . . . . . . . . . . 106
10 Hybrid Approach 111
Bibliography 113List of Tables
2.1 Reaction network model of HIV immunological response . . . . . . 19
2.2 Three levels of model abstraction . . . . . . . . . . . . . . . . . . . 25
3.1 Recipe of chemical boolean circuits . . . . . . . . . . . . . . . . . . 32
4.1 Recipe of reaction networks for maximal independent set problem 50
7.1 Code of automata chemistry dynamics . . . . . . . . . . . . . . . . 83
7.2 Codes to generate closed set . . . . . . . . . . . . . . . . . . . . . . 83
7.3 Codes to self-maintaining set . . . . . . . . . . . . . . . . 84
8.1 Code of self-adaptive scouting . . . . . . . . . . . . . . . . . . . . . 96
9.1 Reaction network for life search scenario . . . . . . . . . . . . . . . 109
iiiList of Figures
2.1 Organizational analysis of HIV immunological response model . . . 20
2.2 Two treatment strategies based on organizational analysis . . . . . 20
3.1 Analysis of organizational structures within chemical xor . . . . . 34
3.2 Dynamic behavior of chemical xor . . . . . . . . . . . . . . . . . . 35
3.3 Analysis of structures within chemicalnand consist-
ing of two gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4 Analysis of organizational structures within chemical or consisting
of three gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5 Analysis of hierarchical organizational structure within chemical
ip- op . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.6 Dynamic behavior of chemical ip- op . . . . . . . . . . . . . . . . 41
3.7 Analysis of organizational structures of chemical oscillator . . . . . 43
3.8 Dynamic behavior of a chemical oscillator . . . . . . . . . . . . . . 45
4.1 MIS simple solution . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2 Analysis of organizational structure on MIS problem instance with
linear graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3 Analysis of structures on MIS problem instance with
circular graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4 Analysis of organizational structure on MIS problem instance with
six vertex graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.5 Forty nine organizations constitute hierarchy on MIS problem in-
stance with six vertex graph . . . . . . . . . . . . . . . . . . . . . . 58
5.1 Benchmark problem scenario for quantitative evaluation of chemical
programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 Chemical programming workbench architecture . . . . . . . . . . . 64
6.1 Circuit diagram and operation mode of ip-op. . . . . . . . . . . 70
6.2 Average tness value in evolutions of chemical ip- op . . . . . . . 71
6.3 Average number of organizations in evolutions of chemical ip- op 72
6.4 Reaction network of chemical ip op designed by evolution . . . . 74
6.5 Organizational structure in the reaction network shown in Figure 6.4. 75
6.6 Dynamical simulation of chemical ip- op designed by evolution . 76
7.1 Two levels of chemical evolution . . . . . . . . . . . . . . . . . . . 81
7.2 Dynamical downward movements . . . . . . . . . . . . . . . . . . . 85
7.3 sideward and upward movements . . . . . . . . . . . . 87
7.4 Dynamical downward movement . . . . . . . . . . . . . . . . . . . 89
iv