In 1961, Feynman [1] proposed the idea of molecular computing, which was demonstrated by Adleman 33 years later. In 1994, Adleman [2] presented a DNA computing model in which DNA molecules were used as data, and enzymes and biological operations were used as tools in information processing. Since then, the DNA computing model has been developed in several new dimensions including theory, experiments, and applications. Studies in the past decade have shown that the DNA computing model is superior in solving optimal and graphical problems, especially in non-deterministic polynomial-time (NP)-complete problems. However, the main challenge of this model is that the size of DNA molecules used as data in information processing grows exponentially with an increase of problem size. This phenomenon is called exponential explosion, and is the biggest bottleneck preventing the development of DNA computing. To solve this problem, a parallel type of DNA computing model is proposed in this article, and several methods are used to overcome the biggest bottleneck.

In this section, we briefly introduce the latest developments in DNA computing research, and then outline the major innovative points of this article.

In 1994, Adleman [2] first explored the computing feasibility of DNA molecules by presenting a DNA computing model for the Hamiltonian path problem. After that, many studies were designed to show the advantage of the huge parallelism that is inherent in DNA-based computing. In 1995, Lipton [3] proposed a DNA computing model to solve the satisfiability (SAT) problem. In 1997, Ouyang et al. [4] designed a DNA computing model for the maximal clique problem. By using the DNA hairpin formation, Sakamoto et al. [5] solved the SAT problem. Rothemund [6] attempted to use DNA as instruments to implement Turing machine. In addition, DNA computing was applied to manipulate gene expression [7], [8]. Winfree [9] proposed a sticker model by DNA self-assembly. In 2002, Adleman’s research group invented a DNA computer to solve a 20-variable 3-SAT problem with a searching ability of 2²⁰ [10].

Graph vertex coloring is a way of coloring the vertices of graph G such that no two adjacent vertices share the same color. Although it is a classical NP-hard problem, graph coloring arises naturally in a variety of applications such as timetable schedules [11], register allocation [12], [13], and so forth. The analysis of approximation algorithms for graph coloring started with the work of Johnson [14]. Subsequently, O(n^{2/5}{\log }^{8/5}n)colors were used to color a 3-colorable graph with n vertices by Blum [15]. Karger et al. [16] provided a randomized polynomial time algorithm that colors a 3-colorable graph on vertices with \min \left\{O({\text{Δ}}^{1/3}{\log }^{1/2}\text{Δ}\log n)\text{,}O(n^{1/4}{\log }^{1/2}n)\right\} colors. Schiermeyer [17] gave a complicated algorithm for deciding 3-colorability in less than time O(1.415ⁿ). Beigel and Eppstein [18] improved the bound by giving a fast algorithm for (3, 2)-constraint satisfaction problem (CSP) for solving the 3-coloring problem in time O(1.3289ⁿ).

The major research into graph vertex coloring based on DNA computing is as follows: In 1999, Jonoska et al. [19] proposed the potential application of three-dimensional (3D) structures in the field of DNA computing, and showed that some DNA structures could theoretically be used in DNA computing. In 2003, they constructed 3-arm and 4-arm DNA molecules to solve the graph vertex 3-coloring problem based on the aforementioned studies [20], [21]. Liu et al. [22] proposed a DNA algorithm for the graph coloring problem based on surfaces. In 2003, Gao and Xu [23] presented a new DNA computing model for solving the graph vertex coloring problem, in which the technology of enzyme cutting was used to eliminate false solutions. In 2006, using the magnetic beads separation technology, Xu et al. [24] established a DNA computing model to solve the graph vertex coloring problem; this model was validated by a series of experiments.

We now present a novel DNA computing model for the graph vertex coloring problem; although we focus on analyzing k = 3, this method can be generalized to the situation of k > 3.

The basic idea of our model is to reduce the initial solution space by using the optimal method and process the data by a parallel polymerase chain reaction (PCR) operation. First, a given graph is divided into several subgraphs in order to make the bio-operations easier and delete as many false solutions possible. The subgraphs can then be solved in parallel according to the following steps: Determine the order of the vertices, determine the color set of each vertex in the subgraph, encode the DNA sequences, determine the probes, construct the initial solution space, and delete the false solutions (see Sections 3.3 Determining the order and color set for each vertex in the subgraphs, 3.4 Encoding, 3.5 Determining probes, 3.6 Construction of the initial solution space, 3.7 Deleting false solutions). Finally, the subgraphs are combined into the graph and implemented to delete false solutions gradually (see Section 3.8).

The main points of this article are as follows: ① The exponential explosion problem is solved by dividing subgraphs, reducing the vertex colors without losing solutions, and ordering the vertices in subgraphs; ② the bio-operation times can be greatly reduced by using a parallel PCR technology. Thus, the processing speed is remarkably improved in this model.

A 3-colorable graph with 61 vertices (Fig. 1) is used as an example to demonstrate how to use this computing model to solve the graph vertex coloring problem. In general, for a 3-colorable graph, the computing complexity is 3ⁿ. Therefore, the computing capacity of our parallel DNA computing model can reach O(3⁵⁹), when the colors of vertices v₁ and v_n are given.

This article is laid out as follows. In Section 2, we explain some notations and definitions of the graph coloring problem and PCR technology. In Section 3, the DNA computing model is illustrated, including algorithm steps, bio-operations, and technologies. In Section 4, a 3-coloring problem of a graph with 61 vertices is then solved by this computing model, and the specific experimental operations are described. Section 5 contains theory analysis, as we carefully examine the complexity of overcoming the exponential explosion phenomenon. In the last section, we conclude the article and point out the next possible research direction.

The work in this paper is always limited to finite, simple, and undirected graphs. In a given graph G, V(G), E(G), d_G(v), and Γ_G(v) denote the vertex set, edges set, degree of vertex v, and set of vertices adjacent to v of graph G, respectively, and are denoted using the short forms V, E, d_G, and Γ_G, respectively. We let V = {v₁, v₂, …, v_n} be the vertex set of a graph G, and denote the degree of v_i as d(v_i) (abbreviated as d_i, i = 1, 2, …, n). A walk denoted by W is an alternating sequence of vertices and edges, beginning and ending with a vertex, respectively, where each vertex is incident to both the edge that precedes it and the edge that follows it in the sequence, and where the vertices that precede and follow an edge are the end of that edge. A sequence of vertices is denoted by W, where W = v₁…v_k (k⩾0), beginning with vertex v₁ and ending with vertex v_k, and where v_i and v_i+1 are adjacent (i = 1, 2, …, k − 1). The length of a walk is the number of edges in it. A path is a walk in which all the vertices are distinct.

The vertex coloring of a graph G is an assignment from its vertex set to a color set such that two ends of each edge are assigned two different colors. Namely, it is a partition of V, where V(G)=V_1\cup V_2\cup \cdots \cup V_k, V_i\ne \varnothing (empty set), and V_i\cap V_j=\varnothing, i = 1, 2, …, k.

The minimum number of colors needed for such a coloring is called the chromatic number of G, and is usually denoted by χ(G). If a graph G can be colored by k (k ≥ χ(G)) colors, then the color set is denoted by C_k(G). In this article, we limit ourselves to a 3-colorable graph G and we always assume that C₃(G) = {r, b, y}, where r, b, and y denote red, blue, and yellow, respectively. In other words, the 3-coloring problem of a given graph G can be solved if we find a map f: V(G) → {r, b, y} with the property ∀uv ∈ E(G), f(u) ≠ f(v). The 3-coloring problem is a classical NP-complete problem [25]. Any terms and notations not defined here can be found in Ref. [26].

