DNA origami words, graphical structures and their rewriting systems

• Published in: Natural computing 2021-06, Vol.20 (2), p.217-231
• Main Authors: Garrett, James, Jonoska, Nataša, Kim, Hwee, Saito, Masahico
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial Intelligence; Complex Systems; Computer Science; Equivalence; Evolutionary Biology; Generators; Gluing; Graphical representations; Modules; Polynomials; Processor Architectures; Scaffolds; Staples; Theory of Computation
• ISSN: 1567-7818; 1572-9796
• DOI: 10.1007/s11047-020-09825-z

We classify rectangular DNA origami structures according to their scaffold and staples organization by associating a graphical representation to each scaffold folding. Inspired by well studied Temperley–Lieb algebra, we identify basic modules that form the structures. The graphical description is obtained by ‘gluing’ basic modules one on top of the other. To each module we associate a symbol such that gluing of modules corresponds to concatenating the associated symbols. Every word corresponds to a graphical representation of a DNA origami structure. A set of rewriting rules defines equivalent words that correspond to the same graphical structure. We propose two different types of basic module structures and corresponding rewriting rules. For each type, we provide the number of all possible structures through the number of equivalence classes of words. We also give a polynomial time algorithm that computes the shortest word for each equivalence class.