A DNA Implementation of the Max 1s Problem

Abstract

Elements of genetic algorithms, DNA computing, and in vitro evolution are combined into laboratory procedures. The traditional test problem for genetic algorithms, Max 1s problem is addressed. Preliminary laboratory results are shown. 1 Introduction Evolution is a concept of obtaining adaptation through the interplay of selection and diversity. Analogies from evolution have been used in both computing and molecular biology. The paradigm in molecular biology is known as #in vitro evolution." In this paper we identify elements of genetic algorithms and in vitro evolution that we recommend combining to address Max 1s problems. Wechoose Max 1s to test our techniques, which can also be used on some other problems #6#. Wechoose genetic algorithms because they manipulate bitstrings using operations of pointwise mutation and crossover. These operations can be performed by modi#cations of techniques from in vitro evolution. The crucial operation of physically separating DNA strands by t...