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

3 Sitaatiot (Scopus)

181 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 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

SFX-saatavuus

Koko teksti

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{\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",

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

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

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

SFX-saatavuus

Sormenjälki

Siteeraa tätä