اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDNA origami and the complexity of Eulerian circuits with turning costs
68
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
Biological materials are self-assembled with near-atomic precision in living cells, whereas synthetic 3D structures generally lack such precision and controllability. Recently, DNA nanotechnology, especially DNA origami technology, has been useful in
the bottom-up fabrication of well-defined nanostructures ranging from tens of nanometres to sub-micrometres. In this Primer, we summarize the methodologies of DNA origami technology, including origami design, synthesis, functionalization and characterization. We highlight applications of origami structures in nanofabrication, nanophotonics and nanoelectronics, catalysis, computation, molecular machines, bioimaging, drug delivery and biophysics. We identify challenges for the field, including size limits, stability issues and the scale of production, and discuss their possible solutions. We further provide an outlook on next-generation DNA origami techniques that will allow in vivo synthesis and multiscale manufacturing.
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. T
his 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.
In this paper, we characterize a duality relation between Eulerian recurrences and Eulerian recurrence systems, which generalizes and unifies Hermite-Biehler decompositions of several enumerative polynomials, including flag descent polynomials for hy
peroctahedral group, flag ascent-plateau polynomials for Stirling permutations, up-down run polynomials for symmetric group and alternating run polynomials for hyperoctahedral group. As applications, we derive some properties of associated enumerative polynomials. In particular, we find that both the ascent-plateau polynomials and left ascent-plateau polynomials for Stirling permutations are alternatingly increasing, and so they are unimodal with modes in the middle.
We demonstrate hierarchical assembly of plasmonic toroidal metamolecules, which exhibit tailored optical activity in the visible spectral range. Each metamolecule consists of four identical origami-templated helical building blocks. Such toroidal met
amolecules show stronger chiroptical response than monomers and dimers of the helical building blocks. Enantiomers of the plasmonic structures yield opposite circular dichroism spectra. The experimental results agree well with the theoretical simulations. We also demonstrate that given the circular symmetry of the structures, distinct chiroptical response along their axial orientation can be uncovered via simple spin-coating of the metamolecules on substrates. Our work provides a new strategy to create plasmonic chiral platforms with sophisticated nanoscale architectures for potential applications such as chiral sensing using chemically-based assembly systems.
We present a modelling framework, and basic model parameterization, for the study of DNA origami folding at the level of DNA domains. Our approach is explicitly kinetic and does not assume a specific folding pathway. The binding of each staple is ass
ociated with a free-energy change that depends on staple sequence, the possibility of coaxial stacking with neighbouring domains, and the entropic cost of constraining the scaffold by inserting staple crossovers. A rigorous thermodynamic model is difficult to implement as a result of the complex, multiply connected geometry of the scaffold: we present a solution to this problem for planar origami. Coaxial stacking and entropic terms, particularly when loop closure exponents are taken to be larger than those for ideal chains, introduce interactions between staples. These cooperative interactions lead to the prediction of sharp assembly transitions with notable hysteresis that are consistent with experimental observations. We show that the model reproduces the experimentally observed consequences of reducing staple concentration, accelerated cooling and absent staples. We also present a simpler methodology that gives consistent results and can be used to study a wider range of systems including non-planar origami.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
