A DNA-based in vitroGenetic Program.
In PNA-mediated Whiplash PCR (PWPCR), autonomous molecular computation is implemented by the recursive polymerase extension of a mixture of DNA hairpins. Like other methods based on exhaustive search, however, application to problem instances of realistic size is prevented by the exponential scaling of thesolution space. The tendency of evolving populations to minimize the sampling of large, low fitness basins suggests that a DNA-based evolutionary approach might be an effective alternative to exhaustive search. In this work, PWPCR is modified to support the evolution of a population of finite state machines. A practical, in vitroalgorithm for applying this architecture to evolve approximate solutions to instances of the NP-complete problem, Hamiltonian Pathis described in detail.
Department of Computer Science, The Universityof Tokyo, Japan.
J A
JA
Rose
M
M
Hagiya
R J
RJ
Deaton
A
A
Suyama
DNA computing; Hamiltonian Path; genetic program; in vitro