On existence of reporter strands in DNA-based graph structures

Nataša Jonoska; Nadrian C. Seeman; Gang Wu

doi:10.1016/j.tcs.2008.12.004

On existence of reporter strands in DNA-based graph structures

Nataša Jonoska, Nadrian C. Seeman, Gang Wu

Chemistry

Research output: Contribution to journal › Article › peer-review

Abstract

Through self-assembly of branched junction molecules many different DNA structures (graphs) can be assembled. We show that every multigraph can be assembled by DNA such that there is a single strand that traces each edge in the graph at least once. This strand corresponds to a boundary component of a two-dimensional orientable surface that has the given graph as a deformation retract. This boundary component traverses every edge at least once, and it defines a circular path in the graph that "preserves the graph structure" and traverses each edge.

Original language	English (US)
Pages (from-to)	1448-1460
Number of pages	13
Journal	Theoretical Computer Science
Volume	410
Issue number	15
DOIs	https://doi.org/10.1016/j.tcs.2008.12.004
State	Published - Apr 1 2009

Keywords

Boundary components
DNA graphs
Graph structures by DNA
Reporter strands
Thickened graphs

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2008.12.004

Cite this

@article{91f2000c80c54aa4bc6bc3a7c221c6fe,

title = "On existence of reporter strands in DNA-based graph structures",

abstract = "Through self-assembly of branched junction molecules many different DNA structures (graphs) can be assembled. We show that every multigraph can be assembled by DNA such that there is a single strand that traces each edge in the graph at least once. This strand corresponds to a boundary component of a two-dimensional orientable surface that has the given graph as a deformation retract. This boundary component traverses every edge at least once, and it defines a circular path in the graph that {"}preserves the graph structure{"} and traverses each edge.",

keywords = "Boundary components, DNA graphs, Graph structures by DNA, Reporter strands, Thickened graphs",

author = "Nata{\v s}a Jonoska and Seeman, {Nadrian C.} and Gang Wu",

note = "Funding Information: Jonoska was supported in part by NSF Grants CCF #0523928 and #0726396. Seeman was supported in part by grants GM-29554 from NIGMS, grants DMI-0210844, EIA-0086015, CCF-0726396, CCF-0523290 and CTS-0548774, CTS-0608889 from the NSF, 48681-EL from ARO, DE-FG02-06ER64281 from DOE (Subcontract from the Research Foundation of SUNY), and a grant from the W.M. Keck Foundation. Gang Wu was a Ph.D. student in New York University when this research was conducted.",

year = "2009",

month = apr,

day = "1",

doi = "10.1016/j.tcs.2008.12.004",

language = "English (US)",

volume = "410",

pages = "1448--1460",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "15",

}

TY - JOUR

T1 - On existence of reporter strands in DNA-based graph structures

AU - Jonoska, Nataša

AU - Seeman, Nadrian C.

AU - Wu, Gang

N1 - Funding Information: Jonoska was supported in part by NSF Grants CCF #0523928 and #0726396. Seeman was supported in part by grants GM-29554 from NIGMS, grants DMI-0210844, EIA-0086015, CCF-0726396, CCF-0523290 and CTS-0548774, CTS-0608889 from the NSF, 48681-EL from ARO, DE-FG02-06ER64281 from DOE (Subcontract from the Research Foundation of SUNY), and a grant from the W.M. Keck Foundation. Gang Wu was a Ph.D. student in New York University when this research was conducted.

PY - 2009/4/1

Y1 - 2009/4/1

N2 - Through self-assembly of branched junction molecules many different DNA structures (graphs) can be assembled. We show that every multigraph can be assembled by DNA such that there is a single strand that traces each edge in the graph at least once. This strand corresponds to a boundary component of a two-dimensional orientable surface that has the given graph as a deformation retract. This boundary component traverses every edge at least once, and it defines a circular path in the graph that "preserves the graph structure" and traverses each edge.

AB - Through self-assembly of branched junction molecules many different DNA structures (graphs) can be assembled. We show that every multigraph can be assembled by DNA such that there is a single strand that traces each edge in the graph at least once. This strand corresponds to a boundary component of a two-dimensional orientable surface that has the given graph as a deformation retract. This boundary component traverses every edge at least once, and it defines a circular path in the graph that "preserves the graph structure" and traverses each edge.

KW - Boundary components

KW - DNA graphs

KW - Graph structures by DNA

KW - Reporter strands

KW - Thickened graphs

UR - http://www.scopus.com/inward/record.url?scp=60649100880&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=60649100880&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2008.12.004

DO - 10.1016/j.tcs.2008.12.004

M3 - Article

AN - SCOPUS:60649100880

SN - 0304-3975

VL - 410

SP - 1448

EP - 1460

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 15

ER -

On existence of reporter strands in DNA-based graph structures

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this