Unknotted strand routings of triangulated meshes

Abdulmelik Mohammed, Mustafa Hajij

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2 Citations (Scopus)
155 Downloads (Pure)

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 languageEnglish
Title of host publicationDNA Computing and Molecular Programming
Subtitle of host publication23rd International Conference, DNA 23, Austin, TX, USA, September 24–28, 2017, Proceedings
EditorsRobert Brijder, Lulu Qian
Pages46-63
ISBN (Electronic)978-3-319-66799-7
DOIs
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventInternational Conference on DNA Computing and Molecular Programming - Austin, United States
Duration: 24 Sep 201729 Sep 2017
Conference number: 23
https://dna23ut.org/

Publication series

Name Lecture Notes in Computer Science
PublisherSpringer
Volume10467
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on DNA Computing and Molecular Programming
Abbreviated titleDNA
CountryUnited States
CityAustin
Period24/09/201729/09/2017
Internet address

Keywords

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

Fingerprint Dive into the research topics of 'Unknotted strand routings of triangulated meshes'. Together they form a unique fingerprint.

  • Cite this

    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 (pp. 46-63). ( Lecture Notes in Computer Science; Vol. 10467). https://doi.org/10.1007/978-3-319-66799-7_4