# A Parallel Bioinspired Algorithm for Chinese Postman Problem Based on Molecular Computing

Authors: Zhaocai Wang; Xiaoguang Bao; Tunhua Wu
Journal: Computational Intelligence and Neuroscience
 (2021)

---

## Abstract

The Chinese postman problem is a classic resource allocation and scheduling problem, which has been widely used in practice. As a classical nondeterministic polynomial problem, finding its efficient algorithm has always been the research direction of scholars. In this paper, a new bioinspired algorithm is proposed to solve the Chinese postman problem based on molecular computation, which has the advantages of high computational efficiency, large storage capacity, and strong parallel computing ability. In the calculation, DNA chain is used to properly represent the vertex, edge, and corresponding weight, and then all possible path combinations are effectively generated through biochemical reactions. The feasible solution space is obtained by deleting the nonfeasible solution chains, and the optimal solution is solved by algorithm. Then the computational complexity and feasibility of the DNA algorithm are proved. By comparison, it is found that the computational complexity of the DNA algorithm is significantly better than that of previous algorithms. The correctness of the algorithm is verified by simulation experiments. With the maturity of biological operation technology, this algorithm has a broad application space in solving large-scale combinatorial optimization problems.


---

## Body

## 1. Background

The Chinese postman problem (CPP) was first raised by Guan Meigu [1] in the 1960s, and it was based on the question of “how should a postman choose a route so that he can walk all the streets where he is responsible for delivering the letter and the shortest distance traveled?” It arises in numerous applications in many fields, such as municipal solid waste collection [2], winter gritting [3], material distribution and transportation [4], and intelligent transportation [5]. Over the past half century, many branches have been formed in the study of the Chinese postman problem, such as the directed Chinese postman problem (DCPP) [6], the mixed Chinese postman problem (MCPP) [7], the windy postman problem (WPP) [8], and the hierarchical Chinese postman problem (HCPP) [9]. Because of its wide application, the Chinese postman problem has been extensively studied, including the design and improvement of calculation methods, the deformation of the problem, and its application in various aspects. In 1965, Edmonds [10] gave the definition of the Chinese postman problem and then proposed an algorithm to solve the shortest distribution route by first finding the minimum weight matching of any graph to construct Euler graph. Later, in 2002, Yin et al. [11] used molecular biology technology to solve the Chinese postman problem. In 2003, Jiang and Li [12] solved the problem in an undirected graph with an evolutionary algorithm and achieved good results. Their algorithm can also be extended to the directed Chinese postman problem. In 2005, Fei and Cui [13] proposed a new search algorithm CPDPA based on the idea of the dynamic planning decision-making process, which realized the dynamic planning of the Chinese postman problem for the first time, and effectively solved the optimal path problem of the NK model. In 2009, Li and Wang [14] proposed a new solution algorithm, which used the polymerase chain reaction technology to eliminate the nonsolution, and then combined the surface-based DNA computing method with fluorescence labeling technology and finally extracted the optimal solution from all feasible solutions. In 2011, Zoraida [15] used the thermodynamic properties of DNA and the chemical reaction operation with other biomolecules to improve the accuracy of the algorithm experiment. According to the specific operation steps, the optimal solution of the Chinese postman problem was finally obtained. In 2016, Lee [16] created the Euler circle algorithm for the Chinese postman problem. They selected the edge with the least weight from the adjacent edge of each vertex to get the minimum spanning tree and finally got the shortest path edge of the odd order vertex.In addition, the arc routing optimization problem similar to the Chinese postman problem has also been widely concerned. Nossack et al. [17] introduce the first modeling of the windy rural postman problem with zigzag option and time windows, discuss two mixed-integer programming formulations for the problem at hand, and suggest exact solution approaches. Meng et al. [18] investigate a class of CTSP, called serial CTSP (S-CTSP), and present a population-based incremental learning (PBIL) approach to the problem. By adding a powerful local search operation, 2-opt, to the algorithm, they can further enhance its search ability. Wang and Lu [19] propose a memetic algorithm with competition (MAC) to solve the capacitated green vehicle routing problem (CGVRP). Carmine et al. [20] develop a two-stage solution approach for the Directed Rural Postman Problem with Turn Penalties (DRPP-TP) and describe an integer linear program that is combined with a local search algorithm. This combination produces high-quality solutions to the DRPP-TP in a reasonable amount of computing time. To solve the Chinese and windy postman problem with variable service costs (CPPVSC), Keskin et al. [8] proposed two heuristics for searching the solution. Xu et al. [21] develop a Delaunay-triangulation-based Variable Neighborhood Search (DVNS) algorithm to solve a general colored traveling salesman problem (GCTSP). Wang et al. [22] firstly introduce a multiobjective MTPDPTW-MP (MO-MTPDPTWMP) with three objectives to better describe the real-world scenario. Then, a multiobjective iterated local search algorithm with adaptive neighborhood selection (MOILS-ANS) is proposed to solve the problem.In real life, as a classical optimization problem, the Chinese postman problem is widely used in practice. Therefore, it is of great practical value and significance to design an efficient algorithm to solve this problem. But with the increase of the number and scale of the problem, the computational efficiency and storage limit of the traditional algorithm are greatly limited, and it is more and more impossible to solve the problem in the polynomial time level. As a new intelligent algorithm, DNA computing has both the advantages of parallel computing and the amazing storage capacity, which has become one of the potential tools to solve the problem efficiently.The Chinese postman problem is the mail delivery distance in a certain area. The postman starts from the post office every day, goes through all the streets in the area, and then returns to the post office. The question is how he should arrange the route to deliver the letters so as to minimize the total distance. In the language of graph theory, the Chinese postman problem is to find a generalized Euler tour that satisfies the sum of the weight of all edges and the sum is minimized, and the starting (ending) vertex is fixed. Given an undirected connected graphG=V,E, V represents the vertex set and E represents the set of arcs (connecting by the vertices in V), and V=n and E=m. Let W=wij be the cost (distance) matrix associated with E and wij=wji. In general, we assume that v1 is both starting and ending node, and the a generalized Euler tour is A. The mathematical definition of the Chinese postman problem is as follows:(1)Min∑eij∈Awijxijs.t.∑eij∈Axij=∑eki∈Axki∀vi∈Vxij≥1and interger∀eij∈A.The optimal route of the Chinese postman problem generally has the following limitations:(1)
Route is continuous, starting, and returning to the same designated vertex(2)
Each edge has been traversed at least once by the route(3)
The weight sum of the route is the minimumWe use Figure1 as an example for the Chinese postman problem. The optimal route starts from the vertex v1, then passes through all the edges at least once, and finally returns v1, and the sum of the weight sum of the route is minimized. Through mathematical calculation, the optimal route to meet the requirements can be obtained as follows:(2)e12,e23,e34,e45,e53,e36,e65,e52,e26,e64,e46,e61,e13,e32,e21.Figure 1
The graph of corresponding CPP with six vertices.In this paper, we will use the DNA algorithm of the Adleman–Lipton model to solve the Chinese postman problem. The feasibility and computational complexity of the algorithm are analyzed, which proves that the algorithm has higher computational efficiency, and the correctness of the algorithm is also verified by simulation experiments.The structure of this paper is as follows. Section2 introduces the research status of DNA computing and the basic knowledge of the Adleman–Lipton model. Section 3 uses a parallel DNA computing algorithm to solve the Chinese postman problem by different operations. The feasibility and computational complexity of the algorithm are analyzed in Section 4. Section 5 gives the simulation results of the algorithm. Finally, in Section 6, we make a summary evaluation of the algorithm and put forward the future research direction.


