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

Authors: Risheng Wang; Zhixiang Yin; Jing Yang; Xinmu Yang; Zhen Tang
Journal: Journal of Mathematics
 (2021)

---

## 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.


---

## Body

## 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 Figure1.Figure 1
Basic principle of the hybrid chain reaction.C1 and C2 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 C1 and the hairpin segment of C1 are opened, as shown in the middle of Figure 1. The exposed section of C1 hybridizes with C2, and the hairpin section of C2 is opened, as shown in the right side of Figure 1. The exposed section of C2 continues to hybridize with the next C1, open up the clamp structure, and repeat the reaction in turn until C1 and C2 in the solution are exhausted. Finally, a long DNA nanowire assembled spontaneously by alternate hybridization of C1 and C2 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 thei-th person to complete the j-th task is Cij. Then, n individuals and n tasks are combined one by one to get n2 costs, which are listed into a matrix to get the coefficient matrix of the assignment problem.


## 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 Figure1.Figure 1
Basic principle of the hybrid chain reaction.C1 and C2 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 C1 and the hairpin segment of C1 are opened, as shown in the middle of Figure 1. The exposed section of C1 hybridizes with C2, and the hairpin section of C2 is opened, as shown in the right side of Figure 1. The exposed section of C2 continues to hybridize with the next C1, open up the clamp structure, and repeat the reaction in turn until C1 and C2 in the solution are exhausted. Finally, a long DNA nanowire assembled spontaneously by alternate hybridization of C1 and C2 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 thei-th person to complete the j-th task is Cij. Then, n individuals and n tasks are combined one by one to get n2 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 hasn×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 2
The diagram of the origami substrate and hairpin structure.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 Figure3(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).Figure 3
Starting chain (a) and intermediate chain (b).
(a)(b)


### 3.2. Model Graphic Realization

According to the composition of the model, the combination graph reflecting the assignment problem matrix is designed. The graph hasnn 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∗ 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∗ 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 ai, bi, ci,… For other molecular beacons, the design of this segment is the same, and we mark it as segment e.Figure 4
Hairpin structure designed on the origami substrate.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 Figure5. 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 5
Opening process after adding the starting chain.The biological algorithm based on the calculation model of the hybrid chain reaction assignment problem is as follows:(1)
For the assignment problem withn 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 Table1 is as follows.Table 1
Assignment problem efficiencycij data.
Number of peopleTask123114122323341It 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 Figure6. 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 a1, b2, c3, that is, the optimal solution is (1, 0, 0, 0, 1, 0, 0, 0, 0, 1).Figure 6
Optimal solution of the origami substrate after the reaction.


## 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 hasn×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 2
The diagram of the origami substrate and hairpin structure.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 Figure3(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).Figure 3
Starting chain (a) and intermediate chain (b).
(a)(b)


## 3.2. Model Graphic Realization

According to the composition of the model, the combination graph reflecting the assignment problem matrix is designed. The graph hasnn 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∗ 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∗ 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 ai, bi, ci,… For other molecular beacons, the design of this segment is the same, and we mark it as segment e.Figure 4
Hairpin structure designed on the origami substrate.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 Figure5. 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 5
Opening process after adding the starting chain.The biological algorithm based on the calculation model of the hybrid chain reaction assignment problem is as follows:(1)
For the assignment problem withn 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 Table1 is as follows.Table 1
Assignment problem efficiencycij data.
Number of peopleTask123114122323341It 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 Figure6. 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 a1, b2, c3, that is, the optimal solution is (1, 0, 0, 0, 1, 0, 0, 0, 0, 1).Figure 6
Optimal solution of the origami substrate after the reaction.


## 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.



---

*Source: 5570737-2021-07-12.xml*