Definition 2.1: Let G be a simple graph with the vertex set V(G) = {v₁, v₂, …, v_n}. Let v_i1v_i2…v_in be an ordering of V(G), where v_ij ∈ V(G), j = 1, 2, …, n, and v_ij ≠ v_il if j ≠ l. The number of edges in the ordering v_i1v_i2…v_in, denoted by N_edge(v_i1v_i2…v_in), is defined as follows:

PCR is a technique that amplifies a few copies of DNA across several orders of magnitude, thereby generating millions or more copies of a particular DNA sequence. The three parts of PCR are carried out in the same vial with different temperatures. The three steps in PCR are: the denaturation of the strands, annealing the primer to the template, and the extension of new strands. At the end of a cycle, each DNA template in the vial has been exponentially duplicated. After n cycles, the number of the DNA molecules is y = (1 + x)ⁿ, where y is the copy number of DNA molecules, x is the efficiency of amplification, and n is the number of cycles.

In this section, we describe the DNA computing model in detail, including algorithm steps, bio-operations, and technologies.

In this model, limited PCR operations are exploited to delete the false solutions of a graph, and the DNA strands representing the true solutions of a given graph are sequenced to obtain the coloring of the given graph. The algorithm of this model is shown in Fig. 2.

Subgraph division can improve the computing efficiency in two aspects: On the one hand, the experiment can be operated more easily; on the other hand, most of false solutions can be deleted when constructing the initial solution space. Therefore, the appropriate division of a given graph G is of great significance in our model. Here G_j, V(G_j) ⊂ V(G), E(G_j) ⊂ E(G), where j = 1, 2, …, m − 1, is used to denote the primary subgraph. The method of subgraph division is demonstrated as follows:

Step 1: Determine the size of the subgraphs. The number of vertices in each subgraph should be consistent, ranging from 15 to 20. In addition, the edges in a subgraph should be as numerous as possible. In this way, the experiments can be conveniently performed, and most of the false solutions will be deleted when the initial solution space is constructed for each subgraph. Taking the graph G in Fig. 3 as an example, there are two divisions. In one case, the graph can be divided into two subgraphs G_1^{\prime } with vertex set V_1^{\prime }=\left\{1\text{,}2\text{,}3\text{,}4\text{,}5\text{,}6\text{,}7\text{,}16\text{,}17\text{,}18\text{,}19\text{,}20\text{,}21\text{,}22\right\}, and G_2^{\prime } with V_2^{\prime }=\left\{8\text{,}9\text{,}10\text{,}11\text{,}12\text{,}13\text{,}14\text{,}15\text{,}23\text{,}24\text{,}25\text{,}26\text{,}27\text{,}28\text{,}29\text{,}30\right\}. In another case, the graph can be divided into two subgraphs G_3^{\prime } with V_3^{\prime }=\left\{1\text{,}2\text{,}3\text{,}4\text{,}5\text{,}6\text{,}7\text{,}8\text{,}9\text{,}10\text{,}11\text{,}12\text{,}13\text{,}14\text{,}15\right\} and G_4^{\prime } with V_4^{\prime }=\left\{16\text{,}17\text{,}18\text{,}19\text{,}20\text{,}21\text{,}22\text{,}23\text{,}24\text{,}25\text{,}26\text{,}27\text{,}28\text{,}29\text{,}30\right\}. Obviously, the latter division method is better because the number of edges in subgraphs G_3^{\prime } and G_4^{\prime } is greater than in G_1^{\prime } and G_2^{\prime }.

Step 2: Obtain the first subgraph G_1^{\prime } with the bridge vertices u₁ and u₂. The bridge vertices should be adjacent and the sum of the degree of the bridge vertices should be maximal. If more than one pair of bridge vertices satisfy these conditions, we select the one pair (u₁ and u₂) that result in N_{\text{edge}}(u_1=v_{i1}{v}_{i2}\dots v_{in}=u_2) being the greatest (see Section 3.3 for more details). If more than one pair of bridge vertices satisfy this condition, we then choose any pair.

Step 3: Determine the second subgraph G_2^{\prime } containing bridge vertiex u₂ and a new bridge vertex u₃, which can be found using the following methods: The bridge vertex should be adjacent to the vertex u₂, and the degree is maximal in G_2^{\prime }. If more than one pair of bridge vertices satisfy these conditions, then choose one pair according to Step 2.

Step 4: Perform similar operations as those in Step 3 to obtain the other subgraphs with their bridge vertices.

It should be noted that: ① the size of the vertex set of the last subgraph G_m may not be equal to the others; and ② the bridge vertices in the last subgraph G_m may be u₁ and u_m−1, which is the bridge vertex of G_m−1 if u₁ and u_m−1 are adjacent.

In our DNA computing model, the bridge vertices are very important for the subgraph combination. The principle in choosing bridge vertices is that the sum of the degrees of two bridge vertices in one subgraph should be as large as possible. In this way, the size of the color set of the vertices adjacent to bridge vertices can be reduced (see Section 3.3). Moreover, the size of the initial solution space can also be reduced.

According to the steps above, the four divided subgraphs of graph G in Fig. 1 are shown in Fig. 4; the bridge vertices are 1, 16, 31, 46, and 61, respectively.

After subgraph division, the bridge vertices in each subgraph are determined. The algorithm for ordering the vertices in a subgraph should satisfy the following conditions: ① The bridge vertices must be considered as two endpoints in the ordering of the vertices subgraphs; and ② the number of edges in ordering (see Definition 2.1) should be as great as possible. Here, we take subgraph G₁ as an example. Suppose that the vertex set of subgraph G₁ is V(G₁) = {v₁, v₂, …, v_t} with the bridge vertices v₁ and v_t. Without loss of generality, let the vertex sequence be v₁ = v_i1v_i2…v_it = v_t, which satisfies the following constraint:

here, we give the algorithm for ordering vertices. Let v be a vertex of graph G. We start by defining the set of v-rooted paths, denoted by P(v), then define all the paths starting with the vertex v in G. The set of v-rooted paths P(v) in G can be determined as follows: First, the neighborhood of v is determined; next, the neighborhood of each vertex in Γ(v) that is represented as Γ²(v) without v is obtained. Thus, Γ³(v), Γ⁴(v), etc. are obtained by the same method above, which is called a pruning algorithm. Because the number of vertices in each subgraph is less than 20, this algorithm can be implemented easily.

Suppose that G₁ with V(G) = {v₁, v₂, …, v_t} is a subgraph, where v₁ and v_t are the bridge vertices. We now give the algorithm for ordering the vertices of the subgraph G₁:

Step 1: Determine on the rooted paths P(v₁) and P(v_t). If the v₁-rooted paths P(v₁) contain a Hamiltonian path of subgraph G₁, then order the vertices according to the Hamiltonian path. Otherwise, order the vertices according to the following steps.

Step 2: If P(v₁) ∪ P(v_t) = V(G₁), then we consider path P₁ in P(v₁) and path P₂ in P(v_t), respectively, where P₁ and P_t satisfy the following conditions: ① P₁ = v₁v_i2…v_ir and P_t = v_isv_i(s+1)…v_t; ② max{|E(P₁)| + |E(P_t)|}; and ③ V(P_1)\cap V(P_2)=\varnothing.

Step 3: If V^{\prime }=V(G_1)-P(v_1)\cup P(v_t)=\varnothing, then we further find the longest path from the induced subgraph G[V^{\prime }] and represent it as P^{\prime }=u_1{u}_2\dots u_m. If V^{″}=V(G_1)-V(P_1)-V(P_t)-V^{\prime }=\varnothing, then the ordering of vertices for the subgraph G₁ is v₁v_i2v_i3…v_iru₁u₂…u_mv_isv_i(s+1)…v_t. Otherwise, if V^{″}=V(G_1)-V(P_1)-V(P_t)-V^{\prime }=\{u_{i1}\text{,}{u}_{i2}\text{,}\dots \text{,}{u}_{iq}\}\ne \varnothing, then the ordering of vertices for the subgraph G₁ is v₁v_i2v_i3…v_iru₁u₂…u_mu_i1u_i2…u_iqv_isv_i(s+1)…v_t.

