Unknotted strand routings of triangulated meshes

Loading...
Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa

Date

2017

Major/Subject

Mcode

Degree programme

Language

en

Pages

46-63

Series

DNA Computing and Molecular Programming, Lecture Notes in Computer Science, Volume 10467

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.

Description

Keywords

DNA nanotechnology, Graphs, Knots, DNA origami, Knot theory, Graph theory, Chinese postman problem

Other note

Citation

Mohammed, A & Hajij, M 2017, Unknotted strand routings of triangulated meshes . in R Brijder & L Qian (eds), DNA Computing and Molecular Programming : 23rd International Conference, DNA 23, Austin, TX, USA, September 24–28, 2017, Proceedings . Lecture Notes in Computer Science, vol. 10467, Springer, pp. 46-63, International Conference on DNA Computing and Molecular Programming, Austin, Texas, United States, 24/09/2017 . https://doi.org/10.1007/978-3-319-66799-7_4