## 2. Biocomputing and Modeling

With the rise and development of molecular biology, the structure and function of biomacromolecules have been proposed gradually. It is found that, in the process of interaction of biomacromolecules, following the laws of biology, chemistry, and physics, a computing process like information transfer and processing process will be formed, accompanied by the emergence of biomacromolecule computing. The concept of biocomputing was first introduced by the famous “salesman problem”. Researchers solved this problem with special DNA tubes in seven nodes, opening a new era of DNA computing research. In 1994, Adleman [23] solved a well-known computational problem with the DNA computing method, that is, the directed Hamiltonian circuit problem. With the increase of variables, it becomes more and more difficult to solve the problem, but DNA computing can easily solve the problem. Adelman’s experiments prove the feasibility of DNA for specific purpose computing and verify the advantages of molecular computing in parallel, high-density compression solutions. Its novelty is that it creates a precedent for applying mathematical problems to molecular level computing and encourages the application of DNA computing in a broader field.Subsequently, DNA computing has also been used by many scientists to solve various nondeterministic polynomial (NP) mathematical problems, and many typical biological computing models have been established at the same time. For example, in 1995, Lipton [24] solved the satisfiability (SAT) problem through DNA experiments, proving that DNA-based computing has a huge efficiency improvement compared with traditional electronic computers. In 1997, Ouyang et al. [25] proposed a method to solve the biggest group problem by using molecular biology technology. They map all possible clusters into a set of binary numbers to form a data pool and then delete and classify it. The effective solution of this problem provides strong evidence for DNA computing to solve NP-complete problem in the future. At present, DNA computing has become a hot topic in the research of new computing models. Through different operation and control technologies for DNA molecules, new algorithms can be formed to provide strong technical support for many problems without effective solutions [26–39]. For the Chinese postman problem, with the increase of data volume and scale, the traditional algorithm will be more difficult to solve it. Therefore, we need to propose and try some high-performance computing algorithms; DNA algorithm is one of them.DNA is a substance that stores genetic information in living cells. DNA is a very thin and long polymer compound composed of a series of deoxynucleotide chains, which in turn are composed of deoxyribose, phosphate, and nitrogen-containing bases. DNA algorithm mainly uses the bases in it, which contains 4 kinds of bases, namely, adenine (A), guanine (G), cytosine (C), and thymine (T). The four types of bases have Watson–Crick complementarity, that is, two opposing bases meet the complementary characteristics, where A complementary to T and C complementary to G. Billions of years of evolutionary cells have created and perfected enzymes with special functions that can copy information from DNA molecules and pass it on to other DNA molecules. The Adleman–Lipton model uses basic biological experimental operations and uses the strings of four different bases A, C, G, and T in DNA as information means to express, and different information is represented by different codes. This provides storage capacity for large amounts of information. A similarly biologically different enzyme is used for different operations to achieve a given goal. Although the fields are different, the principles are the same. In computation, we consider that the length of a single-stranded DNA is the number of nucleotides composed of a single strand. Therefore, if a single-stranded DNA contains 30 nucleotides, we consider the strand to be 30 in length and called 30 mer.In the Adleman–Lipton model, for given test tubes (experimental test tubes) which contain a finite number of DNA strands consisting ofA, G, C, and T, we can perform the following operations:(1)
MergeT1,T2: for two given test tubes T1 and T2, it stores the union T1 and T2 in T1 and leaves T2 empty.(2)
AnnealingT: for a given test tube T, it produces all feasible double strands in T.(3)
DenaturationT: for a given test tube T, it dissociates each double strand in T into two single strands.(4)
SeparationT1,X,T2: for a given test tube T1 and a given set of strings X, it removes all single strands containing the string X from T1 and produces a test tube T2 with the removed strands.(5)
DiscardT: for a given test tube T, it discards the strands in tube T.(6)
CopyT1,T2: for a given test tube T1, it produces a test tube T2 with the same strands as T1.(7)
CleavageT,γ0γ1: given a test tube T and strings γ0γ1, it cuts every strand containing γ0γ1 into three strands:(3)…,αγ0γ1β,…⇔…,α,γ0γ1,β,….(8)
SortT1,T2,T3: it moves the shortest strands of the test tube T1 to the tube T2 and the longest to the test tube T3, and the rest is still stored in the test tube T1.(9)
ReadT: for a given tube T, the operation is used to describe a single molecule, which is contained in the tube T. Even if T contains many different molecules and each of which encodes a different set of bases, the operation can give an explicit description of exactly one of them.Since the above nine operations can be realized by a series of continuous operations on the biological chains, it can reasonably be deduced that the complexity of each operation isO1 [40]. The assumption has been used in previous studies to analyze the complexity of DNA computing [41–46]. We use these operations to implement algorithms to solve the Chinese postman problem.