Consider subgraph G_3^{\prime } with the bridge vertices 1 and 13 as an example (Fig. 3). The path 1-10-11-2 is picked out from P(1), and the matched path 13-14-7-8-15-3-9-4 is also obtained from P(13). Then the path 5-6 is found in the remaining vertices. Finally, V^{″}=\left\{12\right\}. A vertex sequence of G_3^{\prime } and the edges incident to the vertices are shown in Fig. 5(a). A similar vertex sequence of G_3^{\prime } is shown in Fig. 5(b).

The ordering vertices 1-2-…-16 in G_1 in Fig. 4 are the best order because P₁ = 1-2-…-16. P₁ = 1-2-…-16 is a Hamiltonian path of G_1, and 1 and 16 are the bridge vertices in G_1. Another ordering of the vertices in G_1 is 1-3-5-7-9-11-13-15-2-4-6-8-10-12-14-16, which has only five edges ({5,7}, {9,11}, {13,15}, {15,2}, and {6,8}).

Step 4: Relabel the vertices in the subgraphs. Let the vertex sequence be v₁v₂…v_t before labeling, and v_σ(1)v_σ(2)…v_σ(t) after reordering. Obviously, the latter vertex ordering is obtained by the permutation of the vertex subscript:

For example, for the vertex ordering of subgraph G_3^{\prime } in Fig. 5, the mapping of the reordered vertices can be shown as follows:

In general, the vertices of a subgraph should be relabeled after ordering, and the vertex σ(i) will be relabeled by i, where i = 1, 2, …, t.

The chromatic number k in this article is 3, and the color set C(3) = {red, yellow, blue} = {r, y, b}. The variables r_i, y_i, and b_i indicate that the color of v_i can be chosen as red, yellow, or blue.

Considering subgraph G_1, where V(G₁) = {v₁, v₂, …, v_t}, the vertices v_1 and v_t are the bridge vertices in G_1. In our model, the bridge vertices are always adjacent, so vertices v_1 and v_t can be colored red (r_1) and blue (b_t) in advance. (It should be noted that vertex v_t can be colored red or yellow, of course, when it is not adjacent with a vertex colored blue. The true solutions with r_t or y_tcan be obtained by color permutation according to the coloring with b_t.) The vertices belonging to the set Γ(v₁) will be blue or yellow, and those belonging to Γ(v_t) will be red or yellow. The color sets of the vertices of the four subgraphs in Fig. 4 are shown in Fig. 6.

This method can be generalized to any situation where k > 3. If a graph G can be colored by k (k ≥ χ(G)) colors, then the color set is denoted by C_k(G), which can be defined as C₃(G) = {c₁, c₂, …, c_k}. Then the k-coloring problem of a given graph G can be solved if we find a map f: V(G) → C₃(G) with the property that ∀uv ∈ E(G), f(u) ≠ f(v). The other steps are completely the same as for the situation where k = 3.

This method greatly reduces the complexity of the initial solution space. The relevant formula and the analysis are given in Sections 3.2 Subgraph division and bridge vertices determination, 5.2 Complexity analysis of decreasing the initial solution space, respectively.

As DNA molecules work through specific hybridization in the computing process, encoding in DNA computing will be constrained by many factors such as the Gibbs free energy of chemistry, melting temperature, similarity of DNA sequences, length of DNA sequences, experimental environment, scale of problems, and so forth. Therefore, encoding is a very complicated and difficult problem in DNA computing, and is considered to be an NP-complete problem by several scholars. Many algorithms of DNA encoding based on various constraints have been formulated thus far. To provide good DNA strands for both specific hybridization and PCR in this article, the DNA strands are designed based on the following constraints:

•All sequences have no occurrence of five or more consecutive identical bases;

•The GC content of all sequences is 40%-60%;

•There are no more than eight of the same bases between any two sequences;

•There are no more than four matched bases in every sequence;

•For every sequence, five consecutive bases in both the 3^{\prime } and 5^{\prime } ends are mismatched with any five bases in other sequences;

•The absolute value of the change in the Gibbs free energy of chemistry (|\text{Δ}G|) of the primer dimer formed by its own sequence is no more than 6.0 kcal·mol⁻¹ (1 cal = 4.1868 J); and

•The absolute value of the change in the Gibbs free energy of chemistry (|\text{Δ}G|) of the primer dimer is no more than 9.0 kcal·mol⁻¹, and the absolute value of the change in the Gibbs free energy of chemistry (|\text{Δ}G|) of the primer dimer formed at the 3^{\prime } end is no more than 6.0 kcal·mol⁻¹.

Based on these constraints, the method described in Ref. [27] was used to design the DNA strands; next, the proper sequence was selected using the software Primer Premier 5.0.

It is easy to prove the following theorem.

Theorem 3.1: Let G be a 3-coloring graph with bridge vertices v₁ and v_n. According to the possible color set of each vertex, it can be determined that the number of DNA sequences representing vertex colors for any 3-coloring graph with n vertices is

In this article, 129 oligonucleotides (Table 1) were designed to represent the possible colors of the vertices in graph G. These oligonucleotides and their Watson-Crick complementary sequence were denoted by x_i and \stackrel{-}{x_i}, where i = 1, 2, …, 61, respectively.

The advantages of DNA computing are its huge parallelism and its great capacity for information storage. Over decades of research, it has been recognized that the biological activity in artificial DNA molecules is the main feature of the DNA computer. In particular, the gravitation between hydrogen bonds dominates the process. By making use of this feature, most of the false solutions can be eliminated from the initial solution space. This eliminating process cannot be carried out by electronic computers. To implement this idea, the method of designing hybridization probes plays a significant role in deleting false solutions.

In this model, the method of designing probes is described as follows (with chromatic number k = 3 as an example):

Step 1: Determine the color sets of each vertex. Let V(G) = {v₁, v₂, …, v_n}. Without loss of generality, let its ordering of vertices be v₁v₂…v_n. The set of possible colors for each vertex v_i is denoted by C_{v_i}, where i = 1, 2, …, n.

Step 2: Determine the set of probes. The probes are used to constitute the initial solution space. Probes are only set up between two consecutive labeled vertices v_i and v_{i+1}, denoted by \stackrel{-}{x_i{x}_{i+1}}, where x_i\in C_{v_i}, x_{i+1}\in C_{v_{i+1}}, and i = 1, 2, …, n − 1. If \exists e=v_i{v}_{i+1}\in E(G), then x_i and x_{i+1} cannot have the same color, and vice versa. For example, C_{v_7}=\left\{r_7\text{,}{y}_7\right\}, C_{v_8}=\left\{r_8\text{,}{y}_8\right\}, and e=v_7{v}_8\in E(G_1) exist in subgraph G_1(see Fig. 4), so only two probes ( \stackrel{-}{r_7{y}_8}, \stackrel{-}{y_7{r}_8}) are constructed.

Step 3: Determine the DNA sequence for each probe. The probes \stackrel{-}{x_i{x}_{i+1}} consist of the last half of the DNA sequence of x_i and the first half of the DNA sequence of x_{i+1}. In this article, the length of the probe is 20 bases. For example, if $y_7$=5′-AATACGCACTCATCACATCG-3′ and $r_8$=5′-GACCTTACCGTTTAGAGTCG-3′, then \stackrel{-}{y_7{r}_8}=5^{\prime }\text{-CGGTAAGGTCCGATGTGATG}-3^{\prime }.

To explain probe sets clearly, we utilize the graph theory method. This method is very useful for reducing initial solution space and theoretical analysis.

