As the state of the art in DNA nanotechnology continues to develop, highly sophisticated computational molecular devices are being designed and subsequently implemented in DNA. These devices employ a broad range of implementation strategies to perform computation, including DNA strand displacement, localisation to substrates, and the use of enzymes with polymerase, nickase and exonuclease functionality. However, existing computational design tools are unable to account for these different strategies in a unified manner. 

This paper presents a programming language that allows a broad range of computational DNA systems to be expressed and analyzed. We define a semantic framework that allows DNA molecular motifs to be expressed as sub-graphs, and automatically identifies matching motifs in the full system, in order to apply a specified transformation expressed as a rule. The framework also supports the definition of predicates, which provide additional constraints in order for rules to apply. The framework is sufficiently expressive to encode the semantics of DNA strand displacement systems with complex topologies, together with computation performed by a broad range of enzymes. 

Our language, called Rules DSD, is a logic programming language that extends Prolog with a novel equational theory to express DNA molecular motifs in a system. Molecular motifs are interpreted as sub-graphs occurring in a system of strand graphs. Transformations of such motifs are safely handled in the Single Pushout approach, drawing from the theory of graph grammars. Several encodings of molecular systems are presented, including ribocomputing logical circuits.