Naturally selecting solutions: the use of genetic algorithms in bioinformatics

Abstract

For decades, computer scientists have looked to nature for biologically inspired solutions to computational problems; ranging from robotic control to scheduling optimization. Paradoxically, as we move deeper into the post-genomics era, the reverse is occurring, as biologists and bioinformaticians look to computational techniques, to solve a variety of biological problems. One of the most common biologically inspired techniques are genetic algorithms (GAs), which take the Darwinian concept of natural selection as the driving force behind systems for solving real world problems, including those in the bioinformatics domain. Herein, we provide an overview of genetic algorithms and survey some of the most recent applications of this approach to bioinformatics based problems.

Keywords: genetic algorithm; multiple sequence alignment; optimization; protein structure prediction.

Figure 1. An analysis of 150 bioinformatics papers referencing GAs. (A) A plot of the distribution of the sampled papers (y-axis) plotted against the year of publication (x-axis), and (B) A breakdown of the subject matter addressed by the papers.

Figure 2. Flowchart for the execution of a genetic algorithm

Figure 3. (A) A possible genotype representation for the TSP, describing a permutation of a list of cities. (B) A phenotype (the itinerary) generated from the genotype.

Figure 4. One-point crossover on two binary parent genotypes, creating two new offspring

Figure 5. Two-point crossover. The parent genotypes are each divided into three segments, and the offspring are produced by combining alternate segments of the parents.

Figure 6. A possible crossover implementation for the TSP problem. (A) Two parents are chosen using a selection algorithm. A crossover point is randomly selected in the first parent. (B and C) The genes from one side of the crossover point are selected and are combined with the alternate genes in the order which they appear in the second parent to form a new child genotype.

Figure 7. A possible mutation operator for the TSP. An offset in the genotype is selected. The genes either side of the offset are then switched to produce the new valid genotype.

Figure 8. (A) An example distribution of 20 cities and (B) a path linking the cities found using a genetic algorithm.

Figure 9. A typical learning curve for a genetic algorithm

Figure 10. An example 4-sequence alignment. Individual sequences are represented on separate lines. Columns represent aligned amino acids. Adapted from reference .

Figure 11. An example distribution of a set of solutions in a Pareto Optimality. Each box represents the fitness of a solution in terms of ID score plotted against its fitness in terms of the SOP score. The gray line represents the Pareto front. In this example the Pareto front shows optimal trade-offs between the ID and SOP scores.

Figure 12. Example dissection of two parents for a vertical one-point crossover operation

Figure 13. Example dissection of two parents for a horizontal one-point crossover operation

Figure 14. Graphical depiction of the flow of solution exchanges in 4-island model comprising three slave populations and a centrally located master population

Figure 15. (A) A sequence alignment for four sequence, and two equivalent encodings for the alignment. (B) The CGA-MSA genotype representing an alignment solution.

Figure 16. The CGA-MSA mutation operator. The binary digits up to the mutation point are grouped by sequence and considered for mutation individually.

Figure 17. A protein with the format HPHPPHHPHPPHPHHPPHPH fitted to (A) a 2D triangular lattice, and (B) a 3D cubic lattice. The hydrophobic amino acids are represented as black dots and the polar amino acids as white circles. Both conformations are optimal under the HP model. Adapted from references and , respectively.