## 3. Algorithm Design for the Chinese Postman Problem

In this section, the basic idea of the algorithm is introduced first, and then the symbols in the algorithm are set uniformly. Finally, Figure1 is taken as an example of the Chinese postman problem to demonstrate the algorithm.


### 3.1. Preliminary Ideas

The basic idea to solve the Chinese postman problem by DNA computing is as follows: first, the corresponding vertices and edges of the Chinese postman problem are represented by specific symbols; then, all possible DNA chains in the problem are generated by biochemical reactions, and the chains that meet the constraint conditions of the problem are screened. Finally, through search and recognition, the optimal solution corresponding to the biological chain is obtained, and then, the optimal route of the problem is obtained.Correspondingly, the algorithm is divided into four steps:Step 1: generate all possible random routesStep 2: filter out routes that start at a fixed node (post office) and end at the same nodeStep 3: select all routes that pass through all edges at least onceStep 4: find the shortest generalized Euler closed loop, get the shortest route, and output the optimal solution


### 3.2. Graph Theory Expression with DNA Strands

In this paper, in order to clarify and standardise the expression of our algorithm, it is necessary to define and explain the symbols and notations in the algorithm. Therefore, we use the symbols in Table1 to illustrate.Table 1
Notations and symbols.
SymbolDescriptionSymbolDescriptionVVertex setvkThek-th vertexEEdge set#Starting and ending of DNA strandWWeight setAk,BkDNA string of thek-th vertexnNumber of verticesAi℧cij℧BjDNA string of the edgeeijmNumber of edgesBiAi¯Complementary strands of adjacent routesIn DNA computing, as the optimal path is mainly determined by the length of the feasible solution strands, it is necessary and critical to design the length of the problem element information strands. So, in this paper, we set℧cij℧=wij∗l mer and #=Ai=Bi=l mer, where l represent positive integers. Obviously, the length of the single-stranded DNA in the experiment depends largely on the size of the problem involved. At the same time, we use their complementary strand BiAi¯ to synthesize double strands. Generally, we assume that node v1 is the beginning and ending points of the route for the Chinese postman problem.


### 3.3. Algorithm Description

For the Chinese postman problem, we set the nodes as verticesV, the streets as edges E, and the weight of edge eij is wij.Let us start with the initial tubesT1, T2, and T3:(4)T1=#A1℧c1j1℧Bj1,…,Ai℧cij℧Bj,…,Aip℧cip1℧B1#|e1j1,eij,eip1∈E,T2=BiAi¯|i=1,2,…,n,T3=c1j1,cij2,…,cij,…,cip1|eij∈E,cij=wij−2∗l.We use the Chinese postman problem in Figure1 (beginning and ending nodes are v1) as an example to demonstrate the process of the algorithm. Let(5)T1=#A1℧c12℧B2,#A1℧c13℧B3,#A1℧c16℧B6,A2℧c21℧B1#,A2℧c23℧B3,A2℧c25℧B5,A2℧c26℧B6,A3℧c31℧B1#,A3℧c32℧B2,A3℧c34℧B4,A3℧c35℧B5,A3℧c36℧B6,A4℧c43℧B3,A4℧c45℧B5,A4℧c46℧B6,A5℧c52℧B2,A5℧c53℧B3,A5℧c54℧B4,A5℧c56℧B6,A6℧c61℧B1#,A6℧c62℧B2,A6℧c63℧B3,A6℧c64℧B4,A6℧c65℧B5,T2=B1A1¯,B2A2¯,B3A3¯,B4A4¯,B5A5¯,B6A6¯,T3=c12,c13,c16,c21,c23,c25,c26,c31,c32,c34,c35,c36,c43,c45,c46,c52,c53,c54,c56,c61,c62,c63,c64,c65.In Figure1, the edge set matrix composed of binary variables is as follows:(6)MG1=xij=011001101011110111001011011101001110.After the above seven operations, we generate DNA strands to represent different postman routes. Taking the problem in Figure1 as an example, the chain #A1℧c12℧B2A2℧c25℧B5A5℧c54℧B4A4℧c43℧B3A3℧c31℧B1# represents the route e12,e25,e54,e43,e31.For example, in Figure1, route e12,e23,e34,e45,e53,e36,e64,e45,e56,e63,e32,e26,e61 should be excluded because it does not pass through edges e13 and e25. After the operations, all DNA single strands in the tube T5 represent the routes start and end vertex v1 and pass through all edges at least once.Finally, we can get the exact solutions strands for the Chinese postman problem.


#### 3.3.1. Generate a Data Pool and Filter Out the Routes That Start and End with the Specified Vertex

is provided in Algorithm1.Algorithm 1:Generate various route strands.
We can get all the possible routes strands (fromv1 to v1) of the Chinese postman problem in a test tube.(1-1)MergeT1,T2;(1-2)AnnealingT1;(1-3)DenaturationT1;(1-4)SeparationT1,#A1,T4;(1-5)DiscardT1;(1-6)SeparationT4,B1#,T5;(1-7)DiscardT4.


#### 3.3.2. Path through All Edges

is provided in Algorithm2Algorithm 2:Judge the edges of the route.
In the Chinese postman problem, each edge should be traversed at least once. In other words, a route cannot be a feasible path if it does not go through all the edges. We judge the information of the edge that the route passes by and screen out the routes that do not meet the restriction.Fori=1 to i=n−1Forj=i+1 to j=n(2-1)Ifxij=1(2-2-1)SeparationT5,Ai℧cij℧Bj,T6;(2-2-2)SeparationT5,Aj℧cji℧Bi,T7;(2-2-3)MergeT6,T7;(2-2-4)DiscardT7;(2-2-5)DiscardT5;(2-2-6)CopyT6,T5;(2-2-7)DiscardT6;Else(2-3)Continue.End forEnd for


