Computation in Living Cells

by Ehrenfeucht, Andrzej; Harju, Tero; Petre, Ion; Prescott, David M.; Rosenberg, Grzegorz

• ISBN13: 9783540407959
• ISBN10: 3540407952
• Format: Hardcover
• Copyright: 2004-01-01
• Publisher: Springer Verlag

Summary

Natural Computing is concerned with computation that is taking place in Nature. The investigation of computations in living cells is one of the central and fastest growing areas of research in this field. Gene assembly in ciliates (unicellular organisms) is a splendid example of such computations, and it is fascinating from both the biological and the computational viewpoints. As a matter of fact, both biology and the science of computation have benefited from the interdisciplinary research on the computational nature of gene assembly - this work has helped to clarify important biological aspects of gene assembly, yielded novel insights into the nature of computation, and broadened our understanding of what computation is about. This monograph gives an accessible account of both the biology and the formal analysis of the gene assembly process. It can be used as a textbook for either graduate courses or seminars.

Author Biography

Prof. Rozenberg is multiple Springer author/editor of, e.g., the LNCS series Advances in Petri Nets, of ICALP proceedings, of  "DNA Computing - New Computing Paradigms" by George Paun, Grzegorz Rozenberg, Arto Salomaa, of the "Handbook of Formal Languages" edited by Grzegorz Rozenberg, Arto Salomaa (3 volumes). Rozenberg is also founding editor of the EATCS Texts and Monographs Series and the Natural Computing Series.

Table of Contents

Notation	p. XIII
Biological Background
An Overview of the Cell	p. 3
Cells	p. 3
Major Components of Eukaryotic Cells	p. 6
Chromosome Structure	p. 8
Chromosomes and Genes	p. 14
Notes on References	p. 21
Ciliates	p. 23
Defining Characteristics of Ciliates	p. 23
Nuclear Dualism	p. 25
Micronuclear Versus Macronuclear DNA	p. 28
Notes on References	p. 35
Molecular Operations for Gene Assembly	p. 37
Homologous Recombination	p. 37
Three Molecular Operations	p. 39
Notes on References	p. 43
Formal Modelling of Gene Assembly
Model Forming	p. 47
Formalizing Genes	p. 47
Levels of Abstraction	p. 51
Formalizing Molecular Operations	p. 53
Marriage of Models	p. 55
Notes on References	p. 56
Mathematical Preliminaries	p. 57
Sets and Functions	p. 57
Strings	p. 58
Signed Strings	p. 59
Circular Strings	p. 61
Graphs	p. 62
Notes on References	p. 65
MDS Arrangements and MDS Descriptors	p. 67
MDS Arrangements	p. 67
MDS Descriptors	p. 69
Notes on References	p. 73
MDS Descriptor Pointer Reduction System	p. 75
Assembly Operations on MDS Descriptors	p. 75
The Assembling Power of the Operations	p. 80
Notes on References	p. 81
Legal Strings	p. 83
Representation by Legal Strings	p. 83
Realizable Legal Strings	p. 85
Notes on References	p. 90
String Pointer Reduction System	p. 91
Assembly Operations on Strings	p. 91
Equivalence to Descriptor Pointer Reduction System	p. 93
Ld and Snr	p. 93
Hi and Spr	p. 95
Dlad and Sdr	p. 96
Notes on References	p. 97
Overlap Graphs	p. 99
Overlap Graphs of Legal Strings	p. 99
Realizable Graphs	p. 102
The Overlap Equivalence Problem	p. 105
Notes on References	p. 108
Graph Pointer Reduction System	p. 109
Assembly Operations on Graphs	p. 109
Equivalence to String Pointer Reduction System	p. 112
From snr to gnr	p. 112
From spr to gpr	p. 113
From sdr to gdr	p. 113
Reverse Implications	p. 115
Notes on References	p. 117
Properties of Gene Assembly
Invariants	p. 121
MDS-IES Descriptors	p. 121
Invariant Theorem	p. 126
Notes on References	p. 129
Patterns of Subsets of Rules	p. 131
Small Reductions	p. 131
Disjoint Cycles	p. 133
Subsets of Successful Patterns	p. 138
snr	p. 138
snr and spr	p. 139
snr and sdr	p. 141
spr	p. 143
sdr	p. 145
spr and sdr	p. 147
Complexity of Reductions	p. 147
Notes on References	p. 149
Gene Assembly Through Cyclic Graph Decomposition	p. 151
Graphs with Labels and Colors	p. 151
Folding an Mi-graph	p. 156
Unfolding Paired Mi-graphs	p. 159
Assembled Mi-graphs of Genomes	p. 164
Intracyclic Unfolding	p. 166
Notes on References	p. 175
Epilogue
Intermolecular Model	p. 179
String Rules	p. 179
The Intermolecular Model in Terms of Signed Strings	p. 180
Invariants of the Intermolecular Model	p. 182
Notes on References	p. 184
Discussion	p. 187
Between Biology and Computer Science	p. 187
Gene Assembly Strategies	p. 188
Scope of the Operations	p. 189
Pointer Alignment	p. 190
Notes on References	p. 191
References	p. 193
Index	p. 197
Table of Contents provided by Publisher. All Rights Reserved.