ISBN: 3540407952
TITLE: Computation in Living Cells
AUTHOR: Ehrenfeucht et al.
TOC:

Notation XIII
Part I Biological Background
1 An Overview of the Cell 3
1.1 Cells 3
1.2 Major Components of Eukaryotic Cells 6
1.3 Chromosome Structure 8
1.4 Chromosornes and Genes 14
Notes on References 21
2 Ciliates 23
2.1 Defining Characteristics of Ciliates 23
2.2 Nuclear Dualism 25
2.3 Micronuclear Versus Macronuclear DNA 28 Notes an References 35
3 Molecular Operations for Gene Assembly 37
3.1 Homologous Recombination 37
3.2 Three Molecular Operatioris 39
Notes on References 43
Part II Formal Modelling of Gene Assembly
4 Model Forming 47
4.1 Formalizing Genes 47
4.2 Levels of Abstraction 51
4.3 Formalizing Molecular Operations 53
4.4 Marriage of Models 55
Notes on References 56
5 Mathematical Preliminaries 57
5.1 Sets and Functions 57
5.2 Strings 58
5.3 Signed Strings 59
5.4 Circular Strings 61
5.5 Graphs 62
Notes an References 65
6 MDS Arrangements and MDS Descriptors 67
6.1 MDS Arrangements 67
6.2 MDS Descriptors 69
Notes an References 73
7 MDS Descriptor Pointer Reduction System 75
7.1 Assembly Operations an MDS Descriptors 75
7.2 The Assembling Power of the Operations 80
Notes on References 81
8 Legal Strings 83
8.1 Representation by Legal Strings 83
8.2 Realizable Legal Strings 85
Notes on References 90
9 String Pointer Reduction System 91
9.1 Assembly Operations an Strings 91
9.2 Equivalence to Descriptor Pointer Reduction System 93
9.2.1 Ld and Snr 93
9.2.2 Hiand Spr 95
9.2.3 DIad and Sdr 96
Notes on References 97
10 Overlap Graphs 99
10.1 Overlap Graphs of Legal Strings 99
10.2 Realizable Graphs 102
10.3 The Overlap Equivalence Problem 105
Notes on References 108
11 Graph Pointer Reduction System 109
11.1 Assembly Operations on Graphs 109
11.2 Equivalence to String Pointer Reduction System 112
11.2.1 From snr to gnr 112
11.2.2 From spr to gpr 113
11.2.3 From sdr to gdr 113
11.2.4 Reverse Implications 115
Notes on References 117
Part III Properties of Gene Assembly
12 Invariants 121
12.1 MDS-IES Descriptors 121
12.2 Invariant Theorem 126
Notes on References 129
13 Patterns of Subsets of Rules 131
13.1 Small Reductions 131
13.2 Disjoint Cycles 133
13.3 Subsets of Successful Patterns 138
13.3.1 snr 138
13.3.2 snr and spr 139
13.3.3 snr and sdr 141
13.3.4 spr 143
13.3.5 sdr 145
13.3.6 spr and sdr 147
13.4 Complexity of Reductions 147
Notes on References 149
14 Gene Assembly Through Cyclic Graph Decomposition 151
14.1 Graphs with Labels and Colors 151
14.2 Folding on MI-graph 156
14.3 Unfolding Paired MI-graphs 159
14.4 Assembled MI-graphs of Genomes 164
14.5 Intracyclic Unfolding 166
Notes on References 175
Part IV Epilogue
15 Intermolecular Model 179
15.1 String Rules 179
15.2 The Intermolecular Model in Terms of Signed Strings 180
15.3 Invariants of the Intermolecular Model 182
Notes on References 184
16 Discussion 187
16.1 Between Biology and Computer Science 187
16.2 Gene Assembly Strategies 188
16.3 Scope of the Operations 189
16.4 Pointer Alignment 190
Notes on References 191
References 193
Index 197
END