#### 3.3.3. Eliminate the Influence of Vertex Chain Length

is provided in Algorithm3Algorithm 3:Generate weight chain of edges.
The feasible solution chains contain the information of the chain length passing through the vertex. The optimal solution based on the total chain length will be affected by the number of vertices the route passes through. Therefore, it is necessary to exclude the vertex chain information contained in the original feasible chain.Fori=1 to i=n(3-1)CleavageT5,BiAi;(3-2)SeparationT5,BiAi,T8;(3-3)DiscardT8;(3-4)MergeT5,℧℧¯;(3-5)AnnealingT5;(3-6)DenaturationT5;(3-7)SeparationT5,℧℧,T9;(3-8)DiscardT5;(3-9)CopyT9,T5;(3-10)DiscardT9.End forIn Figure1, the edge route e13,e36,e65,e54,e46,e62,e25,e53,e32,e21,e16,e64,e43,e31 can be coded as #A1℧c13℧℧c36℧℧c65℧℧c54℧℧c46℧℧c62℧℧c25℧℧c53℧℧c32℧℧c21℧℧c16℧℧c64℧℧c43℧℧c31℧B1#.


#### 3.3.4. Reconfirm That the Route Passes All Edges At Least Once

is provided in Algorithm4Algorithm 4:Judge the edges of the route again.
Because the complementary chain of vertexBiAi¯ is used to generate the weight information chain of the edge, some paths that do not pass through all the edges will also be doped in tube T5, so the chains should be excluded. We judge the path passing through the edges again and screen out the feasible path chains satisfying that all the edges pass through at least once.Fori=1 to i=n−1Forj=i+1 to j=n(4-1)Ifxij=1(4-2-1)SeparationT5,℧cij℧,T10;(4-2-2)SeparationT5,℧cji℧,T11;(4-2-3)MergeT10,T11;(4-2-4)DiscardT11;(4-2-5)DiscardT5;(4-2-6)CopyT10,T5;(4-2-7)DiscardT10;Else(4-3)Continue.End forEnd for


#### 3.3.5. Get the Solution

is provided in Algorithm5Algorithm 5:Search the optimal route.
In many different routes, the optimal solution of the Chinese postman problem has the minimum weight value. We search for the shortest DNA strand in the last test tube to indicate the result of the Chinese postman problem.(5-1)SortT5,T12,T13;(5-2)ReadT12.


## 3.1. Preliminary Ideas

The basic idea to solve the Chinese postman problem by DNA computing is as follows: first, the corresponding vertices and edges of the Chinese postman problem are represented by specific symbols; then, all possible DNA chains in the problem are generated by biochemical reactions, and the chains that meet the constraint conditions of the problem are screened. Finally, through search and recognition, the optimal solution corresponding to the biological chain is obtained, and then, the optimal route of the problem is obtained.Correspondingly, the algorithm is divided into four steps:Step 1: generate all possible random routesStep 2: filter out routes that start at a fixed node (post office) and end at the same nodeStep 3: select all routes that pass through all edges at least onceStep 4: find the shortest generalized Euler closed loop, get the shortest route, and output the optimal solution


## 3.2. Graph Theory Expression with DNA Strands

In this paper, in order to clarify and standardise the expression of our algorithm, it is necessary to define and explain the symbols and notations in the algorithm. Therefore, we use the symbols in Table1 to illustrate.Table 1
Notations and symbols.
SymbolDescriptionSymbolDescriptionVVertex setvkThek-th vertexEEdge set#Starting and ending of DNA strandWWeight setAk,BkDNA string of thek-th vertexnNumber of verticesAi℧cij℧BjDNA string of the edgeeijmNumber of edgesBiAi¯Complementary strands of adjacent routesIn DNA computing, as the optimal path is mainly determined by the length of the feasible solution strands, it is necessary and critical to design the length of the problem element information strands. So, in this paper, we set℧cij℧=wij∗l mer and #=Ai=Bi=l mer, where l represent positive integers. Obviously, the length of the single-stranded DNA in the experiment depends largely on the size of the problem involved. At the same time, we use their complementary strand BiAi¯ to synthesize double strands. Generally, we assume that node v1 is the beginning and ending points of the route for the Chinese postman problem.


## 3.3. Algorithm Description

For the Chinese postman problem, we set the nodes as verticesV, the streets as edges E, and the weight of edge eij is wij.Let us start with the initial tubesT1, T2, and T3:(4)T1=#A1℧c1j1℧Bj1,…,Ai℧cij℧Bj,…,Aip℧cip1℧B1#|e1j1,eij,eip1∈E,T2=BiAi¯|i=1,2,…,n,T3=c1j1,cij2,…,cij,…,cip1|eij∈E,cij=wij−2∗l.We use the Chinese postman problem in Figure1 (beginning and ending nodes are v1) as an example to demonstrate the process of the algorithm. Let(5)T1=#A1℧c12℧B2,#A1℧c13℧B3,#A1℧c16℧B6,A2℧c21℧B1#,A2℧c23℧B3,A2℧c25℧B5,A2℧c26℧B6,A3℧c31℧B1#,A3℧c32℧B2,A3℧c34℧B4,A3℧c35℧B5,A3℧c36℧B6,A4℧c43℧B3,A4℧c45℧B5,A4℧c46℧B6,A5℧c52℧B2,A5℧c53℧B3,A5℧c54℧B4,A5℧c56℧B6,A6℧c61℧B1#,A6℧c62℧B2,A6℧c63℧B3,A6℧c64℧B4,A6℧c65℧B5,T2=B1A1¯,B2A2¯,B3A3¯,B4A4¯,B5A5¯,B6A6¯,T3=c12,c13,c16,c21,c23,c25,c26,c31,c32,c34,c35,c36,c43,c45,c46,c52,c53,c54,c56,c61,c62,c63,c64,c65.In Figure1, the edge set matrix composed of binary variables is as follows:(6)MG1=xij=011001101011110111001011011101001110.After the above seven operations, we generate DNA strands to represent different postman routes. Taking the problem in Figure1 as an example, the chain #A1℧c12℧B2A2℧c25℧B5A5℧c54℧B4A4℧c43℧B3A3℧c31℧B1# represents the route e12,e25,e54,e43,e31.For example, in Figure1, route e12,e23,e34,e45,e53,e36,e64,e45,e56,e63,e32,e26,e61 should be excluded because it does not pass through edges e13 and e25. After the operations, all DNA single strands in the tube T5 represent the routes start and end vertex v1 and pass through all edges at least once.Finally, we can get the exact solutions strands for the Chinese postman problem.


