DNA origami words, graphical structures and their rewriting systems
- Resource Type
- Authors
- James Garrett; Hwee Kim; Nataša Jonoska; Masahico Saito
- Source
- Natural Computing. 20:217-231
- Subject
- Structure (mathematical logic)
Computer science
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Computer Science Applications
Set (abstract data type)
Algebra
010201 computation theory & mathematics
Symbol (programming)
0202 electrical engineering, electronic engineering, information engineering
DNA origami
020201 artificial intelligence & image processing
Rewriting
Representation (mathematics)
Equivalence class
Word (computer architecture)
- Language
- ISSN
- 1572-9796
1567-7818
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.