Research on DNA Nanostructures Based on the Hybrid Chain Reaction for the Assignment Problem

Abstract

Nanostructures with information processing play an important role in many fields. It is an excellent approach to the application that DNA nanostructures represented by DNA origami molecules combine with the hybrid chain reaction. In this paper, the assignment problem is mapped to a combinatorial graph on the DNA origami substrate. The graph has several modules corresponding to the time efficiency matrix of the assignment problem. The starting chain of the corresponding module is hybridized with the hairpin structure of the starting point, and the corresponding module is opened to emit light. The feasible solution to the problem can be obtained by observing the light-emitting fluorescent numbers of the opened modules. The fluorescent numbers of all the opened modules are added up on the same origami substrate, then different opening methods in different test tubes are compared, and the optimal solution is obtained.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

DNA nanostructure is being studied by more and more scholars, and it has become the main way to construct nanomaterials. DNA nanostructures from one-dimensional to two-dimensional and three-dimensional structures play an increasingly important role in related issues [1–4]. In 2006, Rothemund proposed a new DNA nano-self-assembly method—DNA origami [5]. DNA origami is a kind of phage DNA chain as a scaffold. We call it scaffold chain folding back and forth using multiple stapling chains to fix the shape, and we can get a sophisticated two-dimensional structure. DNA origami has the advantages of high assembly efficiency, nanostructure programmability, and nanostructure addressability. DNA origami can construct many complex and diverse nanostructures, and its substrate has great advantages in assembling functional carbon nanotubes, nanoparticles, and proteins [6, 7]. Ke et al. designed and constructed a tetrahedral three-dimensional molecular container by DNA origami. The three-dimensional molecular cage has high stability and has potential application prospects in the nanofield [8]. Tikhomirov and his team proposed a fractal assembly method for micron-scale DNA origami arrays with arbitrary patterns. In this paper, square DNA origami tiles with patterns on the surface are used as basic building units to construct patterns such as Mona Lisa and rooster. The construction and successful implementation of this assembly method demonstrate the addressability of DNA origami [9]. Wang et al. used DNA origami nanostructures to visually observe cell uptake and metastasis of tumor cells [10]. DNA origami can construct highly complex nanostructures, which has a wide range of potential applications in the nanofield. In fact, DNA origami has been widely used in logic operation, single-molecule detection, and other fields [11, 12]. DNA origami has been used as the basic template, carbon nanotubes, and protein structure for the assembly of functional metal nanoparticles [13–15].

Hybrid chain reaction (HCR) is a DNA molecular structure interaction method proposed by Dirks and Pierce in 2004. It uses competitive hybridization between nucleic acid probes as the energy source to self-assemble a nucleic acid nanostructure to realize signal amplification [16]. Hybridized chain reaction can take place at room temperature. It is easy to operate and has lower experimental cost. By combining HCR with G-quadruplex, Dong et al. designed a fluorescent sensor for unlabeled detection of target DNA. When the target DNA strand exists, it opens two hairpin probes and hybridizes them as a trigger chain. HCR forms long double chains and releases G-quadruplex to detect target DNA by changing the fluorescence intensity before and after the reaction [17]. Xiao et al. designed a variety of chemiluminescent imaging technologies aiming at the hybridization chain reaction amplification of DNA microarrays and adjacent binding [18]. In this paper, the correct solution of logical circuit can be obtained on the basis of hybrid chain reaction. Chao et al. integrated DNA origami with the hybrid chain reaction to design a single-molecule DNA navigator to solve the maze problem. In this design, the 2D origami model is used as the base, and the near-end-chain exchange cascade reaction based on the hybrid chain reaction is used for unidirectional amplification on the base. Finally, the correct route of the maze problem is obtained through the atomic force microscope observation [19]. It has been proved to have good application prospects like hybrid chain reaction combined with DNA origami structure [20–32].

DNA nanostructure and hybrid chain reaction were used to design the graph on the origami substrate. The starting chain was put into the reaction solution and hybridized with the hairpin structure to open the corresponding module. The sequence of the DNA strand in the model is carefully designed, which ensures that the system is stable in solution without any reaction. By reacting with the hairpin structure on the origami substrate in the solution, the corresponding module is opened, and the fluorescence emits light. By adding up the fluorescent numbers of the opened modules on the same origami substrate, we can get the feasible solution.

2. Background Knowledge

2.1. DNA Origami and Hybrid Chain Reaction