The probe graph of a graph G with n vertices, denoted by B(G) (abbreviated as B), is defined as follows:

According to the definition of probes and Fig. 6, the 3-coloring probe graphs of four subgraphs (see Fig. 4) are shown as B_1, B_2, B_3, and B_4 in Fig. 7. It is easy to identify information on probe numbers and distribution from each probe graph.

The method presented by Adleman [2] is used to construct the initial solution space of each deduced subgraph. The DNA sequences representing the possible solutions in the initial solution space are amplified in a series of operations:

•First, the 5′-ends of DNA sequences x_i are phosphorylated by T4 polynucleotide kinase (PNK);

•Second, the product of phosphorylation and probes are mixed in 10 × T4 PNK buffer for annealing;

•Third, the annealed products are ligated by T4 DNA ligase in 10 × T4 DNA ligase buffer; and

•Finally, the ligated products are amplified by PCR with the primer pair 〈r_1\text{,}{\stackrel{-}{x}}_t〉. The amplified DNA strands represent all possible solutions of each subgraph.

In this article, the initial solution space of subgraph G_j is denoted by S(G_j), where j = 1, 2, …, m, and m is the number of subgraphs. Let t = |G_j| and V(G) = {v₁, v₂, …, v_t}. Then S(G_j) = {x₁x₂…x_t}, where x_i ∈ C_{v_j}\subset \left\{r\text{,}b\text{,}y\right\}, and i = 1, 2, …, t. If each x_i has l bases, then the length of the DNA sequence in the initial solution space will be t × l.

It should be noted that if e = v_iv_i+1 ∈ E(G), then x_i and x_i+1 cannot share the same color when constructing the probes. In this way, the false solutions in which adjacent vertices have the same color will be deleted when constructing the initial solution space. Thus, the more edges e = {v_i, v_i+1} there are, the more false solutions will be deleted in the initial solution space. The details of the theoretical analysis will be shown in Section 5.2.

In this section, the methods of deleting the false solutions of each subgraph are described. Let E_j¹ = {v_iv_i+1 ∈ E(G), v_iv_t ∈ E(G_j); i = 1, 2, …, t − 1}, and E_j² = {v₁v_i ∈ E(G_j), i = 2, 3, …, t}. Then E_j³ = E(G_j) − E_j¹ − E_j² and j = 1, 2, …, m.

In fact, the process of deleting false solutions involves eliminating DNA strands that represent the improper coloring of the vertices incident to the edges in E_j³ from the initial solution space S(G_j). In the process of bio-operation, PCR is used to delete false solutions. To improve the processing speed, the edges in E_j³ are divided into two groups and each group is operated using different procedures.

(1) Forward Path. In our experiment, a false solution is deleted by a so-called parallel PCR operation on the forward paths. Here, we introduce a definition of forward path.

Let G_1 be a subgraph with V(G₁) = {v₁, v₂, …, v_t}, and let v_1{v}_2\dots v_t be a vertex ordering of G_1 according to the method shown in Section 3.3. For \forall e=v_i{v}_j\in E(G_1), if i<j, then e=v_i{v}_jis a forward edge; otherwise, it is a backward edge. If all the edges in a path are forward edges, then the path is a forward path; otherwise, it is a backward path.

Now, for example, we take a path P=v_i{v}_j{v}_y{v}_z, 1<i<j<y<z<t (other paths are treated in the same way). In this path, there are three edges: v_i{v}_j, v_j{v}_y, and v_y{v}_z. First, PCR is done with primer pairs:x 〈x_1\text{,}\stackrel{-}{x_i}〉., 〈x_i\text{,}\stackrel{-}{x_j}〉, 〈x_j\text{,}\stackrel{-}{x_y}〉, 〈x_y\text{,}\stackrel{-}{x_z}〉, and 〈x_z\text{,}\stackrel{-}{x_t}〉, where x_i and x_j, x_j and x_y, and x_y and x_z should not have the same color at the same time. In this way, the DNA strands are separated into five fragments. Subsequently, these small fragments will be combined gradually to generate DNA strands with t\times l base pairs (bp). Thus, at the end of PCR operations, the DNA strands representing the improper coloring of these vertices incident to the three edges will be eliminated from S(G_j). Detailed experimental methods and the theoretical analysis are given in Sections 4.4 Deleting false solutions of the subgraph, 5.3 Reducing operation complexity by parallel PCR technology, respectively.

(2) Single edge. Some single edges exist in E_j^3 after deleting all false solutions from forward paths. Let e=v_i{v}_j, x_i\in C_{v_i}, and x_j\in C_{v_j}. PCR is run with primer pairs 〈x_1\text{,}\stackrel{-}{x_i}〉, 〈x_i\text{,}\stackrel{-}{x_j}〉, and 〈x_j\text{,}\stackrel{-}{x_t}〉. Here, x_i and x_j should not have the same color. In this way, the DNA strands representing improper coloring of the vertices incident to the edge are not amplified. That is, the DNA strands representing false solutions are eliminated. When the DNA strands representing improper coloring of the vertices incident to the edges in E_j^3 are all deleted, the amplified DNA strands in S(G_j) represent the colorings of subgraph G_j, where j = 1, 2, …, m.

After obtaining the true solutions of each subgraph, these subgraphs are combined to generate secondary subgraphs. Then the process of deleting false solutions continues. This process involves the following three steps:

Step 1: Combine subgraphs G_j and G_{j+1}, where j = 1, 2, …, m − 1. The DNA strands representing the improper colors of the subgraphs will be linked together to generate new DNA strands by the DNA sequence of the bridge vertices. These new DNA strands will be processed as the initial solution space of the secondary graph G[V(G_j)\cup V(G_{j+1})]. If |V(G_j)|=t_1 and |V(G_{j+1})|=t_2, then the length of the DNA strands generated is (t_1+t_2-1)\times l.

Step 2: Delete the false solutions of secondary graph G[V(G_j)\cup V(G_{j+1})] according to the method described in Section 3.7. That is, the DNA strands representing the color of the vertices incident to the edge in E_{j\text{,}j+1}=\{uv\in E(G)\text{;}u\in V(G_j)\text{,}v\in V(G_{j+1})\} will be amplified, but the false solutions will be eliminated.

Step 3: Repeat Steps 1 and 2 for the secondary and new combined subgraphs until the original graph is completely reshaped. Thus, the DNA strands representing the true solutions of G will be obtained.

The DNA strands representing the true solutions are sequenced and analyzed by Gene Tools to obtain the proper coloring of the graph.

To implement this DNA computing model, consider the graph with 61 vertices shown in Fig. 1 as an example. The scale of this problem is the largest to be solved by DNA computing. The protocol of the assay is given in this section. The result illustrates that the computational capability of the DNA computing model proposed here is as high as O(3⁵⁹).

According to the methods demonstrated in Section 3.2, graph G (Fig. 1) can be divided into four subgraphs (Fig. 4); the color set of each vertex is shown in Fig. 6.

According to the methods in Section 3.5, 129 oligonucleotides (Table 1) were designed to represent the possible colors of all vertices, and 185 probes were constructed according to the probe graph (Fig. 7).

