Biologically-implemented genetic algorithm for protein engineering

ABSTRACT

Protein engineering, developing novel proteins with a desired activity, has become increasingly important in many fields. This paper presents two studies in protein engineering: (i) a biological implementation of a genetic algorithm, with an observed in vitro evolution, and (ii) its preliminary computer simulation using a prototypical probabilistic model based on a random walk. The steady evolution of the fitness distribution of the mutant proteins that appeared in the biological experiments has provided some convincing evidence about the search behavior and the fitness landscape. The computer simulation and the simple probabilistic model have indicated their future potential for providing a practical alternative to the time-consuming manual operations in the biological experiments. Successful experimental results in the two studies have raised expectations of their further development and mutually beneficial interactions.

REFERENCES

• 1: Leonard M. Adleman, Molecular computation of solutions to combinatorial problems, Science, v.266 n.11, p.1021-1024, Nov. 1994
• 2: L. Alberghina, editor. Protein Engineering in Industrial Biotechnology. harwood academic publishers, Jan. 2000.
• 3: T. Back, U. Hammel, and H.-P. Schwefel. Evolutionary computation: Comments on the history and current state. IEEE Transactions on Evolutionary Computation, 1(1):3--17, Apr. 1997.
• 4: T. Back, J.N. Kok, and G. Rozenberg. Evolutionary computation as a paradigm for DNA-based computing. In DIMACS Workshop on Evolution as Computation, pages 67--88, Jan. 1999.
• 5: J. Blazewicz, B. Dziurdza, W.T. Markiewicz, and C. Oguz. The parallel genetic algorithm for designing DNA randomizations in a combinatorial protein experiment. In Parallel Processing and Applied Mathematics, volume 3911 of LNCS, pages 1097--1105. Springer, Sept. 2005.
• 6: C. Branden and J. Tooze. Introduction to Protein Structure. Garland Publishing, 2nd edition, Jan. 1999.
• 7: A. Crameri, E.A. Whitehorn, E. Tate, and W.P.C. Stemmer. Improved green fluorescent protein by molecular evolution using DNA shuffling. Nature Biotechnology, 14:315--319, 1996.
• 8: Sergio Raul Duarte Torres , David Camilo Becerra Romero , Luis Fernando Nino Vasquez , Yoan Jose Pinzon Ardila, A novel ab-initio genetic-based approach for protein folding prediction, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277039]
• 9: M. Ihsan Ecemis, J. Wikel, C. Bingham, and E. Bonabeau. A drug candidate design environment using evolutionary computation. IEEE Transactions on Evolutionary Computation, 12(5):591--603, Oct. 2008.
• 10: K.D. Jong. Parameter Setting in Evolutionary Algorithms, volume 54 of Studies in Computational Intelligence, chapter Parameter Setting in EAs: a 30 Year Perspective, pages 1--18. Springer, 2007.
• 11: H. Joo, Z. Lin, and F.H. Arnold. Laboratory evolution of peroxide-mediated cytochrome P450 hydroxylation. Nature, 399(6737):670--673, June 1999.
• 12: S.A. Kauffman and W.G. Macready. Search strategies for applied molecular evolution. Journal of Theoretical Biology, 173:427--440, Apr. 1995.
• 13: A.D. Keefe and J.W. Szostak. Functional proteins from a random-sequence library. Nature, 410(6829):715--718, Apr. 2001.
• 14: H. Kita, I. Ono, and S. Kobayashi. Multi-parental extension of the unimodal normal distribution crossover for real-coded genetic algorithms. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC'99), pages 1581--1587, July 1999.
• 15: Eric-Wubbo Lameijer , Thomas Bäck , Joost N. Kok , Ad P. Ijzerman, Evolutionary Algorithms in Drug Design, Natural Computing: an international journal, v.4 n.3, p.177-243, September 2005 [doi>10.1007/s11047-004-5237-8]
• 16: L.G. Otten and W.J. Quax. Directed evolution: selecting today's biocatalysts. Biomolecular Engineering, 22(1-3):1--9, June 2005.
• 17: W.M. Patrick, A.E. Firth, and J.M. Blackburn. User-friendly algorithms for estimating completeness and diversity in randomized protein-encoding libraries. Protein Engineering, 16(6):451--457, 2003.
• 18: G.A. Petsko and D. Ringe. Protein Structure and Function, chapter From Sequence to Function, pages 129--165. New Science Press Ltd, 2004.
• 19: John A. Rose , Mitsunori Takano , Akira Suyama, A PNA-mediated Whiplash PCR-based Program for In Vitro Protein Evolution, Revised Papers from the 8th International Workshop on DNA Based Computers: DNA Computing, p.47-60, June 10-13, 2002
• 20: K. Sakamoto, M. Yamamura, and H. Someya. Toward "wet" implementation of genetic algorithm for protein engineering. In C. Ferretti, G. Mauri, and C. Zandron, editors, DNA Computing (Proceedings of 10th International Workshop on DNA Computing), volume 3384 of LNCS, pages 308--318. Springer, 2005.
• 21: H. Someya, M. Yamamura, and K. Sakamoto. Theoretical basis for stochastic optimization starting from a single point in the search space formed by real DNA molecules (in Japanese with English abstract). Transactions of the Japanese Society for Artificial Intelligence, 22(4):405--415, July 2007.
• 22: B. Steipe. Combinatorial Chemistry in Biology, chapter Evolutionary Approaches to Protein Engineering, pages 55--86. Current Topics in Microbiology and Immunology. Springer, Aug. 1999.
• 23: W.P.C. Stemmer. Rapid evolution of a protein in vitro by DNA shuffling. Nature, 370(6488):389--391, Aug. 1994.
• 24: Hideaki Suzuki , Yoh Iwasa, Crossover accelerates evolution in gas with a babel-like fitness landscape: Mathematical analyses, Evolutionary Computation, v.7 n.3, p.275-310, Fall 1999 [doi>10.1162/evco.1999.7.3.275]
• 25: Kenichi Wakabayashi , Masayuki Yamamura, A Design for Cellular Evolutionary Computation by using Bacteria, Natural Computing: an international journal, v.4 n.3, p.275-292, September 2005 [doi>10.1007/s11047-004-5236-9]
• 26: L. Wang, J. Xie, and P.G. Schultz. Expanding the genetic code. Annual Review of Biophysics and Biomolecular Structure, 35:225--249, 2006.
• 27: D.H. Wood, J. Chen, E. Antipov, B. Lemieux, and W. Cedeno. In vitro selection for a OneMax DNA evolutionary computation. In E. Winfree and D.K. Gifford, editors, DNA Based Computers V (Proceedings of 5th International Meeting on DNA Based Computers), volume 54, pages 23--37, 2000.
• 28: H. Yoshizawa and S. Hashimoto. Landscape analyses of search-space in travelling salesman problems (in Japanese with English abstract). Transactions of the Japanese Society for Artificial Intelligence, 16(3):309--315, 2001.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Experimentation

Keywords:
biological implementation, combinatorial optimization, dna computing, genetic algorithm, modeling, molecular evolution, protein engineering, simulation