Molecular programming: evolving genetic programs in a test tube

ABSTRACT

We present a molecular computing algorithm for evolving DNA-encoded genetic programs in a test tube. The use of synthetic DNA molecules combined with biochemical techniques for variation and selection allows for various possibilities for building novel evolvable hardware. Also, the possibility of maintaining a huge number of individuals and their massively parallel manipulation allows us to make robust decisions by the "molecular" genetic programs evolved within a single population. We evaluate the potentials of this "molecular programming" approach by solving a medical diagnosis problem on a simulated DNA computer. Here the individual genetic program represents a decision list of variable length and the whole population takes part in making probabilistic decisions. Tested on a real-life leukemia diagnosis data, the evolved molecular genetic programs showed a comparable performance to decision trees. The molecular evolutionary algorithm can be adapted to solve problems in bio-technology and nano-technology where the physico-chemical evolution of target molecules is of pressing importance.

REFERENCES

• 1: T. Baeck, J. N. Kok, G. Rozenberg, Evolutionary computation as a paradigm for DNA-based computing, Evolution as Computation, L. F. Landweber and E. Winfree (Eds.), Springer-Verlag, pages 15--40, 2002.
• 2: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 3: M. H. Cheok, W. Yang, C.-H. Pui, J. R. Downing, C. Cheng, C. W. Naeve, M. V. Relling, and W. E. Evans, Treatment-specific changes in gene expression discriminate in vivo drug response in human leukemia cells, Nature Genetics, 34:85--90, 2003.
• 4: D. Kalyanmoy et al. (Eds.), Genetic and Evolutionary Computation - GECCO 2004: Genetic and Evolutionary Computation Conference, LNCS 3103, 2004.
• 5: M. Kloster and C. Tang, Simulation and analysis of in vitro DNA evolution, Phys. Rev. Lett., 92(3), 2004.
• 6: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 7: W. B. Langdon, Data Structures and Genetic Programming, Kluwer, 1998.
• 8: J.-Y. Lee, S.-Y. Shin, T.-H. Park, and B.-T. Zhang, Solving traveling salesman problems using DNA molecules encoding numerical values, BioSystems, 78:39--47, 2004.
• 9: Hee-Woong Lim , Ji-Eun Yun , Hae-Man Jang , Young-Gyu Chai , Suk-In Yoo , Byoung-Tak Zhang, Version Space Learning with DNA Molecules, Revised Papers from the 8th International Workshop on DNA Based Computers: DNA Computing, p.143-155, June 10-13, 2002
• 10: Sean Luke , Liviu Panait, Fighting Bloat with Nonparametric Parsimony Pressure, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.411-421, September 07-11, 2002
• 11: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 12: Peter Nordin , Wolfgang Banzhaf , Frank D. Francone, Efficient evolution of machine code for CISC architectures using instruction blocks and homologous crossover, Advances in genetic programming: volume 3, MIT Press, Cambridge, MA, 1999
• 13: U.-M. O'Reilly, P. Testa, S. Greenwold, and M. Hemberg, Agency-GP: Agent-based genetic programming, GECCO-2001 Late Breaking Papers, 2001.
• 14: S.-Y. Shin, I.-H. Lee, D. Kim, and B.-T. Zhang, Multi-objective evolutionary optimization of DNA sequences for reliable DNA computing, IEEE Transactions on Evolutionary Computation, 9(2):143--158, 2005.
• 15: T. Soule and J. Foster, Effects of code growth and parsimony pressure on populations in genetic programming, Evolutionary Computation, 6(4):293--309, 1998.
• 16: L. Spector, Automatic Quantum Computer Programming: A Genetic Programming Approach, Boston, MA: Kluwer Academic Publishers, 2004.
• 17: D. S. Wilson and J. W. Szostak, In vitro selection of functional nucleic acids, Ann. Rev. Biochem., 68:611--647, 1999.
• 18: M. C. Wright and G. F. Joyce, Continuous in vitro evolution of catalytic function, Science, 276:614--617, 1997.
• 19: R. Yokobayashi, R. Weiss, and F. H. Arnold, Directed evolution of a genetic circuit, Proc. Natl. Acad. Sci. USA, 99(26):16587--16591, 2002.
• 20: Byoung-Tak Zhang , Je-Gun Joung, Building Optimal Committees of Genetic Programs, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.231-240, September 18-20, 2000
• 21: Byoung-Tak Zhang, A unified Bayesian framework for evolutionary learning and optimization, Advances in evolutionary computing: theory and applications, Springer-Verlag New York, Inc., New York, NY, 2003
• 22: B.-T. Zhang and H.-Y. Jang, A Bayesian algorithm for in vitro molecular evolution of pattern classifiers, DNA Computing 10, LNCS 3384:458--467, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Design

Keywords:
DNA computing, genetic programs, in vitro evolution, molecular evolutionary computation (MEC), molecular programming (MP)