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

University of South Florida

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

4 Sitaatiot (Scopus)

258 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
Kustantaja	Springer
Sivut	46-63
ISBN (elektroninen)	978-3-319-66799-7
ISBN (painettu)	978-3-319-66798-0
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-319-66799-7_4
Tila	Julkaistu - 2017
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisussa
Tapahtuma	International Conference on DNA Computing and Molecular Programming - Austin, Yhdysvallat Kesto: 24 syysk. 2017 → 29 syysk. 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/Alue	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

4 Viittaukset
1 Doctoral Thesis

Algorithmic Design of Biomolecular Nanostructures
Julkaisun otsikon käännös: Algorithmic Design of Biomolecular NanostructuresMohammed, A., 2018, Aalto University. 168 Sivumäärä
Tutkimustuotos: Doctoral Thesis › Collection of Articles

Open access

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). Springer. 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{\textquoteright}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",

address = "Germany",

note = "International Conference on DNA Computing and Molecular Programming , DNA ; Conference date: 24-09-2017 Through 29-09-2017",

url = "https://dna23ut.org/",

}

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, Springer, Sivut 46-63, International Conference on DNA Computing and Molecular Programming , Austin, Texas, 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. Springer, 2017. s. 46-63 ( Lecture Notes in Computer Science; Vuosikerta 10467).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

TY - GEN

T1 - Unknotted strand routings of triangulated meshes

AU - Mohammed, Abdulmelik

AU - Hajij, Mustafa

N1 - Conference code: 23

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 article in proceedings

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

PB - Springer

T2 - International Conference on DNA Computing and Molecular Programming

Y2 - 24 September 2017 through 29 September 2017

ER -

Unknotted strand routings of triangulated meshes

Abstrakti

Julkaisusarja

Conference

Pääsy asiakirjaan

Sormenjälki

Tutkimustuotos

Algorithmic Design of Biomolecular Nanostructures

Siteeraa tätä