E-grāmata: Evolutionary Computation in Bioinformatics

Preface		xvii
Contributors		xix
PART I Introduction to the Concepts of Bioinformatics and Evolutionary Computation		1	(38)
An Introduction to Bioinformatics for Computer Scientists		3	(16)
David W. Corne
Gary B. Fogel
Introduction		3	(2)
Biology---The Science of Life		5	(1)
The Central Dogma of Molecular Biology		6	(9)
Anatomy of a DNA Sequence		10	(1)
Transcription and Translation		11	(1)
Proteins		12	(3)
Gene Networks		15	(1)
Sequence Alignment		16	(1)
Concluding Remarks		17	(2)
An Introduction to Evolutionary Computation for Biologists		19	(20)
Gary B. Fogel
David W. Corne
Introduction		19	(1)
Evolutionary Computation: History and Terminology		20	(6)
Initialization		22	(1)
Variation		22	(2)
Selection		24	(1)
Additional Parameters and Testing		25	(1)
Self-Adaptation		25	(1)
Theory		26	(1)
Evolutionary Computation within the Context of Computer Science		26	(9)
Local Search		29	(3)
Simulated Annealing		32	(1)
Population-Based Search		33	(2)
Concluding Remarks		35	(4)
PART II Sequence and Structure Alignment		39	(74)
Determining Genome Sequences from Experimental Data Using Evolutionary Computation		41	(18)
Jacek Blazewicz
Marta Kasprzak
Introduction		41	(4)
Sequencing by Hybridization		41	(2)
Example: Reconstruction of Sequence from an Ideal Spectrum		43	(1)
Experimental Errors in the Spectrum		43	(2)
Formulation of the Sequence Reconstruction Problem		45	(2)
An Integer Programming Formulation		45	(1)
Example: Reconstruction of Sequence from a Spectrum Containing Errors		46	(1)
A Hybrid Genetic Algorithm for Sequence Reconstruction		47	(2)
Results from Computational Experiments		49	(6)
Concluding Remarks		55	(4)
Protein Structure Alignment Using Evolutionary Computation		59	(28)
Joseph D. Szustakowski
Zhipeng Weng
Introduction		59	(3)
Structure Alignment Algorithms		60	(1)
The K2 Algorithm		61	(1)
Methods		62	(9)
Stage 1: SSE Alignments		63	(2)
Stage 2: Detailed Alignments Using a Genetic Algorithm		65	(4)
Stage 3: Three-Dimensional Superposition		69	(1)
Evaluation of Statistical Significance		69	(2)
Results and Discussion		71	(13)
Difficult Cases		72	(1)
GA Performance Characteristics		73	(6)
Statistical Significance		79	(5)
Concluding Remarks		84	(3)
Using Genetic Algorithms for Pairwise and Multiple Sequence Alignments		87	(26)
Cedric Notredame
Introduction		87	(4)
Standard Optimization Algorithms		88	(1)
The Objective Function		89	(2)
Evolutionary Algorithms and Simulated Annealing		91	(1)
SAGA: A Genetic Algorithm Dedicated to Sequence Alignment		92	(7)
Initialization		92	(1)
Evaluation		93	(1)
Reproduction, Variation, and Termination		94	(1)
Designing the Variation Operators		94	(1)
Crossover Operators		95	(1)
Mutation Operators: A Gap Insertion Operator		95	(1)
Dynamic Scheduling of Operators		95	(3)
Parallelization of SAGA		98	(1)
Applications: Choice of an Appropriate Objective Function		99	(6)
Weighted Sums of Pairs		100	(1)
Consistency-Based Objective Functions: The COFFEE Score		101	(2)
Taking Nonlocal Interactions into Account: RAGA		103	(2)
Concluding Remarks		105	(8)
PART III Protein Folding		113	(80)
On the Evolutionary Search for Solutions to the Protein Folding Problem		115	(22)
Garrison W. Greenwood
Jae-Min Shin
Introduction		115	(1)
Problem Overview		116	(2)
Protein Computer Models		118	(10)
Minimalist Models		118	(4)
Side-Chain Packing		122	(4)
Docking		126	(2)
Discussion		128	(3)
Chemistry at HARvard Molecular Mechanics (CHARMm)		129	(1)
Assisted Model Building with Energy Refinement (AMBER)		129	(1)
On Force Fields and Evolutionary Algorithms		130	(1)
Concluding Remarks		131	(6)
Virtual Backbone Modeling		131	(1)
Full Modeling of the Side Chains		132	(1)
Development of an Empirical Energy Function to Measure Fitness		132	(1)
A Realistic Assessment of a Search Strategy		133	(4)
Toward Effective Polypeptide Structure Prediction with Parallel Fast Messy Genetic Algorithms		137	(26)
Gary B. Lamont
Laurence D. Merkle
Introduction		137	(2)
Fast Messy Genetic Algorithms		139	(3)
mGA Operators		139	(2)
Fast mGA Operators		141	(1)
Experimental Methodology		142	(9)
Test-Case Proteins		142	(3)
The Energy Model		145	(1)
The Computing Environment		145	(1)
Algorithmic Parameters		145	(1)
Memetic Algorithms		145	(1)
Handling the Steric Constraints		146	(4)
Secondary Structure		150	(1)
Protein Structure Prediction with Secondary Structure Computation		151	(4)
Effects of Seeding the Population		155	(1)
Concluding Remarks		156	(7)
Application of Evolutionary Computation to Protein Folding with Specialized Operators		163	(30)
Steffen Schulze-Kremer
Introduction		163	(14)
Representation Formalism		164	(2)
Fitness Function		166	(1)
Conformational Energy		167	(1)
Variation Operators		168	(3)
Ab Initio Prediction		171	(4)
Side Chain Placement		175	(2)
Multiple-Criteria Optimization of Protein Conformations		177	(3)
Specialized Variation Operators		180	(3)
Preferred Backbone Conformations		181	(1)
Secondary Structure		182	(1)
GA Performance		183	(5)
Concluding Remarks		188	(5)
PART IV Machine Learning and Inference		193	(102)
Identification of Coding Regions in DNA Sequences Using Evolved Neural Networks		195	(24)
Gary B. Fogel
Kumar Chellapilla
David B. Fogel
Introduction		195	(6)
Artificial Neural Networks for Pattern Recognition		197	(2)
Evolutionary Computation and Neural Networks		199	(2)
Evolved Artificial Neural Networks for Gene Identification		201	(14)
Coding Indicators		202	(3)
Classification and Postprocessing		205	(2)
Performance on Training Data		207	(1)
Performance on Test Data		208	(7)
Concluding Remarks		215	(4)
Clustering Microarray Data with Evolutionary Algorithms		219	(12)
Emanuel Falkenauer
Arnaud Marchand
Introduction		219	(1)
The k-Means Technique		220	(4)
Algorithmic Issues		220	(1)
The Caveat		221	(3)
The ArrayMiner Software		224	(5)
The Grouping Genetic Algorithm		224	(2)
The Use of GGA within ArrayMiner		226	(1)
Why Does It Matter in Practice?		226	(1)
ArrayMiner's Performance: Solution Quality and Speed		227	(2)
Concluding Remarks		229	(2)
Evolutionary Computation and Fractal Visualization of Sequence Data		231	(24)
Dan Ashlock
Jim Golden
Introduction		231	(1)
The Chaos Game		232	(6)
IFSs		238	(5)
Evolvable Fractals		239	(2)
Designing the Evolutionary Algorithm		241	(2)
Results for IFSs		243	(1)
Chaos Automata: Adding Memory		243	(7)
The Data Structure and Its Variation Operators		245	(1)
Evolution and Fitness		246	(1)
The Evolutionary Algorithm		247	(1)
Experimental Design		248	(1)
Results		248	(2)
Preliminary Conclusions		250	(1)
Concluding Remarks		250	(5)
Applications		251	(1)
Fitness		252	(1)
Other Fractal Chromosomes		252	(1)
More General Contraction Maps		253	(2)
Identifying Metabolic Pathways and Gene Regulation Networks with Evolutionary Algorithms		255	(24)
Junji Kitagawa
Hitoshi Iba
Introduction		255	(3)
The Importance of Inferring Biological Networks		256	(1)
Representing Biological Networks with Petri Nets		256	(2)
Reaction Kinetics, Petri Nets, and Functional Petri Nets		258	(1)
Petri Nets		258	(1)
Functional Petri Nets		259	(1)
The Inverse Problem: Inferring Pathways from Data		259	(3)
The Encoding Scheme		260	(2)
The Fitness Function		262	(1)
Evolving Pathways: Sample Results		262	(6)
A Simple Metabolic Pathway		262	(1)
Random Target Pathways		263	(1)
Inferring the Phospholipid Pathway		264	(4)
Related Work Using Evolutionary Computation for the Inference of Biological Networks		268	(8)
Biological Network Inference with Genetic Programming		268	(4)
Inference of Gene Regulatory Networks		272	(3)
Interactive Simulation Systems for Biological Network Inference		275	(1)
Concluding Remarks		276	(3)
Evolutionary Computational Support for the Characterization of Biological Systems		279	(16)
Bogdan Filipic
Janez Strancar
Introduction		279	(2)
Characterization of Biological Systems with EPR Spectroscopy		281	(5)
EPR Spectrum-Simulation Model		282	(2)
The Role of Spectral Parameters		284	(2)
Optimization of Spectral Parameters		286	(1)
Experimental Evaluation		287	(6)
Concluding Remarks		293	(2)
PART V Feature Selection		295	(72)
Discovery of Genetic and Environmental Interactions in Disease Data Using Evolutionary Computation		297	(20)
Laetitia Jourdan
Clarisse Dhaenens-Flipo
El-Ghazali Talbi
Introduction		297	(2)
Biological Background and Definitions		299	(2)
Mathematical Background and Definitions		301	(1)
The Feature Selection Phase		302	(6)
Feature Subset Selection		302	(2)
Candidate Solution Encoding and a Distance Measure		304	(1)
The Fitness Function		305	(1)
The Genetic Operators		306	(1)
The Selection Scheme		307	(1)
Random Immigrants		308	(1)
The Clustering Phase		308	(2)
Objective of the Clustering Phase		309	(1)
Application of k-Means		309	(1)
Experimental Results		310	(5)
Experiments on Artificial Data		310	(2)
Experiments on Real Data		312	(3)
Concluding Remarks		315	(2)
Feature Selection Methods Based on Genetic Algorithms for in Silico Drug Design		317	(24)
Mark J. Embrechts
Muhsin Ozdemir
Larry Lockwood
Curt Breneman
Kristin Bennett
Dirk Devogelaere
Marcel Rijckaert
Introduction		317	(2)
The Feature Selection Problem		319	(2)
HIV-Related QSAR Problem		321	(2)
Prediction Measures		321	(1)
Predictive Modeling		322	(1)
Feature Selection Methods		323	(2)
GA-Supervised Scaled Regression Clustering (GARC)		324	(1)
GAFEAT		324	(1)
GARC		325	(3)
GA-Driven Supervised Clustering		326	(1)
Supervised Regression Clustering with Local Learning		326	(1)
Supervised Scaled Regression Clustering		327	(1)
Parameterization and Implementation of GAFEAT		328	(3)
Variation Operators		329	(1)
Correlation Matrix-Based Evaluation Function		330	(1)
Rank-Based Selection Scheme		330	(1)
Comparative Results and Discussion		331	(3)
Concluding Remarks		334	(7)
Interpreting Analytical Spectra with Evolutionary Computation		341	(26)
Jem J. Rowland
Analytical Spectra in Bioinformatics		341	(1)
Some Instrumentation Issues		342	(4)
Unsupervised and Supervised Learning in Spectral Interpretation		346	(1)
Some General Issues of Model Validation		347	(3)
Selecting Spectral Variables for Modeling		350	(2)
Genetic Regression		352	(1)
Genetic Programming		353	(2)
Making Use of Domain Knowledge		355	(3)
Intelligibility of Models		358	(1)
Model Validation with Evolutionary Algorithms		359	(1)
Applications of Evolutionary Computation in Transcriptomics and Proteomics		360	(2)
Concluding Remarks		362	(5)
Appendix: Internet Resources for Bioinformatics Data and Tools		367	(6)
A.1 Introduction		367	(1)
A.2 Nucleic Acids		367	(1)
A.3 Genomes		368	(1)
A.4 Expressed Sequence Tags (ESTs)		369	(1)
A.5 Single Nucleotide Polymorphisms (SNPs)		369	(1)
A.6 RNA Structures		369	(1)
A.7 Proteins		370	(1)
A.8 Metabolic Pathways		371	(1)
A.9 Educational Resources		371	(1)
A.10 Software		371	(2)
Index		373

