DNA origami words, graphical structures and their rewriting systems

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 ob...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1567-7818
1572-9796
DOI:10.1007/s11047-020-09825-z