Unknotted strand routings of triangulated meshes

Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)

Authors

Date

2017

Department

Department of Computer Science

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

DOI

10.1007/978-3-319-66799-7_4

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

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-201902251958

Collections

[article-cris] Perustieteiden korkeakoulu / SCI