Читать книгу DNA- and RNA-Based Computing Systems - Группа авторов - Страница 23

Ouyang et al. [11] solved a maximal clique problem using DNA computing method. A maximal clique is the largest subset in the graph in which each vertex is connected to every other vertex in the subset. In maximal clique problem, the maximum size of the clique in terms of the vertices has to be evaluated. For example (Figure 2.6a), the graph has five vertices, and eight edges where the vertices (5, 4, 2, 1) is the largest clique; thus the maximum size of the clique is four. Ouyang et al. [11] solved the maximal clique problem using DNA computing as follows.

Figure 2.6 (a) The five‐node graph and (b) its complementary graph used to solve 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₅.