DNA origami is to fold a long M13mp18 phage DNA strand back and forth and to use multiple short chains to fix the shape to obtain the fine and complex structure. The design of the DNA chain is relatively simple, and the assembly efficiency is high. The site selection can be achieved by redesigning the staple chain (short chain) and scaffold chain (long chain) to complement each other.

Hybrid chain reaction (HCR) is a new signal amplification method proposed by Dirks and Pierce. It designs different oligonucleotides and uses a small nucleotide chain as an initiator to induce oligonucleotides to hybridize with each other to form DNA with spatial structure. The reaction conditions are mild, and the operation is simple. The reaction principle is shown in Figure 1.

[figure omitted; refer to PDF]

C ₁ and C₂ are two hairpin DNA strands that are stable in solution. They are composed of sticky ends, double-stranded “stems,” and single-stranded loops, as shown in the left side of Figure 1. T is the starting strand, which is a single strand of DNA composed of two parts. When the starting chain is added, its two segments hybridize with the sticky end, and the stem of C₁ and the hairpin segment of C₁ are opened, as shown in the middle of Figure 1. The exposed section of C₁ hybridizes with C₂, and the hairpin section of C₂ is opened, as shown in the right side of Figure 1. The exposed section of C₂ continues to hybridize with the next C₁, open up the clamp structure, and repeat the reaction in turn until C₁ and C₂ in the solution are exhausted. Finally, a long DNA nanowire assembled spontaneously by alternate hybridization of C₁ and C₂ is formed. Each priming strand is equivalent to the growth site of a DNA nanowire.

2.2. Assignment Problem

The assignment problem is a special integer programming problem. There are a certain number of tasks and the same number of people. Each person can complete the task, but the time cost is different. So, we need to find a way of assignment to minimize the total time (or the total efficiency of completing the tasks is the highest). Such problems are called assignment problems.

It is often encountered in life. Each person has different expertise and completes the task differently, so the efficiency is also different. In an actual assignment problem, the cost for the i-th person to complete the j-th task is C_ij. Then, n individuals and n tasks are combined one by one to get n² costs, which are listed into a matrix to get the coefficient matrix of the assignment problem.

3. DNA Origami Model

3.1. Model Composition and Design

For the assignment problem, we present a combinatorial graph of the hairpin structure on DNA origami. It is mapped to the efficiency or time matrix of the assignment problem. The combination has $n\times n$ modules, and each module has a corresponding number of hairpin structures, corresponding to the efficiency or time required for a person to complete a task in the problem. In each module of the graph, the first chain is a common hairpin structure, and the rest are molecular beacons with fluorescent group and quenching group markers, as shown in Figure 2. The origami substrate is represented by gray in the figure. On the origami substrate, there are staple chains (light purple in the figure) extending at corresponding distances, and they connect molecular beacons and ordinary hairpin structures. The distance between adjacent hairpin structures in each module is just the distance that can be connected by opening the auxiliary chain (intermediate chain). Enough space is provided between modules, which enables the same module to react completely and avoids the interaction of different modules.

[figure omitted; refer to PDF]

Molecular beacon and hairpin structure: they are composed of several oligoglycosidic acid segments. A “ring” is a single chain, two complementary segments form a double chain, and the other segment is complementary to the sticky end of a staple chain extending from the origami base to fix the chain on the origami substrate. The molecular beacon has two more sticky ends with the luminescent fluorescent group and quenching group than the ordinary hairpin structure. They do not light up when they are not turned on; they are only turned on while the starting chain and auxiliary chain are added. The molecular beacon fixed on the origami substrate can represent the efficiency (the time required) of the assignment problem. In this way, it can be used for graphic design to solve the optimal problem.

The DNA origami substrate with the hairpin structure can be stable in solution. To open the hairpin structure, the corresponding starting chain is added, whose structure is composed of two oligonucleotide fragments, as shown in Figure 3(a). Only the corresponding starting chain can open the corresponding hairpin structure. After opening the first hairpin structure of each module, the intermediate chain needs to open all the other molecular beacons in the module. The intermediate chain can also exist stably in the solution without adding the starting chain. The intermediate chain is composed of four oligoglycosidic acid segments, as shown in Figure 3(b).

[figures omitted; refer to PDF]

3.2. Model Graphic Realization