### 3.3.1. Generate a Data Pool and Filter Out the Routes That Start and End with the Specified Vertex

is provided in Algorithm1.Algorithm 1:Generate various route strands.
We can get all the possible routes strands (fromv1 to v1) of the Chinese postman problem in a test tube.(1-1)MergeT1,T2;(1-2)AnnealingT1;(1-3)DenaturationT1;(1-4)SeparationT1,#A1,T4;(1-5)DiscardT1;(1-6)SeparationT4,B1#,T5;(1-7)DiscardT4.


### 3.3.2. Path through All Edges

is provided in Algorithm2Algorithm 2:Judge the edges of the route.
In the Chinese postman problem, each edge should be traversed at least once. In other words, a route cannot be a feasible path if it does not go through all the edges. We judge the information of the edge that the route passes by and screen out the routes that do not meet the restriction.Fori=1 to i=n−1Forj=i+1 to j=n(2-1)Ifxij=1(2-2-1)SeparationT5,Ai℧cij℧Bj,T6;(2-2-2)SeparationT5,Aj℧cji℧Bi,T7;(2-2-3)MergeT6,T7;(2-2-4)DiscardT7;(2-2-5)DiscardT5;(2-2-6)CopyT6,T5;(2-2-7)DiscardT6;Else(2-3)Continue.End forEnd for


### 3.3.3. Eliminate the Influence of Vertex Chain Length

is provided in Algorithm3Algorithm 3:Generate weight chain of edges.
The feasible solution chains contain the information of the chain length passing through the vertex. The optimal solution based on the total chain length will be affected by the number of vertices the route passes through. Therefore, it is necessary to exclude the vertex chain information contained in the original feasible chain.Fori=1 to i=n(3-1)CleavageT5,BiAi;(3-2)SeparationT5,BiAi,T8;(3-3)DiscardT8;(3-4)MergeT5,℧℧¯;(3-5)AnnealingT5;(3-6)DenaturationT5;(3-7)SeparationT5,℧℧,T9;(3-8)DiscardT5;(3-9)CopyT9,T5;(3-10)DiscardT9.End forIn Figure1, the edge route e13,e36,e65,e54,e46,e62,e25,e53,e32,e21,e16,e64,e43,e31 can be coded as #A1℧c13℧℧c36℧℧c65℧℧c54℧℧c46℧℧c62℧℧c25℧℧c53℧℧c32℧℧c21℧℧c16℧℧c64℧℧c43℧℧c31℧B1#.


### 3.3.4. Reconfirm That the Route Passes All Edges At Least Once

is provided in Algorithm4Algorithm 4:Judge the edges of the route again.
Because the complementary chain of vertexBiAi¯ is used to generate the weight information chain of the edge, some paths that do not pass through all the edges will also be doped in tube T5, so the chains should be excluded. We judge the path passing through the edges again and screen out the feasible path chains satisfying that all the edges pass through at least once.Fori=1 to i=n−1Forj=i+1 to j=n(4-1)Ifxij=1(4-2-1)SeparationT5,℧cij℧,T10;(4-2-2)SeparationT5,℧cji℧,T11;(4-2-3)MergeT10,T11;(4-2-4)DiscardT11;(4-2-5)DiscardT5;(4-2-6)CopyT10,T5;(4-2-7)DiscardT10;Else(4-3)Continue.End forEnd for


### 3.3.5. Get the Solution

is provided in Algorithm5Algorithm 5:Search the optimal route.
In many different routes, the optimal solution of the Chinese postman problem has the minimum weight value. We search for the shortest DNA strand in the last test tube to indicate the result of the Chinese postman problem.(5-1)SortT5,T12,T13;(5-2)ReadT12.


## 3.3.1. Generate a Data Pool and Filter Out the Routes That Start and End with the Specified Vertex

is provided in Algorithm1.Algorithm 1:Generate various route strands.
We can get all the possible routes strands (fromv1 to v1) of the Chinese postman problem in a test tube.(1-1)MergeT1,T2;(1-2)AnnealingT1;(1-3)DenaturationT1;(1-4)SeparationT1,#A1,T4;(1-5)DiscardT1;(1-6)SeparationT4,B1#,T5;(1-7)DiscardT4.


## 3.3.2. Path through All Edges

is provided in Algorithm2Algorithm 2:Judge the edges of the route.
In the Chinese postman problem, each edge should be traversed at least once. In other words, a route cannot be a feasible path if it does not go through all the edges. We judge the information of the edge that the route passes by and screen out the routes that do not meet the restriction.Fori=1 to i=n−1Forj=i+1 to j=n(2-1)Ifxij=1(2-2-1)SeparationT5,Ai℧cij℧Bj,T6;(2-2-2)SeparationT5,Aj℧cji℧Bi,T7;(2-2-3)MergeT6,T7;(2-2-4)DiscardT7;(2-2-5)DiscardT5;(2-2-6)CopyT6,T5;(2-2-7)DiscardT6;Else(2-3)Continue.End forEnd for


## 3.3.3. Eliminate the Influence of Vertex Chain Length

