ASPECTS OF BIOMOLECULAR COMPUTING
Abstract
This paper is intended as a survey of the state of the art of some branches of Biomolecular Computing. Biomolecular Computing aims to use biological hardware (biomare), rather than chips, to build a computer. We discuss the following three main research directions: DNA computing, membrane systems, and gene assembly in ciliates. DNA computing combines practical results together with theoretical algorithm design. Various search problems have been implemented using DNA strands. Membrane systems are a family of computational models inspired by the membrane structure of living cells. The process of gene assembly in ciliates has been formalized as an abstract computational model. Biomolecular Computing is a field in full development, with the promise of important results from the perspective of both Computer Science (models of computation) and Biology (understanding biological processes).
This research was supported by the Natural Sciences and Engineering Research Council of Canada.
References
- Web page of P systems: http://psystems.disco.unimib.it . Google Scholar
- Science 266, 1021 (1994), DOI: 10.1126/science.7973651. Crossref, ISI, Google Scholar
- Scientific American 34 (1998). Google Scholar
- Selim G. Akl. From infinitely small to infinitely big: The universe as computer. Public lecture, Queen's University, November 2005 . Google Scholar
- , Parallel Numerics, Part 2, Systems and Simulation, eds.
R. Trobec (University of Salzburg, Austria and Jožef Stefan Institute, Ljubljana, Slovenia, 2005) pp. 211–236. Google Scholar - Parallel Processing Letters 16(1), 19 (2006), DOI: 10.1142/S0129626406002447. Link, Google Scholar
- International Journal of Parallel, Emergent and Distributed Systems 20(2), 147 (2005), DOI: 10.1080/17445760500033432. Crossref, ISI, Google Scholar
- Journal of Computational Biology 2, 1 (1995). Crossref, Google Scholar
- Journal of Universal Computer Science 10(5), 509 (2004). ISI, Google Scholar
- Research in Microbiology 155, 399 (2004), DOI: 10.1016/j.resmic.2004.01.017. Crossref, ISI, Google Scholar
- Dan Boneh, Christopher Dunworth, Richard J. Lipton, and Jiří Sgall. Making DNA computers error resistant. Department of Computer Science, Princeton University, Princeton, USA, and Mathematical Institute, AV ČR, Praha, Czech Republic . Google Scholar
- Dan Boneh, Cristopher Dunworth, and Richard J. Lipton. Breaking DES using a molecular computer. Technical Report 489-95, Princeton CS, Princeton, NJ, 1995 . Google Scholar
- Science 296, 499 (2002), DOI: 10.1126/science.1069528. Crossref, ISI, Google Scholar
M. Cavaliere , Evolution-communication P systems, Membrane Computing. International Workshop, WMC-CdeA, eds.Gh. Păun , G. Rozenberg and A. Salomaa (Springer-Verlag, 2003) pp. 134–145. Google Scholar- Parallel Processing Letters 15(4), 469 (2005), DOI: 10.1142/S0129626405002386. Link, ISI, Google Scholar
L. Colson , N. Jonoska and M. Margenstern , λ P systems and typed λ-calculus, Membrane Computing. International Workshop, WMC5,Lecture Notes in Computer Science , eds.G. Mauri (Springer-Verlag, 2005) pp. 1–18. Google Scholar- Theoretical Computer Science 330(2), 237 (2005), DOI: 10.1016/j.tcs.2004.06.028. Crossref, ISI, Google Scholar
-
A. Ehrenfeucht , Computation in Living Cells: Gene Assembly in Ciliates ( Springer , 2003 ) . Google Scholar - Theoretical Computer Science 292, (2003). Google Scholar
-
A. E. Eiben and J. E. Smith , Introduction to Evolutionary Computing ( Springer , 2003 ) . Crossref, Google Scholar - Proceedings of the National Academy of Sciences of the United States of America 97(4), 1385 (2000), DOI: 10.1073/pnas.97.4.1385. Crossref, ISI, Google Scholar
R. Freund and A. Pǎun , Membrane systems with symport/antiport rules: Universality results, Membrane Computing. International Workshop, WMC-CdeA, eds.Gh. Pǎun , G. Rozenberg and A. Salomaa (Springer-Verlag, 2003) pp. 270–287. Google Scholar- Science 273(12), 220 (1996), DOI: 10.1126/science.273.5272.220. Crossref, ISI, Google Scholar
M. A. Gutiérrez-Naranjo , M. J. Pérez-Jiménez and A. Riscos-Núñez , On descriptive complexity in P systems, Preproceedings of the 5-th Workshop on Membrane Computing, (WMC5) (2004) pp. 245–255. Google ScholarM. A. Gutiérrez-Naranjo , M. J. Pérez-Jiménez and J. Romero-Campero , A linear solution for QSAT with membrane creation, Preproceedings of the 6-th Workshop on Membrane Computing, (WMC6) (2005) pp. 395–409. Google ScholarMasami Hagiya , From molecular computing to molecular programming, Proceedings of the 6-th DIMACS Workshop on DNA Based Computers (2000) pp. 87–100. Google Scholar- Tero Harju, Ion Petre, and Grzegorz Rozenberg. Gene assembly in ciliates: Formal framework. TUCS Technical Report 558, Turku Centre for Computer Science, October 2003 . Google Scholar
- Tero Harju, Ion Petre, and Grzegorz Rozenberg. Gene assembly in ciliates: Molecular operations. TUCS Technical Report 557, Turku Centre for Computer Science, October 2003 . Google Scholar
- Bulletin of Mathematical Biology 49, 737 (1987). Crossref, ISI, Google Scholar
- Peter Kaplan, Guillermo Cecchi, and Albert Libchaber. Molecular computation: Adleman's experiment repeated. Technical Report 95-120, NEC Research Institute, Princeton, NJ, 1995 . Google Scholar
- Acta Informatica 35(5), 401 (1998), DOI: 10.1007/s002360050125. Crossref, ISI, Google Scholar
- Journal of Automata, Languages and Combinatorics 6(3), 345 (2001). Google Scholar
Stuart A. Kurtz , Complexity Theory Retrospective II (Springer-Verlag, 1997) pp. 179–196. Crossref, Google Scholar-
Benjamin Lewin , Genes VII ( Oxford University Press , 2000 ) . Google Scholar - Science 268(5210), 542 (1995), DOI: 10.1126/science.7725098. Crossref, ISI, Google Scholar
- Nature 403, 175 (2000), DOI: 10.1038/35001232. Crossref, ISI, Google Scholar
- Science 278, 446 (1997), DOI: 10.1126/science.278.5337.446. Crossref, ISI, Google Scholar
M. J. Pérez-Jiménez and A. Riscos-Núñez , Membrane Computing,Lecture Notes in Computer Science 2933 (2004) pp. 250–268. Crossref, Google Scholar- European Journal of Protistology 37, (2001). Google Scholar
- Journal of Computer and System Sciences . Google Scholar
- Discrete Applied Mathematics 70, 57 (1996), DOI: 10.1016/0166-218X(96)00101-1. Crossref, ISI, Google Scholar
- Journal of Automata, Languages, Combinatorics 1(1), 27 (1996). Google Scholar
- Journal of Automata, Languages, Combinatorics 6(1), 5 (2001). Google Scholar
-
Gheorghe Păun , Grzegorz Rozenberg and Arto Salomaa , DNA Computing - New Computing Paradigms ( Springer , 1998 ) . Google Scholar - Science 296, (2002). Google Scholar
- Grzegorz Rozenberg. DNA processing in ciliates - the wonders of DNA computing in vivo. 1. Leiden Center for Natural Computing, Leiden University, The Netherlands, 2. Departement of Computer Science, university of Colorado, Boulder, USA . Google Scholar
- Science 288(19), 1223 (2000), DOI: 10.1126/science.288.5469.1223. Crossref, ISI, Google Scholar
- Shetu N. Shah and Michael T. Niemier. Pattern matching with DNA computers - draft. College of Computing, Georgia Institue of Technology, Atlanta, Georgia, USA . Google Scholar
- Bell Syst. Tech. J. 28(59), (1949). Google Scholar
- Trends in Biochemical Sciences 30(2), 97 (2005), DOI: 10.1016/j.tibs.2004.12.006. Crossref, ISI, Google Scholar
-
Lionel Tarassenko , A Guide to Neural Computing Applications ( Elsevier , 1998 ) . Google Scholar -
Michael D. Vose , The Simple Genetic Algorithm: Foundations and Theory ( MIT Press , 1999 ) . Google Scholar -
Hiroshi Yoshida and Akira Suyama , Solution to 3-SAT by breadth first search , Proceedings of the 5-th DIMACS Meeting on DNA Based Computers , eds.Erik Winfree and David K. Gifford ( MIT , 1999 ) . Google Scholar - , Unconventional Models of Computation, eds.
I. Antoniou , C. S. Calude and M. J. Dinneen (Springer, London, 2000) pp. 289–301. Google Scholar