According to the composition of the model, the combination graph reflecting the assignment problem matrix is designed. The graph has nⁿ modules. Each module starts with an ordinary hairpin structure followed by the molecular beacons. The base of the hairpin structure at the beginning of each module is different, while the other molecular beacons are the same. Here, because the hairpin structure of the first starting point of each module can only be opened by adding the corresponding starting chain, we will design the molecular beacon of all modules after the hairpin structure of the starting point to be the same, which can greatly simplify the design and model construction. The hairpin structure base of the starting point is mostly the same as the molecular beacon base; only the base of the molecular beacon at the binding marker and the one at the junction of the starting chain are different, as shown in Figure 4. In the composite pattern on the origami substrate, all the starting hairpin structures can be regarded as composed of five oligoglycosidic acid fragments, and the subsequent molecular beacon can be regarded as composed of five oligoglycosidic acid fragments, fluorescent groups and quenching groups. One of them complements the sticky end of the staple chain extending from the base, and all the hairpins in this section have the same structure. The rest of the segments are shown in the hairpin structure in Figure 4, and we mark them with letters. The design of three sections is the same for all hairpin structures. There are two complementary segments forming a double chain, named s and s${}^{\ast }$ segments, respectively, and one segment is a ring structure, named o segment. Compared with the hairpin structure of the starting point, the two sticky ends of the s and s${}^{\ast }$ segments of the latter molecular beacon have luminescent fluorescent groups and absorbable fluorescence quenching groups. However, the oligoglycosidic acid fragment is different that binds the starting chain and the hairpin structure at the beginning of each module, which is labeled a_i, b_i, c_i,… For other molecular beacons, the design of this segment is the same, and we mark it as segment e.

[figure omitted; refer to PDF]

Origami base and intermediate chain have been in the solution in advance, and then the starting chain corresponding to the opening module is added to the solution. When the start chain is added, it opens the hairpin structure of the starting point. The opening process is shown in Figure 5. The corresponding section of the starting chain complements the corresponding section of the starting hairpin structure to open the hairpin structure. Correspondingly, the starting hairpin structure and the intermediate chain complement each other and then open the intermediate chain. The intermediate chain can continue to complement the molecular beacon, open the molecular beacon, and make the graph luminescent.

[figure omitted; refer to PDF]

The biological algorithm based on the calculation model of the hybrid chain reaction assignment problem is as follows:

(1) For the assignment problem with n implementers and n tasks, all possible solutions are n!, corresponding to n! different opening modules’ combinations of the DNA strand.

(2) Construct the combinatorial graph on DNA origami (n) of corresponding variables, and put them in the test tubes (n! in total). Add a set of DNA start strands to each test tube, and perform the DNA hybrid chain reaction.

(3) After the reaction is completed, each test tube has a combination mode of opening the hairpin structure module, corresponding to a task completion mode, which is the feasible solution of the problem.

(4) By comparing the light-emitting fluorescent number in different test tubes, the efficiency of different ways is obtained, and then the optimal solution is determined.

3.3. Case Analysis

To illustrate the feasibility of DNA computing to solve the assignment problem, an example of an assignment problem is given to verify it.

The calculation process of the assignment problem with an efficiency value in Table 1 is as follows.

Table 1

Assignment problem efficiency c_ij data.

Number of people	Task
	1	2	3
1	1	4	1
2	2	3	2
3	3	4	1

It can be seen from the above algorithm that, for the assignment problem of three implementers completing three tasks, all possible solutions are 3! = 6, corresponding to the DNA origami base combination graph composed of nine modules. Each module is composed of a common hairpin structure at the starting point and a luminous molecular beacon at the back. The number of molecular beacons corresponds to the efficiency of an implementer to complete a task. Because the possible solutions are 6, the designed origami substrate is put into 6 test tubes. A set of promoter chains were added to each tube and hybridized at room temperature. Each group of chains is the starting chain corresponding to three modules in different rows and columns. In this way, in each test tube, three modules in different rows and columns are opened to emit light. After the reaction, the DNA strand on the origami substrate is shown in Figure 6. By observing the fluorescent number of each tube, the one with the least fluorescent number is the optimal solution. Finally, the origami base with the least open fluorescent number is a₁, b₂, c₃, that is, the optimal solution is (1, 0, 0, 0, 1, 0, 0, 0, 0, 1).

[figure omitted; refer to PDF]

4. Simulation

In this paper, a DNA origami model based on the DNA nanostructure is constructed, which can be used to solve assignment problems. The simulation results are consistent with the expected results of the system. The molecular beacon was used as reactant, and the reaction concentration gradually approached 0. The concentration of intermediate chain tends to be stable. The simulation results show that the model has good performance compared with the previous work.

