Convergent evolution to an aptamer observed in small populations on DNA microarrays.

The development of aptamers on custom synthesized DNA microarrays, which has been demonstrated in recent publications, can facilitate detailed analyses of sequence and fitness relationships. Here we use the technique to observe the paths taken through sequence-fitness space by three different evolutionary regimes: asexual reproduction, recombination and model-based evolution. The different evolutionary runs are made on the same array chip in triplicate, each one starting from a small population initialized independently at random. When evolving to a common target protein, glucose-6-phosphate dehydrogenase (G6PD), these nine distinct evolutionary runs are observed to develop aptamers with high affinity and to converge on the same motif not present in any of the starting populations. Regime specific differences in the evolutions, such as speed of convergence, could also be observed.

Approximating the nondominated front using the Pareto Archived Evolution Strategy.

We introduce a simple evolution scheme for multiobjective optimization problems, called the Pareto Archived Evolution Strategy (PAES). We argue that PAES may represent the simplest possible nontrivial algorithm capable of generating diverse solutions in the Pareto optimal set. The algorithm, in its simplest form, is a (1 + 1) evolution strategy employing local search but using a reference archive of previously found solutions in order to identify the approximate dominance ranking of the current and candidate solution vectors. (1 + 1)-PAES is intended to be a baseline approach against which more involved methods may be compared. It may also serve well in some real-world applications when local search seems superior to or competitive with population-based methods. We introduce (1 + lambda) and (mu + lambda) variants of PAES as extensions to the basic algorithm. Six variants of PAES are compared to variants of the Niched Pareto Genetic Algorithm and the Nondominated Sorting Genetic Algorithm over a diverse suite of six test functions. Results are analyzed and presented using techniques that reduce the attainment surfaces generated from several optimization runs into a set of univariate distributions. This allows standard statistical analysis to be carried out for comparative purposes. Our results provide strong evidence that PAES performs consistently well on a range of multiobjective optimization tasks.