These probes are: $\overline{r_1 y_2}$, $\overline{r_1 b_2}$; $\overline{y_2 r_3}$, $\overline{b_2 r_3}$, $\overline{b_2 y_3}$; $\overline{r_3 y_4}$, $\overline{y_3 r_4}$; $\overline{r_4 y_5}$, $\overline{r_4 b_5}$, $\overline{y_4 b_5}$; $\overline{y_5 b_6}$, $\overline{b_5 y_6}$; $\overline{y_6 r_7}$, $\overline{b_6 r_7}$, $\overline{b_6 y_7}$; $\overline{r_7 y_8}$, $\overline{y_7 r_8}$; $\overline{r_8 y_9}$, $\overline{r_8 b_9}$, $\overline{y_8 r_9}$, $\overline{y_8 b_9}$; $\overline{r_9 y_10}$, $\overline{r_9 b_10}$, $\overline{y_9 r_10}$, $\overline{y_9 b_10}$, $\overline{b_9 r_10}$, $\overline{b_9 y_10}$; $\overline{r_10 y_11}$, $\overline{y_10 r_11}$, $\overline{b_10 r_11}$, $\overline{b_10 y_11}$; $\overline{r_11 y_12}$, $\overline{y_11 r_12}$; $\overline{r_12 y_13}$, $\overline{r_12 b_13}$, $\overline{y_12 r_13}$, $\overline{y_12 b_13}$; $\overline{r_13 y_14}$, $\overline{r_13 b_14}$, $\overline{y_13 b_14}$, $\overline{b_13 y_14}$; $\overline{y_14 r_15}$, $\overline{b_14 r_15}$, $\overline{b_14 y_15}$; $\overline{r_15 b_16}$, $\overline{y_15 b_16}$; $\overline{b_16 r_17}$, $\overline{b_16 y_17}$; $\overline{r_17 y_18}$, $\overline{r_17 b_18}$, $\overline{y_17 b_18}$; $\overline{y_18 b_19}$, $\overline{b_18 y_19}$; $\overline{y_19 r_20}$, $\overline{b_19 r_20}$, $\overline{b_19 y_20}$; $\overline{r_20 y_21}$, $\overline{r_20 b_21}$, $\overline{y_20 r_21}$, $\overline{y_20 b_21}$; $\overline{r_21 y_22}$, $\overline{y_21 r_22}$, $\overline{b_21 r_22}$, $\overline{b_21 y_22}$; $\overline{r_22 y_23}$, $\overline{y_22 r_23}$; $\overline{r_23 y_24}$, $\overline{r_23 b_24}$, $\overline{y_23 b_24}$; $\overline{y_24 b_25}$, $\overline{b_24 y_25}$; $\overline{y_25 r_26}$, $\overline{b_25 r_26}$, $\overline{b_25 y_26}$; $\overline{r_26 y_27}$, $\overline{y_26 r_27}$; $\overline{r_27 y_28}$, $\overline{r_27 b_28}$, $\overline{y_27 b_28}$; $\overline{y_28 r_29}$, $\overline{y_28 b_29}$, $\overline{b_28 r_29}$, $\overline{b_28 y_29}$; $\overline{r_29 y_30}$, $\overline{r_29 b_30}$, $\overline{y_29 b_30}$, $\overline{b_29 y_30}$; $\overline{y_30 r_31}$, $\overline{b_30 r_31}$; $\overline{r_31 y_32}$, $\overline{r_31 b_32}$; $\overline{y_32 r_33}$, $\overline{y_32 b_33}$, $\overline{b_32 r_33}$, $\overline{b_32 y_33}$; $\overline{r_33 y_34}$, $\overline{y_33 r_34}$, $\overline{b_33 r_34}$, $\overline{b_33 y_34}$; $\overline{r_34 y_35}$, $\overline{r_34 b_35}$, $\overline{y_34 b_35}$; $\overline{y_35 r_36}$, $\overline{y_35 b_36}$, $\overline{b_35 r_36}$, $\overline{b_35 y_36}$; $\overline{r_36 y_37}$, $\overline{y_36 r_37}$, $\overline{b_36 r_37}$, $\overline{b_36 y_37}$; $\overline{r_37 y_38}$, $\overline{r_37 b_38}$, $\overline{y_37 r_38}$, $\overline{y_37 b_38}$; $\overline{r_38 y_39}$, $\overline{r_38 b_39}$, $\overline{y_38 b_39}$, $\overline{b_38 y_39}$; $\overline{y_39 r_40}$, $\overline{y_39 b_40}$, $\overline{b_39 r_40}$, $\overline{b_39 y_40}$; $\overline{r_40 y_41}$, $\overline{y_40 r_41}$, $\overline{b_40 r_41}$, $\overline{b_40 y_41}$; $\overline{r_41 y_42}$, $\overline{y_41 r_42}$; $\overline{r_42 y_43}$, $\overline{r_42 b_43}$, $\overline{y_42 b_43}$; $\overline{y_43 r_44}$, $\overline{y_43 b_44}$, $\overline{b_43 r_44}$, $\overline{b_43 y_44}$; $\overline{r_44 y_45}$, $\overline{y_44 r_45}$, $\overline{b_44 r_45}$, $\overline{b_44 y_45}$; $\overline{r_45 b_46}$, $\overline{y_45 b_46}$; $\overline{b_46 r_47}$, $\overline{b_46 y_47}$; $\overline{r_47 b_48}$, $\overline{y_47 r_48}$, $\overline{y_47 b_48}$; $\overline{r_48 y_49}$, $\overline{b_48 r_49}$, $\overline{b_48 y_49}$; $\overline{r_49 y_50}$, $\overline{y_49 r_50}$; $\overline{r_50 y_51}$, $\overline{r_50 b_51}$, $\overline{y_50 r_51}$, $\overline{y_50 b_51}$; $\overline{r_51 y_52}$, $\overline{y_51 r_52}$, $\overline{b_51 r_52}$, $\overline{b_51 y_52}$; $\overline{r_52 y_53}$, $\overline{r_52 b_53}$, $\overline{y_52 r_53}$, $\overline{y_52 b_53}$; $\overline{r_53 b_54}$, $\overline{y_53 r_54}$, $\overline{y_53 b_54}$, $\overline{b_53 r_54}$; $\overline{r_54 y_55}$, $\overline{b_54 r_55}$, $\overline{b_54 y_55}$; $\overline{r_55 y_56}$, $\overline{y_55 r_56}$; $\overline{r_56 b_57}$, $\overline{y_56 r_57}$, $\overline{y_56 b_57}$; $\overline{r_57 b_58}$, $\overline{b_57 r_58}$; $\overline{r_58 y_59}$, $\overline{b_58 r_59}$, $\overline{b_58 y_59}$; $\overline{r_59 b_60}$, $\overline{y_59 r_60}$, $\overline{y_59 b_60}$; and $\overline{r_60 y_61}$, $\overline{b_60 y_61}$.

All the oligonucleotides used in this article were synthesized by Sangon Biotech (Shanghai) Co., Ltd.

Here, we use the subgraph G₁ as an example to show how to construct the initial solution space; the result is shown in Fig. 8(a). The steps and reaction systems were as follows:

Step 1: Phosphorylation. DNA sequences x_i, where v_i\in V(G_1), x_i\in C_v, and i=1\text{,}2\text{,}\dots \text{,}16, were phosphorylated at the 5′ end by T4 PNK. In a sterile 0.2 mL amplification tube, the phosphonated reaction components were: 16.5 μL of oligonucleotide (0.5 μL for each x_i; v_i\in V(G_1), x_i\in C_v, i=1\text{,}2\text{,}\dots \text{,}16), 3 μL of T4 PNK, 3 μL of buffer forT4 PNK, 5 μL of adenosine triphosphate (ATP) (10 mmol·L⁻¹), and 2.5 μL of double-distilled water. The total volume of the mixture was 30 μL. The mixture was incubated at 37 °C for an hour.

Step 2: Annealing. In a sterile 0.2 mL amplification tube, the annealing reaction components were: 30 μL of the phosphorylated product, 23 μL of probes (0.5 μL for each probe), 3 μL of buffer for T4 PNK, and 4 μL of double-distilled water for a total volume of 60 μL. The mixture was incubated at 94 °C for 5 min and at 50 °C for 10 min, and was then slowly cooled to room temperature.

