A DNA-based in vitroGenetic Program
Tóm tắt
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.
Tài liệu tham khảo
Rose, J. et al.: Equilibrium analysis of an autonomous molecular computer, Physical Review E 65(2002), Article 021910, pp. 1–13.
Sakamoto, K. et al.: State transitions by molecules, Biosystems 52(1999), 81–91.
Adleman, L.: Molecular Computation of Solutions to Combinatorial Problems, Science 266(1994), 1021–1024.
Bäck, T., Kok, J. and Rozenberg, G.: Cross-Fertilization between Evolutionary Computation and DNA-based Computing, In: Proc. Cong. Evol. Comp., IEEE Press, Washington, DC, 1999, 980–987.
Chen, J. and Wood, D.H.: Computation with Biomolecules, PNAS 97(2000), 1328–1330.
Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd ed., Springer-Verlag, Berlin, 1996.
Deaton, R. et al.: A DNA based Implementation of an Evolutionary Search for Good Encodings for DNA Computation, In: Proc. 1997 IEEE ICEC, IEEE Press, Indianapolis, 1997, pp. 267–271.
Wood, D. et al.: DNA Starts to Learn Poker, in [12], pp. 23–32.
REBase restriction enzyme database, http://rebase.neb.com/.
Sambrook, J., Fritsch, E. and Maniatis, T: Molecular Cloning: A Laboratory Manual, 2nd ed., Cold Spring Harbor Press, 1992.
van Noort, D., Gast, F.-U. and McCaskill, J.: DNA Computing in Microreactors, in [12], pp. 128–137.
Jonaska, N. and Seeman, N. (eds.), Prelim. Proc. of the 7th Int'l Meeting on DNA-based Computers, Univ. of S. Florida, Tampa, 2001.