is provided in Algorithm3Algorithm 3:Generate weight chain of edges.
The feasible solution chains contain the information of the chain length passing through the vertex. The optimal solution based on the total chain length will be affected by the number of vertices the route passes through. Therefore, it is necessary to exclude the vertex chain information contained in the original feasible chain.Fori=1 to i=n(3-1)CleavageT5,BiAi;(3-2)SeparationT5,BiAi,T8;(3-3)DiscardT8;(3-4)MergeT5,℧℧¯;(3-5)AnnealingT5;(3-6)DenaturationT5;(3-7)SeparationT5,℧℧,T9;(3-8)DiscardT5;(3-9)CopyT9,T5;(3-10)DiscardT9.End forIn Figure1, the edge route e13,e36,e65,e54,e46,e62,e25,e53,e32,e21,e16,e64,e43,e31 can be coded as #A1℧c13℧℧c36℧℧c65℧℧c54℧℧c46℧℧c62℧℧c25℧℧c53℧℧c32℧℧c21℧℧c16℧℧c64℧℧c43℧℧c31℧B1#.


## 3.3.4. Reconfirm That the Route Passes All Edges At Least Once

is provided in Algorithm4Algorithm 4:Judge the edges of the route again.
Because the complementary chain of vertexBiAi¯ is used to generate the weight information chain of the edge, some paths that do not pass through all the edges will also be doped in tube T5, so the chains should be excluded. We judge the path passing through the edges again and screen out the feasible path chains satisfying that all the edges pass through at least once.Fori=1 to i=n−1Forj=i+1 to j=n(4-1)Ifxij=1(4-2-1)SeparationT5,℧cij℧,T10;(4-2-2)SeparationT5,℧cji℧,T11;(4-2-3)MergeT10,T11;(4-2-4)DiscardT11;(4-2-5)DiscardT5;(4-2-6)CopyT10,T5;(4-2-7)DiscardT10;Else(4-3)Continue.End forEnd for


## 3.3.5. Get the Solution

is provided in Algorithm5Algorithm 5:Search the optimal route.
In many different routes, the optimal solution of the Chinese postman problem has the minimum weight value. We search for the shortest DNA strand in the last test tube to indicate the result of the Chinese postman problem.(5-1)SortT5,T12,T13;(5-2)ReadT12.


## 4. Feasibility and Time Complexity of the Proposed DNA Algorithm

We should prove that the proposed DNA algorithm can find the DNA chain corresponding to the optimal solution in a certain length range and solve the Chinese postman problem in a certain time complexity.Theorem 1.
The proposed DNA algorithm can solve the Chinese postmen problem.Proof.
We use DNA strands with different symbols to express the corresponding nodes and edges of the problem and use biochemical reactions with complementary strands to generate all possible routes strands in the test tube. Therefore, after Algorithm1, each DNA strand represents a feasible path starting from a specified fixed vertex and ending it. Another constraint of the feasible solutions is that each edge needs to pass at least once, so we screen out feasible chains that pass through all specified edges by Algorithm 2. The chains L1 after Algorithm 2 can be described as(7)#A1℧c1j1℧Bj1Aj1℧cj1j2℧Bj2,…,℧Ajpcjpjp+1℧Bjp+1,…,Aq℧cq1℧B1#jp,jp+1∈1,2,…,n.
In order to select the optimal solution in a feasible chain, the weight of the feasible chain needs to be compared. Because the original chain contains information passing through the vertex, we filter out the vertex information in the chain through Algorithm3. Algorithm 4 excludes the infeasible solution chains of doping caused by the synthesis of complementary chains in Algorithm 3. At this time, the chains L2 which pass through all edges at least once and only contain edge weight information are retained in test tube T5. After the step, the chain L2 can be expressed as follows:(8)#A1℧c1j1℧℧cj1j2℧℧,…,℧cjpjp+1℧,…,℧cq1℧B1#.
In addition, we set℧cij℧=wij∗l mer and #=Ai=Bi=l mer. The length of chain L2 is given by(9)L2=#+A1+℧c1j1℧+℧cj1j2℧+⋯+℧cjpjp+1℧+⋯+℧cq1℧+B1+#=l+l+w1j1∗l+wj1j2∗l+⋯+wjpjp+1∗l+⋯+wq1∗l+l+l=4l+w1j1+wj1j2+⋯+wjpjp+1+⋯+wq1∗l=4l+∑℧cij℧∈T5wij∗l.
Therefore, the length ofL2 chain changes in the same direction as the weight of the edge through the path it represents. In Algorithm 5, we obtain the optimal solution to the problem by comparing the lengths of the DNA chains.Theorem 2.
The Chinese postman problem can be solved at theOn2 time complexity level.Proof.
Since each biochemical operation is completed inO1 time complexity [41–46], according to the steps we designed, the Chinese postman problem can be performed in a limited number of steps and time complexity. The time complexity T of the DNA algorithm is as follows:(10)TAlgorithm1=O1;TAlgorithm2=On2;TAlgorithm3=On;TAlgorithm4=On2;TAlgorithm5=O1;T=TAlgorithm1+TAlgorithm2+TAlgorithm3+TAlgorithm4+TAlgorithm5=O1+On2+On+On2+O1=On2.
Therefore, according to the analysis, the algorithm can solve the Chinese postman problem at theOn2 time complexity level.


## 5. Simulation Experiments of DNA Algorithms