Step 3: Ligation. In a sterile 0.2 mL amplification tube, the ligation reaction components were: 6 μL of the annealing product, 2 μL of T4 DNA ligase, and 2 μL of buffer for T4 DNA ligase. The total volume of the mixture was 10 μL. The mixture was incubated at 16 °C overnight.

Step 4: PCR amplification. The ligation product was amplified by the primer pairs 〈r_1\text{,}\stackrel{-}{b_{16}}〉. In a sterile 0.2 mL amplification tube, the PCR reaction components were: 1 μL of the template, 2 μL of the primer pairs (1 μL of each), 4 μL of dNTP Mix (2.5 mmol·L⁻¹ for each), 0.5 μL of the Taq polymerase, and 5 μL of the buffer for the Taq polymerase, in a total volume of 30 μL. The reaction conditions were: 94 °C for 5 min; then 94 °C for 30 s, 54 °C for 30 s, and 72 °C for 45 s for 35 cycles; then 72 °C for 10 min.

After PCR, 4% agarose gel electrophoresis was used to display the products, and the 320 bp bands were cut and purified with a Gel Extraction Kit (U-gene) in a final volume of 50 μL. The DNA strands representing the possible solutions of subgraph G_1 were denoted by S(G_1), where S(G₁) = {x₁x₂…x₁₆}.

These steps were also used to construct the initial solution space of G_2, G_3, and G_4; the results are shown in Fig. 8(b-d). These results were denoted by S(G_2),, S(G3), a, and S(G_4), respectively, where S(G₂) = {x₁₆x₁₇…x₃₁}, S(G₃) = {x₃₁x₃₂…x₄₆}, and S(G₄) = {x₄₆x₄₇…x₆₁}, with x_i\in C_{v_i} and v_i\in V(G).

PCR was also used to test the completeness of each initial solution space of each subgraph. Taking S(G_1) as an example, a 50-fold dilution of the initial solution space S(G_1) was amplified with primer pairs: 〈x_1\text{,}\stackrel{-}{x_i}〉, where i=1,2,…,16. These products are shown in Fig. 8(e,f).

In this section, we describe how to delete false solutions of the subgraph. PCR is also used to delete false solutions. According to the different walks, PCR operations were classified into three basic types:

The first type was designed for the walk or circle, and parallel PCR was applied to find the true solutions. We give the steps using a path P = 16-20-22-26-30 of subgraph G_2 as an example.

First, the 50-fold dilutions of S(G_2) were amplified by different primer pairs: $＜b_16, \overline{r_20}＞$, $＜b_16, \overline{y_20}＞$, $＜r_20, \overline{y_22}＞$, $＜y_20, \overline{r_22}＞$, $＜r_22, \overline{y_26}＞$, $＜y_22, \overline{r_26}＞$, $＜r_26, \overline{y_30}＞$, $＜r_26, \overline{b_30}＞$, $＜y_26, \overline{b_30}＞$, $＜y_30, \overline{r_31}＞$, and $＜b_30, \overline{r_31}＞$. After PCR, five different DNA segments with different lengths were obtained. The DNA segments of 100 bp ($＜b_16, \overline{x_20}＞$), 60 bp ($＜x_20, \overline{x_22}＞$), 100 bp ($＜x_22, \overline{x_26}＞$), 100 bp ($＜x_26, \overline{x_30}＞$), and 40 bp ($＜x_30, \overline{x_31}＞$) are shown in Fig. 9(a) and (b), where $\chi_i \in C_{v_i}$, i = 16, 17, …, 31. Lane 5 in Fig. 9(a) shows no product with the primer pair $＜r_22, \overline{y_26}＞$, which means that there is no DNA strand with $r_{22}$ and $y_{26}$ in the initial solution space. This is the first PCR.

Next, the second PCR was run using different templates and different primer pairs, and the five DNA segments were combined to form three segments. Here T_i (i = 1, 2, 3) is used to represent the different templates. T₁ represents the mixtures of PCR products from Lanes 1 and 3 in Fig. 9, T₂ represents the mixtures from Lanes 1 and 4 in Fig. 9(b) as the template, and T₃ represents the mixtures from Lanes 2 and 5 in Fig. 9(b). With the primer pairs $＜b_16, \overline{y_22}＞$, $＜r_26, \overline{r_31}＞$, and $＜r_26, \overline{r_31}＞$, three segments with 140 bp, 120 bp, and 120 bp, respectively, were acquired. The results are shown in Fig. 9(c).

Subsequently, the third PCR was run, and a 220 bp band was acquired with the primer pair $＜b_16, \overline{r_26}＞$ by using the mixtures of PCR products from Lane 6 in Fig. 9(a) and Lane 1 in Fig. 9(c). The result is shown in Fig. 9(d).

Finally, the mixtures from Lane 1 in Fig. 9(d) and Lane 2 in Fig. 9(c) and the mixtures from Lane 1 in Fig. 9(d) and Lane 3 in Fig. 9(c) were amplified separately by primer pair $＜b_16, \overline{r_31}＞$, and two different 320 bp bands were acquired (see Fig. 9(e)). Thus, at the end of the PCR operations, two sets consisting of 320 bp DNA sequences were obtained. In these sets, the coloring of vertices 20, 22, 26, and 30 were ascertained as follows: b_{16}{r}_{20}{y}_{22}{r}_{26}{y}_{30}{r}_{31} and b_{16}{r}_{20}{y}_{22}{r}_{26}{b}_{30}{r}_{31}. These steps are shown in Fig. 9(f).

The second type was designed for the single edge whose two end vertices colors were undetermined. Here, we take e=\left\{4\text{,}8\right\} in subgraph G_1 as an example.

At first, the PCR products of the third cycle of subgraph G_1 were amplified by the primer pairs $＜r_1, \overline{r_4}＞$, $＜r_4, \overline{y_8}＞$, $＜y_8, \overline{b_16}＞$, $＜r_1, \overline{y_4}＞$, $＜y_4, \overline{r_8}＞$, and $＜r_8, \overline{b_16}＞$, and the 320 bp full-length DNA strands were divided into sequences of 80 bp ($＜r_1, \overline{x_4}＞$), 100 bp ($＜x_4, \overline{x_8}＞$), and 180 bp ($＜x_8, \overline{b_16}＞$), respectively, where ($x_{i}=C_{v_{i}}$,i=1,2,…,16). The results are shown in Fig. 10(a); there is no product for $＜y_4, \overline{r_8}＞$.

Next, PCR was run with primer pair $＜r_1, \overline{y_8}＞$, using the mixtures of PCR products from Lanes 1 and 3 in Fig. 10(a) as a template, and a 160 bp band was acquired (see Fig. 10(b)).

At last, the mixtures of PCR products from Lane 5 in Fig. 10(a) and Lane 1 in Fig. 10(b) were amplified by primer pair $＜r_1, \overline{b_16}＞$, and a 320 bp band was acquired. To test the color of v₄ and v₈, the 320 bp band was amplified by primer pairs $＜r_1, \overline{r_8}＞$, $＜r_4, \overline{r_8}＞$, $＜y_4, \overline{r_8}＞$, and $＜y_4, \overline{y_8}＞$, respectively. No product was obtained. Thus, the colors of vertices 4 and 8 were determined as $r_4$ and $y_8$.

The third type was designed to check the edges whose two end vertices colors had been determined. Here, e=\left\{39\text{,}42\right\}was used to illustrate the operation.

After finishing all PCRs of C = 34-38-42-46-34 and the first PCR of C = 34-38-42-46-34 of subgraph G_3, there were a total of six solutions (marked as (1) to (6) in Fig. 11), and the color of v₃₉ and v₄₂ could be determined as b_{39}, y_{39}, r_{42}, and y_{42}. In these cases, only the DNA strands with y₃₉ and y₄₂ are false solutions. To delete the false solutions, these six solutions were amplified by primer pair $＜y_39, \overline{y_42}＞$ separately; only the false solutions would produce 80 bp bands after PCR. The results are shown in Fig. 11(a), and the principle is shown in Fig. 11(b).

