DNA strand displacement system running logic programs

Alfonso Rodríguez-Patón; Iñaki Sainz de Murieta; Petr Sosík

doi:10.1016/j.biosystems.2013.10.006

DNA strand displacement system running logic programs

Biosystems. 2014 Jan:115:5-12. doi: 10.1016/j.biosystems.2013.10.006. Epub 2013 Nov 5.

Authors

Alfonso Rodríguez-Patón¹, Iñaki Sainz de Murieta², Petr Sosík³

Affiliations

¹ Departamento de Inteligencia Artificial, Facultad de Informática, Universidad Politécnica de Madrid, Campus de Montegancedo s/n, Boadilla del Monte, 28660 Madrid, Spain. Electronic address: arpaton@fi.upm.es.
² Departamento de Inteligencia Artificial, Facultad de Informática, Universidad Politécnica de Madrid, Campus de Montegancedo s/n, Boadilla del Monte, 28660 Madrid, Spain; Centre for Synthetic Biology and Innovation and Department of Bioengineering, Imperial College London, London SW7 2AZ, UK. Electronic address: i.sainzdemurieta@imperial.ac.uk.
³ Research Institute of the IT4Innovations Centre of Excellence, Faculty of Philosophy and Science, Silesian University in Opava, 74601 Opava, Czech Republic; Departamento de Inteligencia Artificial, Facultad de Informática, Universidad Politécnica de Madrid, Campus de Montegancedo s/n, Boadilla del Monte, 28660 Madrid, Spain. Electronic address: petr.sosik@fpf.slu.cz.

PMID: 24211259
DOI: 10.1016/j.biosystems.2013.10.006

Abstract

The paper presents a DNA-based computing model which is enzyme-free and autonomous, not requiring a human intervention during the computation. The model is able to perform iterated resolution steps with logical formulae in conjunctive normal form. The implementation is based on the technique of DNA strand displacement, with each clause encoded in a separate DNA molecule. Propositions are encoded assigning a strand to each proposition p, and its complementary strand to the proposition ¬p; clauses are encoded comprising different propositions in the same strand. The model allows to run logic programs composed of Horn clauses by cascading resolution steps. The potential of the model is demonstrated also by its theoretical capability of solving SAT. The resulting SAT algorithm has a linear time complexity in the number of resolution steps, whereas its spatial complexity is exponential in the number of variables of the formula.

Keywords: DNA computing; DNA strand displacement; Horn clause; Logic program.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms*
Computer Simulation
Computers, Molecular*
Logic*
Models, Theoretical*
Software Design*