World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

ASPECTS OF BIOMOLECULAR COMPUTING

    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
    • Leonard Adleman, Science 266, 1021 (1994), DOI: 10.1126/science.7973651. Crossref, ISIGoogle Scholar
    • Leonard Adleman, 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
    • Selim G. Akl, Parallel Numerics, Part 2, Systems and Simulation, eds. R. Trobecet al. (University of Salzburg, Austria and Jožef Stefan Institute, Ljubljana, Slovenia, 2005) pp. 211–236. Google Scholar
    • Selim G. Akl, Parallel Processing Letters 16(1), 19 (2006), DOI: 10.1142/S0129626406002447. LinkGoogle Scholar
    • Selim G. Akl, Brendan Cordy and W. Yao, International Journal of Parallel, Emergent and Distributed Systems 20(2), 147 (2005), DOI: 10.1080/17445760500033432. Crossref, ISIGoogle Scholar
    • Donald Beaver, Journal of Computational Biology 2, 1 (1995). CrossrefGoogle Scholar
    • F. Bernardini and M. Gheorghe, Journal of Universal Computer Science 10(5), 509 (2004). ISIGoogle Scholar
    • Mireille Bétermier, Research in Microbiology 155, 399 (2004), DOI: 10.1016/j.resmic.2004.01.017. Crossref, ISIGoogle 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
    • Ravinderjit S. Braichet al., Science 296, 499 (2002), DOI: 10.1126/science.1069528. Crossref, ISIGoogle 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
    • Weng-Long Chang, Minyi Guo and Jesse Wu, Parallel Processing Letters 15(4), 469 (2005), DOI: 10.1142/S0129626405002386. Link, ISIGoogle 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. Mauriet al. (Springer-Verlag, 2005) pp. 1–18. Google Scholar
    • Mark Daley and Ian McQuillan, Theoretical Computer Science 330(2), 237 (2005), DOI: 10.1016/j.tcs.2004.06.028. Crossref, ISIGoogle Scholar
    • A.   Ehrenfeucht et al. , Computation in Living Cells: Gene Assembly in Ciliates ( Springer , 2003 ) . Google Scholar
    • A. Ehrenfeuchtet al., Theoretical Computer Science 292, (2003). Google Scholar
    • A. E.   Eiben and J. E.   Smith , Introduction to Evolutionary Computing ( Springer , 2003 ) . CrossrefGoogle Scholar
    • Dirk Faulhammeret al., 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, ISIGoogle 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
    • Frank Guarnieri, Makiko Fliss and Carter Bancroft, Science 273(12), 220 (1996), DOI: 10.1126/science.273.5272.220. Crossref, ISIGoogle 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 Scholar
    • M. 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 Scholar
    • Masami 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
    • Tom Head, Bulletin of Mathematical Biology 49, 737 (1987). Crossref, ISIGoogle 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
    • Lila Kariet al., Acta Informatica 35(5), 401 (1998), DOI: 10.1007/s002360050125. Crossref, ISIGoogle Scholar
    • Shankara N. Krishna and Raghavan Rama, Journal of Automata, Languages and Combinatorics 6(3), 345 (2001). Google Scholar
    • Stuart A. Kurtzet al., Complexity Theory Retrospective II (Springer-Verlag, 1997) pp. 179–196. CrossrefGoogle Scholar
    • Benjamin   Lewin , Genes VII ( Oxford University Press , 2000 ) . Google Scholar
    • Richard J. Lipton, Science 268(5210), 542 (1995), DOI: 10.1126/science.7725098. Crossref, ISIGoogle Scholar
    • Qinghua Liuet al., Nature 403, 175 (2000), DOI: 10.1038/35001232. Crossref, ISIGoogle Scholar
    • Qi Ouyanget al., Science 278, 446 (1997), DOI: 10.1126/science.278.5337.446. Crossref, ISIGoogle Scholar
    • M. J. Pérez-Jiménez and A. Riscos-Núñez, Membrane Computing, Lecture Notes in Computer Science 2933 (2004) pp. 250–268. CrossrefGoogle Scholar
    • D. M. Prescott, A. Ehrenfeucht and Grzegorz Rozenberg, European Journal of Protistology 37, (2001). Google Scholar
    • Gheorghe   Păun , Journal of Computer and System Sciences   . Google Scholar
    • Gheorghe Păun, Discrete Applied Mathematics 70, 57 (1996), DOI: 10.1016/0166-218X(96)00101-1. Crossref, ISIGoogle Scholar
    • Gheorghe Păun, Journal of Automata, Languages, Combinatorics 1(1), 27 (1996). Google Scholar
    • Gheorghe Păun, 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
    • John H. Reif, 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
    • Kensaku Sakamotoet al., Science 288(19), 1223 (2000), DOI: 10.1126/science.288.5469.1223. Crossref, ISIGoogle 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
    • Claude Shannon, Bell Syst. Tech. J. 28(59), (1949). Google Scholar
    • Kenneth D. Stuartet al., Trends in Biochemical Sciences 30(2), 97 (2005), DOI: 10.1016/j.tibs.2004.12.006. Crossref, ISIGoogle 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
    • Claudio Zandron, Claudio Ferretti and Giancarlo Mauri, Unconventional Models of Computation, eds. I. Antoniou, C. S. Calude and M. J. Dinneen (Springer, London, 2000) pp. 289–301. Google Scholar