To find the solutions of graph G, the solution spaces of the subgraphs must be combined, and then the false solutions must be deleted according to the operations described in Section 4.4.

First, the solution spaces mixtures of subgraphs G_1 and G_2 were amplified by primer pair $＜r_1, \overline{r_31}＞$. The PCR results were DNA strands with a 620 bp band, which represented all possible three-colorings of G[V_1\cup V_2]. Meanwhile, false solutions might also exist in this space, because there were five edges connecting G_1 and G_2. After deleting the false solutions, four true solutions of G[V_1\cup V_2] (X₁-X₄) were obtained (shown below). The results are shown in Fig. 12(a) and (b).

Similarly, the solution spaces mixtures of subgraphs G₃ and G₄ were amplified by primer pair $＜r_31, \overline{y_61}＞$ to obtain the possible solutions of G[V_3\cup V_4]. After deleting the false solutions, six true solutions Y₁-Y₆ remained (shown below). The results are shown in Fig. 12(c)-(e).

Finally, the solution space of subgraphs G[V_1\cup V_2] and G[V_3\cup V_4] were combined by primer pair $＜r_1, \overline{y_61}＞$. This primer pair only resulted in a band corresponding to 1220 bp. After deleting false solutions, eight true solutions Z₁-Z₈ were obtained (shown below). The results are shown in Fig. 13.

All eight solutions Z₁-Z₈ were purified and sequenced by Beijing AuGCT Biology Company. The sequences were analyzed by Gene Tools and improved to be the true solutions of graph G.

In this section, we analyze the complexity of this DNA computing model in two aspects: the complexity of the initial solution space and the complexity of the experiments. We provide a calculation formula to estimate the amount of initial solution space for typical and for worst cases.

To illustrate the complexity of the initial solution space, we first introduce a formula, which can be used to calculate the number of the walks between any two vertices.

Lemma 5.1 [28]: Let G be a graph with n vertices and V(G) = {v₁, v₂, …, v_n}. A is the adjacent matrix of G. The number of walks of length l in G, from v_i to v_j, is the entry in position (i, j) of the matrix A^l.

In previous DNA computing models for solving NP-complete problems, a large number of DNA molecules were frequently used to encode and enumerate an infinite amount of data. However, those models rarely considered decreasing false solutions by constructing the initial solution space; rather, they used the enumerating method. In fact, this enumerating idea does not work for large-scale problems for two reasons. First, with an increase of problem scale, the number of DNA molecules becomes too large to obtain. Second, even if the number of DNA molecules can be designed, the experiments will be too difficult to implement due to the larger size and greater number of molecules. Thus, it is necessary to find more efficient methods to decrease the initial solution space when designing a DNA computing model to solve NP problems. In this article, we designed a DNA computing model for the coloring problem by using an optimization idea to construct an initial solution space, rather than by enumerating.

Theorem 5.2: Suppose that G is a graph with |V(G)| = n and G₁ is its subgraph, as proposed by Section 3.2, where V(G) = {v₁, v₂, …, v_n}, with the bridge vertices v₁ and v_t. Let B(G₁) be the probe graph of G₁. Then the number of DNA sequences representing all possible coloring solutions in the initial solution space to G₁ is equal to the number of paths connecting the bridge vertices v₁ and v_t with length t − 1 in B(G₁), denoted by N_p(v₁, v_t), which is given by the following formula:

Proof: The vertex x_i in 99.9997% represents a coloring of the vertex v_i in G_1 by the definition of B(G_1). The edge \left\{x_i\text{,}{z}_{i+1}\right\}\in B(G_1) represents the probe between x_i and z_{i+1}. That is, when the color of v_i is x, the color of v_{i+1} can be chosen as z, where x\text{,}z\in \left\{r\text{,}y\text{,}b\right\}. Consequently, each path from vertex r_1 to vertex b_t denotes one possible coloring of subgraph G_1. Furthermore, all the paths between r_1 and b_t in B(G_1) represent all the possible solutions of the initial solution space.

Considering the structure of the probe graph B(G_1), we divide V(B(G_1)) into v_t parts, where the vertex with subscript i is the ith part. It is concluded that there must at least exist an edge connecting the ith part and the (i + 1)th part by the definition of a probe graph. Thus, the length of the paths between r_1 and b_t in B(G_1) is only t-1. And each walk from r_1 to b_t is just the path between r_1and b_t. Thus, the theorem is proved by Lemma 5.1. □

Corollary 5.3: The number of DNA strands in initial solution spaces S(G₁), S(G₂), S(G₃), and S(G₄) of the subgraphs G₁, G₂, G₃, and G₄ shown in Fig. 4 are 89, 81, 412, and 151, respectively. The corresponding percentage of DNA strands deleted in the enumerable initial solution spaces are 99.9998%, 99.9998%, 99.999%, and 99.9997%, respectively.

Proof: Notice that vertices v₁ and v₁₆ are the bridge vertices of subgraph G₁. Thus, the number of DNA strands in S(G₁) is N₃₃(r₁, b₁₆), which is the number of paths with length 15 from vertex r₁ to b₁₆ in B₁ (see Fig. 7) by Theorem 5.2.

The adjacent matrix A(B_1) of B_1 is

The correspondence between the vertices of A(B₁) and B₁ is

According to Lemma 5.1, we have A{(B_1)}^{15}(1\text{,}33)=89, and \frac{89}{43046721}\approx 0.000002=0.0002\%. The result shows that 99.9998% of the false solutions are deleted when constructing the initial solution space S(G_1).

Similarly, we have A{(B_2)}^{15}(1\text{,}32)=81, and \frac{81}{43046721}\approx 0.00000188=0.000188\% for subgraph G_2\text{;} A{(B_3)}^{15}(1\text{,}35)=412, and \frac{412}{43046721}\approx 0.0000096=0.00096\% for subgraph G_3; and A{(B_4)}^{15}(1\text{,}32)=151, and \frac{151}{43046721}\approx 0.0000035=0.00035\% for subgraph G_4, respectively. The results show that 99.9998%, 99.999%, and 99.9997% of the false solutions were deleted when constructing the initial solution spaces S(G_2),, S(G3), a, and S(G_4), respectively. □

In our experiment, false solutions are deleted by designed parallel PCR operation on the forward paths (see Section 3.7). In this way, the bio-operation times are greatly reduced. The bio-operation complexity is analyzed in this section.

Let P = v_i0v_i1…v_im with |V(P)|=m+1 be a forward path in subgraph G_1 with bridge vertices v_1 and v_t. Then we must consider the relationships between the two bridge vertices and path P = v_i0v_i1…v_im with three cases when we design corresponding parallel PCR operation:

Case 1: There are no bridge vertices in V(P). That is, v_{i0}\ne v_1 and v_{im}\ne v_t. For this case, we need to add the two bridge vertices so as to analyze the advantages of the parallel PCR operations (see Fig. 14(a)).

Case 2: There is one bridge vertex in V(P). That is, v_{i0}=v_1 but v_{im}\ne v_t, or v_{i0}\ne v_1 but v_{im}=v_t. For this case, we need to add the one bridge vertex v_1 or v_t(see Fig. 14(b)).

Case 3: There are two bridge vertices in V(P). That is, v_{i0}=v_1 and v_{im}=v_t. For this case, we need only to consider the ordering vertices in path P(see Fig. 14(c)).

