Bioinformatics has never been as popular as it is today. The genomics revolution is generating so much data in such rapid succession that it has become difficult for biologists to decipher. In particular, there are many problems in biology that are too large to solve with standard methods. Researchers in evolutionary computation (EC) have turned their attention to these problems. They understand the power of EC to rapidly search very large and complex spaces and return reasonable solutions. While these researchers are increasingly interested in problems from the biological sciences, EC and its problem-solving capabilities are generally not yet understood or applied in the biology community. This book offers a definitive resource to bridge the computer science and biology communities. Gary Fogel and David Corne, well-known representatives of these fields, introduce biology and bioinformatics to computer scientists, and evolutionary computation to biologists and computer scientists unfamiliar with these techniques. The fourteen chapters that follow are written by leading computer scientists and biologists who examine successful applications of evolutionary computation to various problems in the biological sciences. * Describes applications of EC to bioinformatics in a wide variety of areas including DNA sequencing, protein folding, gene and protein classification, drug targeting, drug design, data mining of biological databases, and biodata visualization. * Offers industrial and academic researchers in computer science, biology, and bioinformatics an important resource for applying evolutionary computation. * Includes a detailed appendix of biological data resources.
Inhaltsverzeichnis
1;Cover ;1 2;Evolutionary Computation in Bioinformatics;4 3;Copyright Page ;5 4;Contents ;8 5;Preface;18 6;Contributors;20 7;Color Plates;418 8;Part I: Introduction to the Concepts of Bioinformatics and Evolutionary Computation;24 8.1;Chapter 1. An Introduction to Bioinformatics for Computer Scientists;26 8.1.1;1.1 Introduction;26 8.1.2;1.2 BiologyThe Science of Life;28 8.1.3;1.3 The Central Dogma of Molecular Biology;29 8.1.4;1.4 Gene Networks;38 8.1.5;1.5 Sequence Alignment;39 8.1.6;1.6 Concluding Remarks;40 8.2;Chapter 2. An Introduction to Evolutionary Computation for Biologists;42 8.2.1;2.1 Introduction;42 8.2.2;2.2 Evolutionary Computation: History and Terminology;43 8.2.3;2.3 Evolutionary Computation within the Context of Computer Science;49 8.2.4;2.4 Concluding Remarks;58 9;Part II: Sequence and Structure Alignment;62 9.1;Chapter 3. Determining Genome Sequences from Experimental Data Using Evolutionary Computation;64 9.1.1;3.1 Introduction;64 9.1.2;3.2 Formulation of the Sequence Reconstruction Problem;68 9.1.3;3.3 A Hybrid Genetic Algorithm for Sequence Reconstruction;70 9.1.4;3.4 Results from Computational Experiments;72 9.1.5;3.5 Concluding Remarks;78 9.2;Chapter 4. Protein Structure Alignment Using Evolutionary Computation;82 9.2.1;4.1 Introduction;82 9.2.2;4.2 Methods;85 9.2.3;4.3 Results and Discussion;94 9.2.4;4.4 Concluding Remarks;107 9.3;Chapter 5. Using Genetic Algorithms for Pairwise and Multiple Sequence Alignments;110 9.3.1;5.1 Introduction;110 9.3.2;5.2 Evolutionary Algorithms and Simulated Annealing;114 9.3.3;5.3 SAGA: A Genetic Algorithm Dedicated to Sequence Aligmnent;115 9.3.4;5.4 Applications: Choice of an Appropriate Objective Function;122 9.3.5;5.5 Concluding Remarks;128 10;Part III: Protein Folding;136 10.1;Chapter 6. On the Evolutionary Search for Solutions to the Protein Folding Problem;138 10.1.1;6.1 Introduction;138 10.1.2;6.2 Problem Overview;139 10.1.3;6.3 Protein Computer Models;141 10.1.4;6.4 Discussion;151 10.1.5;6.5 Concludin
g Remarks;154 10.2;Chapter 7. Toward Effective Polypeptide Structure Prediction with Parallel Fast Messy Genetic Algorithms;160 10.2.1;7.1 Introduction;160 10.2.2;7.2 Fast Messy Genetic Algorithms;162 10.2.3;7.3 Experimental Methodology;165 10.2.4;7.4 Protein Structure Prediction with Secondary Structure Computation;174 10.2.5;7.5 Effects of Seeding the Population;178 10.2.6;7.6 Concluding Remarks;179 10.3;Chapter 8. Application of Evolutionary Computation to Protein Folding with Specialized Operators;186 10.3.1;8.1 Introduction;186 10.3.2;8.2 Multiple-Criteria Optimization of Protein Conformations;200 10.3.3;8.3 Specialized Variation Operators;203 10.3.4;8.4 GA Performance;206 10.3.5;8.5 Concluding Remarks;211 11;Part IV: Machine Learning and Inference;216 11.1;Chapter 9. Identification of Coding Regions in DNA Sequences Using Evolved Neural Networks;218 11.1.1;9.1 Introduction;218 11.1.2;9.2 Evolved Artificial Neural Networks for Gene Identification;224 11.1.3;9.3 Concluding Remarks;238 11.2;Chapter 10. Clustering Microarray Data with Evolutionary Algorithms;242 11.2.1;10.1 Introduction;242 11.2.2;10.2 The k-Means Technique;243 11.2.3;10.3 The ArrayMiner Software;247 11.2.4;10.4 Concluding Remarks;252 11.3;Chapter 11. Evolutionary Computation and Fractal Visualization of Sequence Data;254 11.3.1;11.1 Introduction;254 11.3.2;11.2 The Chaos Game;255 11.3.3;11.3 IFSs;261 11.3.4;11.4 Chaos Automata: Adding Memory;266 11.3.5;11.5 Preliminary Conclusions;273 11.3.6;11.6 Concluding Remarks;273 11.4;Chapter 12. Identifying Metabolic Pathways and Gene Regulation Networks with Evolutionary Algorithms;278 11.4.1;12.1 Introduction;278 11.4.2;12.2 Reaction Kinetics, Petri Nets, and Functional Petri Nets;281 11.4.3;12.3 The Inverse Problem: Inferring Pathways from Data;282 11.4.4;12.4 Evolving Pathways: Sample Results;285 11.4.5;12.5 Related Work Using Evolutionary Computation for the Inference of Biological Networks;291 11.4.6;12.6 Concluding Remarks;299 11.5;Chapter 13. Evolu
tionary Computational Support for the Characterization of Biological Systems;302 11.5.1;13.1 Introduction;302 11.5.2;13.2 Characterization of Biological Systems with EPR Spectroscopy;304 11.5.3;13.3 Optimization of Spectral Parameters;309 11.5.4;13.4 Experimental Evaluation;310 11.5.5;13.5 Concluding Remarks;316 12;Part V: Feature Selection;318 12.1;Chapter 14. Discovery of Genetic and Environmental Interactions in Disease Data Using Evolutionary Computation;320 12.1.1;14.1 Introduction;320 12.1.2;14.2 Biological Background and Definitions;322 12.1.3;14.3 Mathematical Background and Definitions;324 12.1.4;14.4 The Feature Selection Phase;325 12.1.5;14.5 The Clustering Phase;331 12.1.6;14.6 Experimental Results;333 12.1.7;14.7 Concluding Remarks;338 12.2;Chapter 15. Feature Selection Methods Based on Genetic Algorithms for in Silico Drug Design;340 12.2.1;15.1 Introduction;340 12.2.2;15.2 The Feature Selection Problem;342 12.2.3;15.3 HIV-Related QSAR Problem;344 12.2.4;15.4 Feature Selection Methods;346 12.2.5;15.5 GARC;348 12.2.6;15.6 Parameterization and Implementation of GAFEAT;351 12.2.7;15.7 Comparative Results and Discussion;354 12.2.8;15.8 Concluding Remarks ;357 12.3;Chapter 16. Interpreting Analytical Spectra with Evolutionary Computation;364 12.3.1;16.1 Analytical Spectra in Bioinformatics;364 12.3.2;16.2 Some Instrumentation Issues;365 12.3.3;16.3 Unsupervised and Supervised Learning in Spectral Interpretation;369 12.3.4;16.4 Some General Issues of Model Validation;370 12.3.5;16.5 Selecting Spectral Variables for Modeling;373 12.3.6;16.6 Genetic Regression;375 12.3.7;16.7 Genetic Programming;376 12.3.8;16.8 Making Use of Domain Knowledge;378 12.3.9;16.9 Intelligibility of Models;381 12.3.10;16.10 Model Validation with Evolutionary Algorithms;382 12.3.11;16.11 Applications of Evolutionary Computation in Transcriptomics and Proteomics;383 12.3.12;16.12 Concluding Remarks;385 13;Appendix. Internet Resources for Bioinformatics Data and Tools;390 13.1;A.1 Intro
duction;390 13.2;A.2 Nucleic Acids;390 13.3;A.3 Genomes;391 13.4;A.4 Expressed Sequence Tags (ESTs);392 13.5;A.5 Single Nucleotide Polymorphisms (SNPs);392 13.6;A.6 RNA Structures;392 13.7;A.7 Proteins;393 13.8;A.8 Metabolic Pathways;394 13.9;A.9 Educational Resources;394 13.10;A.10 Software;394 14;Index;396