Gary B. Fogel is a senior staff scientist at Natural Selection, Inc., in La Jolla, California.His research interests include the application of evolutionary computationto problems in the biomedical sciences and evolutionary biology. He received aB.A. in biology from the University of California, Santa Cruz, in 1991 and a Ph.D.in biology from the University of California, Los Angeles, in 1998 with a focus onevolutionary biology. While at UCLA, Dr. Fogel was a fellow of the Center for theStudy of Evolution and the Origin of Life and earned several teaching and researchawards. He is a current member of the International Society for the Studyof the Origin of Life, the Society for the Study of Evolution, IEEE, Sigma Xi, andthe Evolutionary Programming Society. He currently serves as an associate editorfor IEEE Transactions on Evolutionary Computation and BioSystems and was a technicalco-chair for the recent 2000 Congress on Evolutionary Computation. He is alsoa senior staff scientist at the Center for Excellence in Evolutionary Computation,a nonprofit organization that promotes scientific research and development ofevolutionary algorithms. David W. Corne is a reader in evolutionary computation (EC) at the University of Reading. His early research on evolutionary timetabling (with Peter Ross) resultedin the first freely available and successful EC-based general timetabling programfor educational and other institutions. His later EC work has been in suchareas as DNA pattern mining, promoter modeling, phylogeny, scheduling, layoutdesign, telecommunications, data mining, algorithm comparison issues, and multiobjectiveoptimization. Recent funded work (with Douglas Kell) applies EC directlyto the in vivo optimization of proteins. He is an associate editor of the IEEETransactions on Evolutionary Computation and a founding co-editor of the Journal ofScheduling. Dr. Corne is on the editorial boards of Applied Soft Computing and the InternationalJournal of Systems Science, and he serves on a host of international conferenceprogram committees. Other recent edited books include New Ideas in Optimization(with Marco Dorigo and Fred Glover), Telecommunications Optimization: Heuristic andAdaptive Techniques (with Martin Oates and George Smith), and Creative EvolutionarySystems (with Peter Bentley). He is also a director of Evosolve (United Kingdomregistered charity number 1086384, with Jeanne Lynch-Aird, Paul Marrow, GlenysOates, and Martin Oates), a nonprofit organization that promotes the use of advancedcomputation technologies to enhance the quality of life.