Evolutionary Computation in Bioinformatics

Rating:
Summary: Significant Addition to Biocomputing
Review: I like this book. Bioinformatics is a ripe area for applying evolutionary algorithms and the book provides a good overview of many different applications. Some chapters are more polished than others, but that's to be expected. The editors do an excellent job of introducing both bioinformatics and evolutionary computation to their respective audiences. I can't think of another book that makes such an effort to integrate the two communities.

I see another reviewer gave the book 3 stars. I've no idea why. The book is excellent, and has encouraged me to take a look at other papers in this area.

Rating:
Summary: A good literature survey
Review: The subject of this book would seem a natural one, given the evolutionary paradigm in biology. Genetic algorithms and evolutionary programming have now found use in many different fields such as physics, financial engineering, network modeling, and computational radiology, to name a few. This use will no doubt continue as computer processing power increases in the future. Although genetic/evolutionary approaches are still much more effective from a computational point of view than strict combinatorial ones, they are still very time intensive, and for many problems have yet to compete with ordinary Monte Carlo techniques. This book gives a brief overview of how evolutionary algorithms are used in bioinformatics, with emphasis on genetic sequence alignment and protein folding. The book does not offer in-depth discussion on these algorithms, but does give references where more information can be obtained. Therefore the book could be described as a literature survey, at least for the chapters that I read, which did not include those on protein folding.

The book is written for the computer scientist who wants to move into bioinformatics, and the biologist, who needs more background in these types of algorithms. Therefore, the editors of the book include two introductory chapters, one introducing bioinformatics for computer scientists, the other an introduction to evolutionary computation for biologists. The latter is more detailed, and the authors introduce the biologist to some of the elementary aspects of evolutionary computation. One interesting, but too short discussion is on the "No Free Lunch Theorem", which implies that evolutionary programs are not in any sense "universal", in that the choice of such a program will depend on the problem at hand, and in fact there may be many such programs for the problem, each with their own performance properties. The theorem is not proved in this book, but references to the proof are given. However, the proof involves a level of mathematics that a biologist would probably not have knowledge of, and so this reference would not be accessible to such a reader. In addition, the theorem has generated a lot of controversy, but the authors do point this out. The authors also discuss effectively the difference between the analytical and heuristic approaches to sequence alignment, setting the stage for later chapters in the book. The problem of local search algorithms getting "trapped" in local minima is also given a very intuitive and understandable treatment by the authors.

The book also includes a discussion on the "DNA sequence reconstruction problem". Algorithms for dealing with this problem are recommended and the the problem is presented as one in integer programming. The authors present a hybrid evolutionary algorithm for dealing with this problem. They characterize this algorithm as being hybrid since it does make use of "crossover" operators and a heuristic "greedy-improvement" method. The discussion of this algorithm is only brief, but references are given. However the main reference is not yet available as it is very recent and in press, and, although the authors do include a fairly lengthy discussion of computational experiments, without a detailed description of the algorithm or source code, their results cannot be checked or validated.

The contrast between optimization theory and evolutionary algorithms is a common theme in the book, with emphasis on the use of evolutionary algorithms to design scoring schemes for sequence alignment where optimization issues can be ignored. The difference between the optimal alignment obtained by various mathematical techniques and the correct (biological) alignment is carefully pointed out. Thus one must be able to tell whether an objective function is relevant from a biological standpoint. In chapter 5 of the book for example, the author introduces an alignment algorithm based on a combination of simulated annealing (SA), and genetic algorithms (GA), called appropriately SAGA. This chapter is the most helpful one in the book, for the author gives pseudocode for this algorithm, with Web links given for obtaining the source code. This allows the interested reader to study the efficacy of the SAGA algorithm in doing muliple sequence alignment.

The use of simulated evolution to find optimal neural networks for identifying coding regions is discussed in chapter 9 of the book. The use of genetic algorithms to assign the weights in a neural network is well-known. The authors point out a further advantage in their use, namely that evolutionary neural networks can adapt to unexpected inputs on their own, and thus do not require any intervention on the part of the user. References are given that elaborate on the power of this approach. Readers who have worked with neural networks will understand fully the need for improvements over back-propagation and the need for automatic topology selection. The authors do not show however that the function-approximation ability of neural networks, so important from both a mathematical and applications standpoint, is improved by their approach.