Edge-outer graph embedding and the complexity of the DNA reporter strand problem

DOI10.1016/J.TCS.2019.03.019MaRDI QIDQ2315018zbMATH OpenOpenAlexWikidataFDO

Authors Joanna A. Ellis-Monaghan, M. N. Ellingham

Publication date 31 July 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.09048

zbMATH Keywords

reporter strandDNA-origamiedge-outer embeddingone-face embeddingorientable graph embedding

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: In 2009, Jonoska, Seeman and Wu showed that every graph admits a route for a DNA reporter strand, that is, a closed walk covering every edge either once or twice, in opposite directions if twice, and passing through each vertex in a particular way. This corresponds to showing that every graph has an emph{edge-outer embedding}, that is, an orientable embedding with some face that is incident with every edge. In the motivating application, the objective is such a closed walk of minimum length. Here we give a short algorithmic proof of the original existence result, and also prove that finding a shortest length solution is NP-hard, even for $3$-connected cubic ($3$-regular) planar graphs. Independent of the motivating application, this problem opens a new direction in the study of graph embeddings, and we suggest new problems emerging from it.

Recommendations

• On existence of reporter strands in DNA-based graph structures
• Efficient DNA sticker algorithms for NP-complete graph problems
• A strand graph semantics for DNA-based computation
• scientific article; zbMATH DE number 5526120
• A DNA-based graph encoding scheme with its applications to graph isomorphism problems
• scientific article; zbMATH DE number 1953078
• Simulating the DNA overlap graph in succinct space
• Graph algorithms for DNA sequencing -- origins, current models and the future
• On some properties of DNA graphs
• scientific article; zbMATH DE number 4142064

Cites work

• scientific article; zbMATH DE number 9847 (Why is no real title available?)
• scientific article; zbMATH DE number 2200042 (Why is no real title available?)
• scientific article; zbMATH DE number 3231691 (Why is no real title available?)
• DNA origami and the complexity of Eulerian circuits with turning costs
• DNA origami and unknotted A-trails in torus graphs
• Design tools for reporter strands and DNA origami scaffold strands
• Graphs on surfaces
• Graphs on surfaces. Dualities, polynomials, and knots
• Matching, Euler tours and the Chinese postman
• On existence of reporter strands in DNA-based graph structures
• The Genus, Regional Number, and Betti Number of a Graph
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Topological graph theory.
• Unknotted strand routings of triangulated meshes

Cited in

(3)

• On existence of reporter strands in DNA-based graph structures
• Design formalism for DNA self-assembly of polyhedral skeletons using rigid tiles
• The topology of scaffold routings on non-spherical mesh wireframes

This page was built for publication: Edge-outer graph embedding and the complexity of the DNA reporter strand problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2315018)