RECORD
DNA origami and the complexity of Eulerian circuits with turning costs
Combinatorics · Submitted 18 Sep 2013
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim By showing that it leads to a solution to the 3-SAT problem, we prove that the general problem of finding an optimal route for a scaffolding strand for such structures is NP-hard.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Building a structure using self-assembly of DNA molecules by origami folding requires finding a route for the scaffolding strand through the desired structure. When the target structure is a 1-complex (or the geometric realization of a graph), an optimal route corresponds to an Eulerian circuit through the graph with minimum turning cost. By showing that it leads to a solution to the 3-SAT problem, we prove that the general problem of finding an optimal route for a scaffolding strand for such structures is NP-hard. We then show that the problem may readily be transformed into a Traveling Salesman Problem (TSP), so that machinery that has been developed for the TSP may be applied to find optimal routes for the scaffolding strand in a DNA origami self-assembly process. We give results for a few special cases, showing for example that the problem remains intractable for graphs with maximum degree 8, but is polynomial time for 4-regular plane graphs if the circuit is restricted to following faces. We conclude with some implications of these results for related problems, such as biomolecular computing and mill routing problems.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Building a structure using self-assembly of DNA molecules by origami folding requires finding a route for the scaffolding strand through the desired structure. | background 1.00 | 0.07 | 0.02 | asserted 1.00 |
| s1 | When the target structure is a 1-complex (or the geometric realization of a graph), an optimal route corresponds to an Eulerian circuit through the graph with minimum turning cost. | background 0.73 | 0.24 | 0.06 | asserted 1.00 |
| s2 | By showing that it leads to a solution to the 3-SAT problem, we prove that the general problem of finding an optimal route for a scaffolding strand for such structures is NP-hard. | result 0.95 | 0.94 | 0.66 | asserted 1.00 |
| s3 | We then show that the problem may readily be transformed into a Traveling Salesman Problem (TSP), so that machinery that has been developed for the TSP may be applied to find optimal routes for the scaffolding strand in a DNA origami self-assembly process. | contribution 0.46 | 0.91 | 0.15 | hedged possibility 0.68 |
| s4 | We give results for a few special cases, showing for example that the problem remains intractable for graphs with maximum degree 8, but is polynomial time for 4-regular plane graphs if the circuit is restricted to following faces. | result 0.99 | 0.95 | 0.08 | asserted 1.00 |
| s5 | We conclude with some implications of these results for related problems, such as biomolecular computing and mill routing problems. | interpretation 0.97 | 0.51 | 0.12 | asserted 0.47 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Building a structure using self-assembly of DNA molecules by origami folding requires finding a route for the scaffolding strand through the desired structure. When the target structure is a 1-complex (or the geometric realization of a graph), an optimal route corresponds to an Eulerian circuit through the graph with minimum turning cost. By showing that it leads to a solution to the 3-SAT problem, we prove that the general problem of finding an optimal route for a scaffolding strand for such structures is NP-hard. We then show that the problem may readily be transformed into a Traveling Salesman Problem (TSP), so that machinery that has been developed for the TSP may be applied to find optimal routes for the scaffolding strand in a DNA origami self-assembly process. We give results for a few special cases, showing for example that the problem remains intractable for graphs with maximum degree 8, but is polynomial time for 4-regular plane graphs if the circuit is restricted to following faces. We conclude with some implications of these results for related problems, such as biomolecular computing and mill routing problems.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.