Unknotted strand routings of triangulated meshes

Abdulmelik Mohammed; Mustafa Hajij

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

Unknotted strand routings of triangulated meshes

Abdulmelik Mohammed, Mustafa Hajij

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

2 Sitaatiot (Scopus)

146 Lataukset (Pure)

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	DNA Computing and Molecular Programming
Alaotsikko	23rd International Conference, DNA 23, Austin, TX, USA, September 24–28, 2017, Proceedings
Toimittajat	Robert Brijder, Lulu Qian
Sivut	46-63
ISBN (elektroninen)	978-3-319-66799-7
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-319-66799-7_4
Tila	Julkaistu - 2017
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	International Conference on DNA Computing and Molecular Programming - Austin, Yhdysvallat Kesto: 24 syyskuuta 2017 → 29 syyskuuta 2017 Konferenssinumero: 23 https://dna23ut.org/

Julkaisusarja

Nimi	Lecture Notes in Computer Science
Kustantaja	Springer
Vuosikerta	10467
ISSN (painettu)	0302-9743
ISSN (elektroninen)	1611-3349

Conference

Conference	International Conference on DNA Computing and Molecular Programming
Lyhennettä	DNA
Maa	Yhdysvallat
Kaupunki	Austin
Ajanjakso	24/09/2017 → 29/09/2017
www-osoite	https://dna23ut.org/

Pääsy asiakirjaan

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

SCI_Mohammed_and_Hajij_Unknotted_Strand_Routings_acrisAccepted author manuscript, 1,17 MB

Sormenjälki Sukella tutkimusaiheisiin 'Unknotted strand routings of triangulated meshes'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä

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

@inproceedings{84327aab1a7e45c5a654dc03bbbc1d95,

title = "Unknotted strand routings of triangulated meshes",

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.",

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

author = "Abdulmelik Mohammed and Mustafa Hajij",

year = "2017",

doi = "10.1007/978-3-319-66799-7_4",

language = "English",

isbn = "978-3-319-66798-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "46--63",

editor = "Robert Brijder and Lulu Qian",

booktitle = "DNA Computing and Molecular Programming",

}

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

Unknotted strand routings of triangulated meshes. / Mohammed, Abdulmelik; Hajij, Mustafa.

DNA Computing and Molecular Programming: 23rd International Conference, DNA 23, Austin, TX, USA, September 24–28, 2017, Proceedings. toim. / Robert Brijder; Lulu Qian. 2017. s. 46-63 ( Lecture Notes in Computer Science; Vuosikerta 10467).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

TY - GEN

T1 - Unknotted strand routings of triangulated meshes

AU - Mohammed, Abdulmelik

AU - Hajij, Mustafa

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - DNA nanotechnology

KW - Graphs

KW - Knots

KW - DNA origami

KW - Knot theory

KW - Graph theory

KW - Chinese postman problem

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

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

M3 - Conference contribution

SN - 978-3-319-66798-0

T3 - Lecture Notes in Computer Science

SP - 46

EP - 63

BT - DNA Computing and Molecular Programming

A2 - Brijder, Robert

A2 - Qian, Lulu

ER -