In order to verify the feasibility of the algorithm, simulation operations are very necessary and meaningful. The calculation of DNA depends on the accuracy of biochemical molecular operation; otherwise, it will lead to the accumulation and expansion of errors in biochemical reactions. At the same time, the operations should exclude the DNA sequences that may promote the unexpected hybridization of the probe library. Therefore, the design of appropriate DNA sequence is the necessary basis to ensure the accuracy of DNA calculation. In order to achieve these objectives, the experiments comply with the seven limitations of DNA manipulation proposed in [47]. These limitations include the following: no more than 7 base pairs of any 8 base pairs between library sequences and their own or any other library sequences; no occurrence of 5 or more consecutive identical nucleotides appear in all library and probe sequences; no more than 7 matches of any probe sequence with any 8 base pairs of any library sequence; the probe will only bind weakly where it is not intended to bind, and so on. Similarly, the experiments use the sequence design method in references [40, 47–52].In this paper, the computational molecular biology tool Biopython is used as the system development platform, and Braich’s program is used to generate “appropriate DNA sequences” suitable for biological computing algorithm, which can be used to solve the CPP. Braich’s program and other simulations are running on a Windows 7 machine, with an Intel Core-XP CPU and 8 GB main memory, and the compiler is Python 3.6. Our modified program is used to construct a random sequence of 4 bases for each bit of the library and to check whether the library chain meets the seven constraints of DNA sequence [47]. When generating one DNA chain, the first step is to determine whether the chain satisfies the restrictions specified in references [40, 47–52]. If the produced DNA sequence does not meet the restrictions, the program will continue to generate another new sequence. When these restrictions can be met, the sequence is accepted for subsequent biochemical reactions. Using this method, we can get the “appropriate DNA sequences” which meet the restriction conditions to improve the accuracy of biochemical reactions.Therefore, taking the Chinese postman problem in Figure1 as an example, the program generates random sequences to form Ai, Bi, #, ℧, and cij (l=6 mer and ℧=2 mer) as shown in Table 2. Table 3 demonstrates the DNA node sequence composed by Braich’s methods. In Table 4, the enthalpy, entropy, and free energy of the binding of each probe to the corresponding region in the chains have also been calculated. Their average deviation and standard deviation levels are also shown in Table 4. Then, DNA solution strands for the Chinese postman problem have been found. Table 5 demonstrates the DNA solution strands for the Chinese postman problem.Table 2
Sequences chosen to representAi, Bi, #, ℧, and ciji,j∈1,2,…,7 for the Chinese postman problem.
Bit3′−5′DNA sequenceA1AACTGAA2TGTGAGA3GACTTCA4CATTTGA5ACTCGCA6CTACGT#AGCAGAc12TCGTCACGc16AGTGACGCc25ATTAAGCGCCAATCc34AATGACAGCCAACCGAGATCc36GCGTTTCAc46ATc21ATCAGCTAc61TATCACAGc52AATGCTAGAGTGCTc43TTCTGAACACTGACACCAGAc63ATCATGCTc64TGB1TAAATCB2CCAATAB3ATACGCB4TGCAAGB5GATCTCB6TGAAGC℧GGc13CATAGCACGCCTGCCTCTGTc23TCc26CCGAGATCCTCAATc35ATAGCGCTc45AGCCAATGc56CGACTAATATCGTCc31GTGCGCACGAGCCTTTACCAc32GCc62TCCTCGCTAGATCGc53ACGTCATGc54CTATTTCAc65GTGTACGACCCTATTable 3
Sequences chosen to represent the elementseij for the Chinese postman problem.
Bit3′−5′DNA sequenceA1℧c12℧B2AACTGAGGTCGTCACGGGCCAATAA1℧c13℧B3AACTGAGGCATAGCACGCCTGCCTCTGTGGATACGCA1℧c16℧B6AACTGAGGAGTGACGCGGTGAAGCA2℧c23℧B3TGTGAGGGTCGGATACGCA2℧c25℧B5TGTGAGGGATTAAGCGCCAATCGGGATCTCA2℧c26℧B6TGTGAGGGCCGAGATCCTCAATGGTGAAGCA3℧c34℧B4GACTTCGGAATGACAGCCAACCGAGATCGGCATTTGA3℧c35℧B5GACTTCGGATAGCGCTGGGATCTCA3℧c36℧B6GACTTCGGGCGTTTCAGGTGAAGCA4℧c45℧B5CATTTGGGAGCCAATGGGGATCTCA4℧c46℧B6CATTTGGGATGGTGAAGCA5℧c56℧B6ACTCGCGGCGACTAATATCGTCGGTGAAGCA2℧c21℧B1TGTGAGGGATCAGCTAGGTAAATCA3℧c31℧B1GACTTCGGGTGCGCACGAGCCTTTACCAGGTAAATCA6℧c61℧B1CTACGTGGTATCACAGGGTAAATCA3℧c32℧B2AGACTTCGGGCGGCCAATAA5℧c52℧B2ACTCGCGGAATGCTAGAGTGCTGGCCAATAA6℧c62℧B2CTACGTGGTCCTCGCTAGATCGGGCCAATAA4℧c43℧B3CATTTGGGTTCTGAACACTGACACCAGAGGATACGCA5℧c53℧B3ACTCGCGGACGTCATGGGATACGCA6℧c63℧B3CTACGTGGATCATGCTGGATACGCA5℧c54℧B4ACTCGCGGCTATTTCAGGTGCAAGA6℧c64℧B4CTACGTGGTGGGTGCAAGA6℧c65℧B5CTACGTGGGTGTACGACCCTATGGGATCTCTable 4
The energies over all probe/library strand interactions.
VertexEnthalpy energyHEntropy energySFree energyGA1℧c12℧B2101.4250.923.9A1℧c13℧B3116.9294.426.6A1℧c16℧B699.7252.623.2A2℧c23℧B396.1246.323.3A2℧c25℧B5106.7269.326.3A2℧c26℧B6100.7249.923.7A3℧c34℧B4102.9263.223.8A3℧c35℧B5112.5279.627.3A3℧c36℧B6103.5273.323.4A4℧c45℧B5102.7263.922.7A4℧c46℧B6113.5294.528.0A5℧c56℧B6106.0277.822.7A2℧c21℧B1105.5266.524.5A3℧c31℧B1111.2284.525.1A6℧c61℧B1105.1271.223.2A3℧c32℧B2110.6278.626.5A5℧c52℧B299.6250.723.7A6℧c62℧B297.1238.923.1A4℧c43℧B3105.6251.324.2A5℧c53℧B3104.3249.724.5A6℧c63℧B3103.2249.325.3A5℧c54℧B4116.5297.625.6A6℧c64℧B4102.5248.624.2A6℧c65℧B596.1244.723.1Average104.618263.72724.427Standard deviation5.565016.81641.5088Table 5
DNA sequences chosen to represent the solutions to the Chinese postman problem in Figure1.
3′−AAGCAGAAACTGAGGTCGTCACGGGGGTCGGGGAATGACAGCCAACCGAGATCGGGGAGCCAATGGGGGGCGTTTCAGGGGGTGTACGACCCTATGGGGAATGCTAGAGTGCTGGGGCCGAGATCCTCAATGGGGTGGGGGATGGGGTATCACAGGGGGCATAGCACGCCTGCCTCTGTGGGGGCGGGGATCAGCTAGGTAAATCAGCAGA−5′


