Abstract
In molecular self-assembly such as DNA origami, a circular strand’s topological routing determines the feasibility of a design to assemble to a target. In this regard, the Chinese-postman DNA scaffold routings of Benson et al. (2015) only ensure the unknottedness of the scaffold strand for triangulated topological spheres. In this paper, we present a cubic-time 53−approximation algorithm to compute unknotted Chinese-postman scaffold routings on triangulated orientable surfaces of higher genus. Our algorithm guarantees every edge is routed at most twice, hence permitting low-packed designs suitable for physiological conditions.
| Original language | English |
|---|---|
| Title of host publication | DNA Computing and Molecular Programming |
| Subtitle of host publication | 23rd International Conference, DNA 23, Austin, TX, USA, September 24–28, 2017, Proceedings |
| Editors | Robert Brijder, Lulu Qian |
| Publisher | Springer |
| Pages | 46-63 |
| ISBN (Electronic) | 978-3-319-66799-7 |
| ISBN (Print) | 978-3-319-66798-0 |
| DOIs | |
| Publication status | Published - 2017 |
| MoE publication type | A4 Conference publication |
| Event | International Conference on DNA Computing and Molecular Programming - Austin, United States Duration: 24 Sept 2017 → 29 Sept 2017 Conference number: 23 https://dna23ut.org/ |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 10467 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | International Conference on DNA Computing and Molecular Programming |
|---|---|
| Abbreviated title | DNA |
| Country/Territory | United States |
| City | Austin |
| Period | 24/09/2017 → 29/09/2017 |
| Internet address |
Keywords
- DNA nanotechnology
- Graphs
- Knots
- DNA origami
- Knot theory
- Graph theory
- Chinese postman problem