5. Conclusion

In this paper, DNA nanostructures are combined with the hybrid chain reaction to establish a DNA origami model that solves the assignment problem. We design the hairpin structure on the origami base, which can solve simple assignment problems. By adding the starting chain, the corresponding module is opened to obtain the optimal solution. With the development of molecular biology and bioengineering, this method is expected to have more progress in reusability and can be further expanded to solve more complex problems.

References

[1] E. Winfree, Algorithmic Self-Assembly of DNA, 1998.

[2] T. H. LaBean, "Another dimension for DNA art," Nature, vol. 459 no. 7245, pp. 331-332, DOI: 10.1038/459331a, 2009.

[3] P. Yin, H. M. T. Choi, C. R. Calvert, N. A. Pierce, "Programming biomolecular self-assembly pathways," Nature, vol. 451 no. 7176, pp. 318-322, DOI: 10.1038/nature06451, 2008.

[4] P. Yin, R. F. Hariadi, S. Sahu, "Programming DNA tube circumferences," Science, vol. 321 no. 5890, pp. 824-826, DOI: 10.1126/science.1157312, 2008.

[5] P. W. K. Rothemund, "Folding DNA to create nanoscale shapes and patterns," Nature, vol. 440 no. 7082, pp. 297-302, DOI: 10.1038/nature04586, 2006.

[6] F. Zhang, J. Nangreave, Y. Liu, H. Yan, "Reconfigurable DNA origami to generate quasifractal patterns," Nano Letters, vol. 12 no. 6, pp. 3290-3295, DOI: 10.1021/nl301399z, 2012.

[7] B. Wei, M. Dai, P. Yin, "Complex shapes self-assembled from single-stranded DNA tiles," Nature, vol. 485 no. 7400, pp. 623-626, DOI: 10.1038/nature11075, 2012.

[8] Y. Ke, J. Sharma, M. Liu, K. Jahn, Y. Liu, H. Yan, "Scaffolded DNA origami of a DNA tetrahedron molecular container," Nano Letters, vol. 9 no. 6, pp. 2445-2447, DOI: 10.1021/nl901165f, 2009.

[9] G. Tikhomirov, P. Petersen, L. Qian, "Fractal assembly of micrometre-scale DNA origami arrays with arbitrary patterns," Nature, vol. 552 no. 7683, pp. 67-71, DOI: 10.1038/nature24655, 2017.

[10] P. Wang, M. A. Rahman, Z. Zhao, "Visualization of the cellular uptake and trafficking of DNA origami nanostructures in cancer cells," Journal of the American Chemical Society, vol. 140 no. 7, pp. 2478-2484, DOI: 10.1021/jacs.7b09024, 2018.

[11] C. Zhang, J. Yang, S. Jiang, Y. Liu, H. Yan, "DNAzyme-based logic gate-mediated DNA self-assembly," Nano Letters, vol. 16 no. 1, pp. 736-741, DOI: 10.1021/acs.nanolett.5b04608, 2016.

[12] D. Wang, Y. Fu, J. Yan, "Molecular logic gates on DNA origami nanostructures for microRNA diagnostics," Analytical Chemistry, vol. 86 no. 4, pp. 1932-1936, DOI: 10.1021/ac403661z, 2014.

[13] H. Yan, S. H. Park, G. Finkelstein, J. H. Reif, T. H. LaBean, "DNA-templated self-assembly of protein arrays and highly conductive nanowires," Science, vol. 301 no. 5641, pp. 1882-1884, DOI: 10.1126/science.1089389, 2003.

[14] N. V. Voigt, T. Tørring, A. Rotaru, "Single-molecule chemical reactions on DNA origami," Nature Nanotechnology, vol. 5 no. 3, pp. 200-203, DOI: 10.1038/nnano.2010.5, 2010.

[15] H. T. Maune, S.-P. Han, R. D. Barish, "Self-assembly of carbon nanotubes into two-dimensional geometries using DNA origami templates," Nature Nanotechnology, vol. 5 no. 1, pp. 61-66, DOI: 10.1038/nnano.2009.311, 2010.

[16] R. M. Dirks, N. A. Pierce, "From the cover: triggered amplification by hybridization chain reaction," Proceedings of the National Academy of Sciences, vol. 101 no. 43, pp. 15275-15278, DOI: 10.1073/pnas.0407024101, 2004.