## 6. Conclusions

Traditional silicon electronic computers can deal with simple types of computing problems, but they cannot deal with complex big data problems efficiently due to the limitations of the chip’s microprocessing ability and other factors. DNA molecules not only have the natural characteristics of specific hybridization and miniaturization but also have the ability of high-density information storage and powerful parallel computing, which makes DNA computing having natural advantages in dealing with difficult problems. In this paper, an algorithm based on the Adleman–Lipton model is proposed to solve the Chinese postman problem. DNA algorithm has the advantages of simple interpretation, simple coding, and high precision. Secondly, the computational complexity of the algorithm increases linearly with the scale of the problem. Due to the good parallelism of DNA computing, this method solves the Chinese postman problem withn vertices in On2 time complexity. Compared with the previous algorithms, it has made great progress and improvement. For example, Edmonds [10] and Johnson et al. [53] give a perfect matching algorithm about the minimum weight of CPP with the On3 time complexity. Kaj Holmberg [54] proposed a heuristic idea and improved it with the Frederickson method; the time complexity of the method is also On3. Kundeti et al. [55] showed that the cyclic CPP on bidirected graphs can be solved without reducing it to bidirected flow with OE2log2V time complexity. Gutin et al. [56] prove that the MCPP parameterized by the number of arcs is also fixed-parameter tractable, and solve it in time O2kn3, where n is the number of vertices in G. Nilofer and Rizwanullah [57] propose a combination of minimum matching algorithms, which create an Euler walk and Dijkstra algorithm to calculate short paths, and the computational complexity of the algorithms is between On2 and On4. The comparison results are shown in Table 6. By comparing the results, we can see that different algorithms will have a great impact on the computational efficiency due to the differences in computational complexity when solving large-scale Chinese traveling salesman problems. Especially with the increase of n, the difference will become more clear. Therefore, the improvement of computational efficiency is obviously conducive to the solution of large-scale problems.Table 6
Comparison of the computational complexity of different algorithms.
AuthorsTime complexityEdmonds and Johnson [53]On3Kaj Holmberg [54]On3Kundeti et al. [55]OE2log2VGutin et al. [56]O2kn3Nilofer and Rizwanullah [57]On2−On4Our algorithmOn2Moreover, our algorithm uses DNA as the basic element and unit of calculation, which has the characteristics of low energy consumption and large storage capacity compared with other algorithms. As DNA molecules are very tiny, a cubic meter of DNA solution can store nearly one trillion binary data. In addition, the energy consumption required for the reaction is very low. To complete the same computing operation, the energy consumption is one billion of that of supercomputers. It is conceivable that, with the expansion of the scale of the problem, there will be enough molecules to represent the element information in the problem. At the same time, the parallel chemical reaction of molecules has obvious advantages over the serial operation of computer. The parallel efficiency of DNA computing is amazing. The number of parallel operations of DNA strands can reach 10 to the 14th power per second. Of course, these advantages are based on the further development of DNA molecular manipulation technology. This also leads to the fact that although DNA computing has the advantage in computing time of molecular reactions, the preparation work of algorithm operation and the preparation work between experiments are seriously wasted. But from the perspective of development, with the maturity of DNA operation technology, the advantages of high parallelism, huge storage capacity, and low energy consumption response of DNA computing will be brought into play in the future. Now, DNA computing algorithms are mainly used to solve NP problems with exponential feasible solutions. Especially in the era of big data in the future, the scale of the problem to be solved, the amount of data and the number of feasible solutions are huge. In this case, ordinary computing algorithms are powerless. DNA computing just takes advantage of its own advantages to play its own advantages in such problems. In addition, the effective solution of this problem has certain reference significance and application performance for resource planning.However, our algorithm also has some shortcomings. Our algorithm to solve this problem is only compared with the classical algorithm, and the conclusion of comparison is relatively limited. The reason is that the main purpose of this paper is to show the characteristics and advantages of the algorithm in reducing the computational complexity of the problem algorithm, so we only compare it with the previous literature studies that have obviously proposed the computational complexity. The vast majority of literature studies mainly reveal the efficiency performance of the algorithm, while fewer literature studies clearly give the analysis of algorithm complexity. Therefore, our comparative literature studies are limited. On the other hand, DNA computing algorithm is mainly based on the biological DNA molecular chemical reaction to achieve the output of the algorithm function. Because the computer programs are executed in sequence, it is impossible to realize the parallel chemical reaction operation of molecules in the DNA algorithm. Therefore, the Python program designed by our simulation analysis can only realize the biological experiment results we designed. Compared with other algorithms (ant colony algorithm [33], particle swarm optimization algorithm [34], collaborative optimization algorithm [35], and genetic algorithm [36]), DNA algorithm is not ideal because of the different computing mechanism. Therefore, in the past papers on DNA computing, most of them explained the feasibility of the algorithm from the theoretical point of view [40, 43–45, 47, 48]. Of course, the problems raised by the reviewers are also the research direction of our efforts in the future, and we hope that the research work in this area can make a breakthrough.Because the various DNA operations used in the algorithm model can already be operated in the laboratory, the method can be put into practical application. Now, DNA computer has broadened people’s vision, accelerated the development of bioinformatics, brought corresponding problems, and put forward challenges to many fields. We believe that more efficient DNA algorithms can be used to solve more problems in future research.



---

*Source: 8814947-2021-01-16.xml*