title: DNA strand displacement system running logic programs.
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.
authors.affiliation: 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.
authors.forename: Alfonso
authors.initials: A
authors.lastname: Rodríguez-Patón
authors.affiliation: 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.
authors.forename: Iñaki
authors.initials: I
authors.lastname: Sainz de Murieta
authors.affiliation: 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.
authors.forename: Petr
authors.initials: P
authors.lastname: Sosík
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D039301:Computers, Molecular; D008128:Logic; D008962:Models, Theoretical; D012985:Software Design
keywords: DNA computing; DNA strand displacement; Horn clause; Logic program