[17] J. Dong, X. Cui, Y. Deng, Z. Tang, "Amplified detection of nucleic acid by G-quadruplex based hybridization chain reaction," Biosensors and Bioelectronics, vol. 38 no. 1, pp. 258-263, DOI: 10.1016/j.bios.2012.05.042, 2012.

[18] Q. Xiao, J. Wu, P. Dang, H. Ju, "Multiplexed chemiluminescence imaging assay of protein biomarkers using DNA microarray with proximity binding-induced hybridization chain reaction amplification," Analytica Chimica Acta, vol. 1032, pp. 130-137, DOI: 10.1016/j.aca.2018.05.043, 2018.

[19] J. Chao, J. Wang, F. Wang, "Solving mazes with single-molecule DNA navigators," Nature Materials, vol. 18 no. 3, pp. 273-279, DOI: 10.1038/s41563-018-0205-3, 2019.

[20] M. Xiao, W. Lai, T. Man, "Rationally engineered nucleic acid architectures for biosensing applications," Chemical Reviews, vol. 119 no. 22, pp. 11631-11717, DOI: 10.1021/acs.chemrev.9b00121, 2019.

[21] S. Shah, A. K. Dubey, J. Reif, "Improved optical multiplexing with temporal DNA barcodes," ACS Synthetic Biology, vol. 8 no. 5, pp. 1100-1111, DOI: 10.1021/acssynbio.9b00010, 2019.

[22] S. D. Mason, Y. Tang, Y. Li, X. Xie, F. Li, "Emerging bioanalytical applications of DNA walkers," TrAC Trends in Analytical Chemistry, vol. 107, pp. 212-221, DOI: 10.1016/j.trac.2018.08.015, 2018.

[23] K. Chen, J. Zhu, F. Bošković, U. F. Keyser, "Nanopore-based DNA hard drives for rewritable and secure data storage," Nano Letters, vol. 20 no. 5, pp. 3754-3760, DOI: 10.1021/acs.nanolett.0c00755, 2020.

[24] Z. Zeng, R. Zhou, R. Sun, "Nonlinear hybridization chain reaction-based functional DNA nanostructure assembly for biosensing, bioimaging applications," Biosensors and Bioelectronics, vol. 173,DOI: 10.1016/j.bios.2020.112814, 2021.

[25] A. E. Kiouche, M. Bessedik, F. Benbouzid-SiTayeb, M. R. Keddar, "An efficient hybrid multi-objective memetic algorithm for the frequency assignment problem," Engineering Applications of Artificial Intelligence, vol. 87,DOI: 10.1016/j.engappai.2019.103265, 2020.

[26] Z. Zhang, Y. Yang, F. Pincet, M. C. Llaguno, C. Lin, "Placing and shaping liposomes with reconfigurable DNA nanocages," Nature Chemistry, vol. 9 no. 7, pp. 653-659, DOI: 10.1038/nchem.2802, 2017.

[27] X. Song, J. Reif, "Nucleic acid databases and molecular-scale computing," ACS Nano, vol. 13 no. 6, pp. 6256-6268, DOI: 10.1021/acsnano.9b02562, 2019.

[28] J. O’Brien, A. Murugan, "Temporal pattern recognition through analog molecular computation," ACS Synthetic Biology, vol. 8 no. 4, pp. 826-832, DOI: 10.1021/acssynbio.8b00503, 2019.

[29] G. Chatterjee, N. Dalchau, R. A. Muscat, A. Phillips, G. Seelig, "A spatially localized architecture for fast and modular DNA computing," Nature Nanotechnology, vol. 12 no. 9, pp. 920-927, DOI: 10.1038/nnano.2017.127, 2017.

[30] K. Sergio, W. J. Paschoalino, L. T. Kubota, "Supramolecular DNA origami nanostructures for use in bioanalytical applications," TrAC Trends in Analytical Chemistry, vol. 108, pp. 88-97, DOI: 10.1016/j.trac.2018.08.019, 2018.

[31] K. E. Bujold, A. Lacroix, H. F. Sleiman, "DNA nanostructures at the interface with biology," Chem, vol. 4 no. 3, pp. 495-521, DOI: 10.1016/j.chempr.2018.02.005, 2018.

[32] T. Fu, Y. Lyu, H. Liu, "DNA-based dynamic reaction networks," Trends in Biochemical Sciences, vol. 43 no. 7, pp. 547-560, DOI: 10.1016/j.tibs.2018.04.010, 2018.