DNA- and RNA-Based Computing Systems. Группа авторов

Скачать книгу

the maximal clique problem.

First, all possible cliques in the graph of N vertices are represented by an N‐digit binary string. In the clique, if the vertex is present, then it is represented by “1,” and if the vertex is absent, then it is represented by “0.” For the case of 5‐vertex graph (shown in Figure 2.6a), a clique involving {5, 4, 2} vertices is represented by a binary string as {11010}. Initially, all possible combinations of this N‐digit binary number are generated. Some of the vertices in the graph are not connected by the edges. A graph of such unconnected vertices is referred to as the complementary graph (see Figure 2.6b). In the next step, the combinations comprising the edges present in the complementary graph are removed. For the given illustrative example (Figure 2.6b), the combinations with {cc11c} and {c11cc} are removed from the data pool (c ɛ {0, 1}). Lastly, find out the binary number having the largest number of “1,” which represents the size of the maximal clique. This procedure is performed using the DNA sequences as follows.

Each bit in the above binary string corresponds to a vertex and is represented as a DNA sequence having three parts. In this, the second part corresponds to the vertex number, whereas the first and the third part correspond to the position number. Further, these vertices have to be connected in sequential order (e.g. V₁–V_N) as represented in the binary string. In order to have such connection, the value “0” for the first vertex is represented as P₁V₁⁰P₂, whereas the value “1” is represented by P₁V₁¹P₂. Since the next vertex V₂ has to be connected to V₁, its “0” value is represented by the complementary sequence , whereas its value “1” is represented by the sequence . Similarly, the next vertex V₃ will be connected to V₂ by P₃V₃⁰P₄ and P₃V₃¹P₄ for “0” and “1” values. Thus, all odd‐numbered vertices are represented by P_iV_i⁰P_i+1 and P_iV_i¹P_i+1 for “0” and “1” values, whereas those for even‐numbered vertices are represented by and, respectively. Further, all sequences with have 10 nucleotides representing the second part, whereas these are absent in. The ssDNA sequences corresponding to each bit combine in a sequential manner to form a dsDNA representing all combination of 0 or 1 for each vertex. Initially, all the sequences starting with P₁ and ending with P_N are amplified using PCR. The complementary graph is removed from the data pool by treating the DNA solutions using the restriction enzyme repeatedly for each edge present in the corresponding graph. For each edge, the DNA solution is divided into two equal parts in two tubes, and the restriction enzymes corresponding to the constituting vertices are added in the respective tubes. After restriction enzyme digestion, solutions of both tubes are added, and the process is repeated for all the edges of the corresponding graph. After this, a PCR is performed with starting P₁ and ending P_N. The amplified solutions are then analyzed using gel electrophoresis to obtain the maximal clique for the given supergraph. On the gel electrophoresis, the largest clique is corresponding to the shortest DNA strands. This is primarily because all the sequences comprising maximum will lead to the maximum “1”s in the binary string and will have the shortest length in base pairs. Such strands are analyzed by cloning and sequencing to obtain the maximal clique. For the given illustrative example (Figure 1.12b), {cc11c} and {c11cc} sequences will be removed. Therefore, the sequences that will lead to the maximal clique will be {11011}. From these, the maximal size of the clique for the given illustrative example is four, which corresponds to the clique V₁–V₂–V₄–V₅.

      2.2.6 Chao's Model

      Chao et al. [13] developed a single‐molecule “DNA navigator” to solve a maze (tree graph) of 10 vertices with three junctions. In this, the desired path is explored out of all possible paths of the maze present on an origami that is used as a substrate. On this origami, some sites are specifically used for the binding of the vertices of the tree graph. This helps in the propagation of the path on the origami.

The DNA used for the process is very specific in size and design. The designing of DNA is described next. Hairpin DNA Y is attached to the origami and has a typical sequence layout of the structure , as shown in Figure 2.7. Another type of DNA used is hairpin DNA Z, which is present freely in the solution. Its structure is like . Additionally, an initiator DNA that has a sequence is used to start the process. This initiator DNA binds to the entry vertex. Similarly, an exit DNA is present, which does not have a loop to form a hairpin.

Figure 2.7 Chao's single‐molecule DNA navigator [13] for solving the maze.

      After the binding of the initiator, a hairpin loop of the DNA Y opens to make it free to bind to DNA Z and vice versa as both have complementary sites for free form of each other. This type of hybridization continues until it reaches the exit DNA. This hybridization chain also produces those paths that are not the solution to the maze. The exit DNA corresponding to an end vertex of the maze is biotin labeled. If the path is correct, then this biotin‐labeled DNA is free from the exit vertex; otherwise, biotin remains attached to the DNA corresponding to the exit vertex. All the biotin‐labeled sequences are then removed from the solution by streptavidin magnetic beads. The correct path sequence remained in the solution as it is not attached to the biotin. This solution is then analyzed by AFM for identifying the final path.

      2.2.7 DNA Origami

Self‐assembly of DNA is one of the most popular techniques used to create a variety of two‐dimensional and three‐dimensional structures. The DNA origami is an excellent example of self‐assembly of DNA, which was introduced by Rothemund [14]. The procedure of DNA origami is shown in Figure 2.8. DNA origami is generated from a thousand base pair long ssDNA, known as a scaffold. Some shorter and linear ssDNA called staples are mixed with the scaffold to create DNA origami. For this purpose, the solution mixture is first heated to 95 °C. The solution is then cooled down to room temperature from 95 °C; throughout the cooling, the staples bind to the scaffold through Watson–Crick complementary base pairing. The scaffold then becomes a static structure or pattern of DNA. The sequence of DNA staples results in the formation of various shapes, for example, squares, smiley faces, cube, hexagon, star, and many more.

Скачать книгу