Evolutionary Computation in Bioinformatics (eBook)

Cover 1
Evolutionary Computation in Bioinformatics 4
Copyright Page 5
Contents 8
Preface 18
Contributors 20
Color Plates 418
Part I: Introduction to the Concepts of Bioinformatics and Evolutionary Computation 24
Chapter 1. An Introduction to Bioinformatics for Computer Scientists 26
1.1 Introduction 26
1.2 Biology„The Science of Life 28
1.3 The Central Dogma of Molecular Biology 29
1.4 Gene Networks 38
1.5 Sequence Alignment 39
1.6 Concluding Remarks 40
Chapter 2. An Introduction to Evolutionary Computation for Biologists 42
2.1 Introduction 42
2.2 Evolutionary Computation: History and Terminology 43
2.3 Evolutionary Computation within the Context of Computer Science 49
2.4 Concluding Remarks 58
Part II: Sequence and Structure Alignment 62
Chapter 3. Determining Genome Sequences from Experimental Data Using Evolutionary Computation 64
3.1 Introduction 64
3.2 Formulation of the Sequence Reconstruction Problem 68
3.3 A Hybrid Genetic Algorithm for Sequence Reconstruction 70
3.4 Results from Computational Experiments 72
3.5 Concluding Remarks 78
Chapter 4. Protein Structure Alignment Using Evolutionary Computation 82
4.1 Introduction 82
4.2 Methods 85
4.3 Results and Discussion 94
4.4 Concluding Remarks 107
Chapter 5. Using Genetic Algorithms for Pairwise and Multiple Sequence Alignments 110
5.1 Introduction 110
5.2 Evolutionary Algorithms and Simulated Annealing 114
5.3 SAGA: A Genetic Algorithm Dedicated to Sequence Aligmnent 115
5.4 Applications: Choice of an Appropriate Objective Function 122
5.5 Concluding Remarks 128
Part III: Protein Folding 136
Chapter 6. On the Evolutionary Search for Solutions to the Protein Folding Problem 138
6.1 Introduction 138
6.2 Problem Overview 139
6.3 Protein Computer Models 141
6.4 Discussion 151
6.5 Concluding Remarks 154
Chapter 7. Toward Effective Polypeptide Structure Prediction with Parallel Fast Messy Genetic Algorithms 160
7.1 Introduction 160
7.2 Fast Messy Genetic Algorithms 162
7.3 Experimental Methodology 165
7.4 Protein Structure Prediction with Secondary Structure Computation 174
7.5 Effects of Seeding the Population 178
7.6 Concluding Remarks 179
Chapter 8. Application of Evolutionary Computation to Protein Folding with Specialized Operators 186
8.1 Introduction 186
8.2 Multiple-Criteria Optimization of Protein Conformations 200
8.3 Specialized Variation Operators 203
8.4 GA Performance 206
8.5 Concluding Remarks 211
Part IV: Machine Learning and Inference 216
Chapter 9. Identification of Coding Regions in DNA Sequences Using Evolved Neural Networks 218
9.1 Introduction 218
9.2 Evolved Artificial Neural Networks for Gene Identification 224
9.3 Concluding Remarks 238
Chapter 10. Clustering Microarray Data with Evolutionary Algorithms 242
10.1 Introduction 242
10.2 The k-Means Technique 243
10.3 The ArrayMiner Software 247
10.4 Concluding Remarks 252
Chapter 11. Evolutionary Computation and Fractal Visualization of Sequence Data 254
11.1 Introduction 254
11.2 The Chaos Game 255
11.3 IFSs 261
11.4 Chaos Automata: Adding Memory 266
11.5 Preliminary Conclusions 273
11.6 Concluding Remarks 273
Chapter 12. Identifying Metabolic Pathways and Gene Regulation Networks with Evolutionary Algorithms 278
12.1 Introduction 278
12.2 Reaction Kinetics, Petri Nets, and Functional Petri Nets 281
12.3 The Inverse Problem: Inferring Pathways from Data 282
12.4 Evolving Pathways: Sample Results 285
12.5 Related Work Using Evolutionary Computation for the Inference of Biological Networks 291
12.6 Concluding Remarks 299
Chapter 13. Evolutionary Computational Support for the Characterization of Biological Systems 302
13.1 Introduction 302
13.2 Characterization of Biological Systems with EPR Spectroscopy 304
13.3 Optimization of Spectral Parameters 309
13.4 Experimental Evaluation 310
13.5 Concluding Remarks 316
Part V: Feature Selection 318
Chapter 14. Discovery of Genetic and Environmental Interactions in Disease Data Using Evolutionary Computation 320
14.1 Introduction 320
14.2 Biological Background and Definitions 322
14.3 Mathematical Background and Definitions 324
14.4 The Feature Selection Phase 325
14.5 The Clustering Phase 331
14.6 Experimental Results 333
14.7 Concluding Remarks 338
Chapter 15. Feature Selection Methods Based on Genetic Algorithms for in Silico Drug Design 340
15.1 Introduction 340
15.2 The Feature Selection Problem 342
15.3 HIV-Related QSAR Problem 344
15.4 Feature Selection Methods 346
15.5 GARC 348
15.6 Parameterization and Implementation of GAFEAT 351
15.7 Comparative Results and Discussion 354
15.8 Concluding Remarks 357
Chapter 16. Interpreting Analytical Spectra with Evolutionary Computation 364
16.1 Analytical Spectra in Bioinformatics 364
16.2 Some Instrumentation Issues 365
16.3 Unsupervised and Supervised Learning in Spectral Interpretation 369
16.4 Some General Issues of Model Validation 370
16.5 Selecting Spectral Variables for Modeling 373
16.6 Genetic Regression 375
16.7 Genetic Programming 376
16.8 Making Use of Domain Knowledge 378
16.9 Intelligibility of Models 381
16.10 Model Validation with Evolutionary Algorithms 382
16.11 Applications of Evolutionary Computation in Transcriptomics and Proteomics 383
16.12 Concluding Remarks 385
Appendix. Internet Resources for Bioinformatics Data and Tools 390
A.1 Introduction 390
A.2 Nucleic Acids 390
A.3 Genomes 391
A.4 Expressed Sequence Tags (ESTs) 392
A.5 Single Nucleotide Polymorphisms (SNPs) 392
A.6 RNA Structures 392
A.7 Proteins 393
A.8 Metabolic Pathways 394
A.9 Educational Resources 394
A.10 Software 394
Index 396