Since the color of the bridge vertex v_1 (or v_t) is fixed in advance, its adjacent vertices in Cases 2 and 3 are taken as the other colors aside from the color of v_1(or v_t). Since there are three cases shown in Fig. 14, we will only discuses Case 1, because the other two cases can be treated as special cases of Case 1. Let P belongs to Case 1, then P^{\prime }=P-\left\{v_1\text{,}{v}_{i0}\right\} or r P′=P-{vim,vt} shoul should belongs to Case 2, and P^{″}=P-\left\{v_1\text{,}{v}_{i0}\right\}-\left\{v_{im}\text{,}{v}_t\right\} will be Case 3.

Next, let us discuss the parallel PCR method. First, we determine the number and sequence of the vertices for the forward path P = v_i0v_i1…v_im using the approach given in Fig. 14. Next, we perform the PCR operations. In practice, we do several times of PCR to fulfill one deleting false solutions operation. We found that the times of PCR operation are only relevant to the number of vertices or edges. Taking the first case above as an example, it is necessary to amplify the strands with the primer pairs 〈v_1\text{,}{v}_{i0}〉〉, 〈v_{i0}\text{,}{v}_{il}〉\text{,}\dots 〈v_{i(m-1)}\text{,}{v}_{im}〉, and 〈v_{im}\text{,}{v}_t〉 in the first PCR operation. The second PCR operation is designed to connect the consecutive two segments of the results of the previous PCR operation. The following PCR processes perform similar operations to the second PCR operation. In Fig. 15, we refer to cases with five vertices (a path with two edges) and six vertices (a path with three edges) as examples in order to illustrate the process of parallel PCR, where the edges mean how we do the PCR operation to connect the DNA segments to get a completed DNA sequence.

It is concluded from Fig. 15 that the number of PCR operation is 3 for the case of the path with two edges, and for the case of the path with six edges the number of PCR operation is 4. Thus, we have Theorem 5.4.

Theorem 5.4: Suppose that P is the forward path of a subgraph with x edges. If x satisfies --2^{l-1}--x⩽2^l--, we define 〈x〉=2^l. Let the number of PCR operation be represented as \text{PCR}(x). Then, it can be concluded that

Proof: First, we consider the case x + 2 = 2^l. Suppose that the number of edges in path P is x. That is, the number of vertices in path P is x + 1. We already analyze the three cases between the two bridge vertices in a forward path in Fig. 14, and Cases 2 and 3 are the special cased of Case 1. So without loss of generality, we focus our attention on Case 1.

Since there are no bridge vertices in path P, it is necessary to increase two bridge vertices according to the requirements of the PCR operations, such that the number of vertices increases to x + 3. Then, we obtain the following equation:

As a result, the number of primer pairs of the first PCR can be concluded as shown below:

Following the above operations, the primer pair number in the second PCR is 2^{l-1}. In general, the primer number in the lth PCR is concluded to be:

Thus, the PCR can be accomplished in the (l + 1)th time. In other words, the number of PCR operation required are l + 1 when x + 2 = 2^l. Then, we obtain the following mathematical relation:

Similarly, if x + 2 = 2^l+1, then the number of PCR operation satisfy the formula as follows:

Here, we demonstrate the case x + 2 = 2^l + 1:

As shown above, the number of vertices in path P is x + 3 by increasing two bridge vertices. Thus, when x + 2 = 2^l + 1, there are 2^l + 2 vertices. The number of primer pairs in the first PCR is 2^l + 1, as induced by the following formula: (x + 3) − 1 = x + 2 = 2^l + 1.

The number of primer pairs in the second PCR is then 2^l−1 + 1. Similarly, the number of primer pairs in the (l + 1)th PCR is 2. The (l + 2)th PCR can be completed.

On the other hand, we can obtain the number of the PCR operation as follows:

Thus, the conclusion above is verified when x+2=2^l+1.

For --2⩽y--2^l--, the number of PCR operation when x+2=2^l+y is more than that of the case x+2=2^{l+1}. The number of PCR operation for these two cases above is l+2. Thus, the conclusion holds when --2⩽y--2^l-- and x+2=2^l+y. Consequently, Theorem 5.4 is demonstrated. □

Theorem 5.4 fully shows the relations between the length x of forward path P and the number of the PCR operation. Of course, the number can be reduced by parallel PCR operations, which will greatly accelerate the computation speed. We can now see the advantages of parallel PCR operations, as shown in Table 2 and Fig. 16.

Corollary 5.5: Let P be the forward path in a graph G₁ with x edges. It can be induced by using Theorem 5.4 that

Proof: Let x + 2 = 2^l + y, where 1 ≤ y ≤ 2^l. Then, we have

In addition, since y is less than 2^l, then it is induced that 2^l+1 > y + 2^l. Consequently, the following consecutive inequalities hold:

That is, x satisfies the relation below:

Then, we obtain

On the basis of L’Hospital’s rule, we obtain

Therefore, the formula \underset{x\to \infty }{\lim }\frac{{\log }_2〈x+2〉+1}{3x}=0 is true. □

Since shortly after the discovery of the double helix structure of DNA, the idea of using DNA molecules to process information has been a dream, one that originated from Feynman’s concept of constructing submicroscopic computers [1]. This dream was ultimately fulfilled by Adleman in 1994, when he established a DNA computing model for a Hamiltonian graph with seven vertices. These works greatly contributed to the development of DNA computing.

The success of our DNA computing model not only demonstrates its huge computational capability, but also provides a seemingly feasible method to solve the exponential explosion problem, which may be the biggest bottleneck preventing DNA computing from solving larger-scale NP problems. In this paper, a graph vertex coloring problem with a computing complexity of O(3⁵⁹) is solved by using the advantages of the DNA computing model: the construction of an un-enumerating initial solution space, the division and combination of subgraphs, and parallel bio-operation.

By dividing subgraphs, reducing the vertex colors without losing solutions, and ordering the vertices in subgraphs, the exponential explosion problem is effectively avoided. According to Lemma 5.1, the initial solution space of each subgraph is 89, 81, 412, and 151, respectively, all of which are much lower than 3¹⁶ (the worst complexity). Therefore, the values of DNA sequences in the un-enumerating initial solution space are 99.9998%, 99.9998%, 99.999%, and 99.9997% lower than those in an enumerating initial solution space.

In this model, we also improve the computing efficiency by dividing the graph into four subgraphs and simultaneously deleting the false solutions of these subgraphs. After obtaining the solutions of each subgraph, the true solutions are found by combining the subgraphs. It is possible that the ability of this model to solve the graph vertex coloring problem will reach 100 vertices.

In this model, false solutions are deleted according to the path rather than the edge. Thus, all edges in one path are dealt with at the same time. In this way, the number of PCR operation required decreases. The efficiency of this DNA computing model is greatly improved by a significant innovation: the “parallel deleting method.”

In general, many researchers use PCR for amplification with only two primers and one template, because they think that PCR is not very reliable with many templates. However, in this model, we use PCR to amplify all templates in a test-tube. In order to obtain reliable results, the primer pairs are strictly designed according to the constraints of PCR, and the reaction conditions and the concentration of the components are optimized for each PCR. Only the bands representing the specific amplification are cut and purified for the next operation. In addition, contrast tests are implemented to avoid false positives and false negatives in the experiments. The sequencing shows that the results of the experiments are reliable. Because of its reliability and its ability to reduce the solution space, we assert that this DNA computing model can be used to solve larger-size problems, and that DNA molecular tools can be used to carry out larger-scale NP problems. In future, it may be possible to use DNA computing for certain practical engineering problems.

The authors are grateful for the support from the National Natural Science Foundation of China (61632002, 61379059, and 61572046).

Jin Xu, Xiaoli Qiang, Kai Zhang, Cheng Zhang, and Jing Yang declare that they have no conflict of interest or financial conflicts to disclose.