Research On DNA Computing Methods Of Optimization Problems On Weighted Graph

For the research on DNA computing methods of optimization problems on weighted graph,the method of encoding weights in DNA strands is the key of solving the problems.In this paper,we discuss the DNA computing methods of classical optimization problems on weighted graph,such as the Chinese postman problem,the traveling salesman problem,the maximum-weight clique problem,and the minimum spanning tree problem.We improve the methods of encoding weights in the previous DNA computing models,and give some new DNA algorithms of solving these problems based on the improved DNA encoding methods.By designing the general edge graph of a weighted and undirected graph,we propose a DNA encoding method and the corresponding DNA computing model for the Chinese postman problem;by designing the relative length graph of a weighted graph,we give a new DNA encoding method and DNA computing model for the traveling salesman problem;by selecting the best ones of the reverse complement alignments of DNA sequences,we give a DNA encoding method and DNA computing model based on reverse complement alignment for the minimum spanning tree problem;and by improving the previous DNA encoding methods,we give some DNA computing models for the maximum-weight clique problem,the vertex cover problem and the 0/1 knapsack problem.The proposed DNA computing models improve the capability of representing and dealing with data in DNA strands.The specific research works are as follows.For the Chinese postman problem,we first propose the definition of general edge graph,and then devise a new DNA encoding method and DNA algorithm based on general edge graph.The DNA encoding method maps each edge on a weighted graph to one vertex by means of the edge-to-vertex map so as to construct the general edge graph of the weighted graph.Thus,the weights on the edges of the weighted graph are converted to the weights on the vertices of the general edge graph,and we can represent the weights using the lengths of DNA strands of encoding vertices so as to deal with the weights more easily than the previous methods.Specifically,for a weighted and undirected graph G=(V,E),we first convert it into its general edge graph G'=(V',E')through the edge-to-vertex map,where each vertex v'_i∈V' corresponds to one edge e_i of the graph G.If the edges e_i and e_j are adjacent in G,we link the vertices v'_i and v'_j in G';if the vertex v_i in G is an odd degree one,we add one self-loop to the vertices which are mapped from the edges linked to v_i.The length of DNA strand s_i,which is used to encode the vertex v'_i in G',is equal to the value of the weight on the edge e_i in G.The DNA strand s_ij,which is used to encode the edge e'_ij= (v'_i,v'_j),is the reverse complement of the concatenation of the last half of s_i and the first half of s_j.This DNA encoding method can improve the capability of representing and dealing with data in DNA computing models for optimization problems on weighted graph.For the traveling salesman problem,we first propose the definitions of order number of weight and relative length graph,and then devise a DNA encoding method based on relative length graph and an improved DNA encoding method.For a weighted and undirected graph G=(V,E),the proposed relative length DNA encoding method encodes weights in DNA strands according to the order number of weight and the relative length graph rather than the weights themselves.This DNA encoding method can directly deal with weights of integer or real number,even very small or very big weight,and the solution obtained in this method isn't proportional to the length of DNA strand since in this encoding method,the length of DNA strand used to encode weight is relative to the order number of weight rather than the weight itself.This makes the encoding method can deal with weights of wide range.The improved DNA encoding method uses two DNA strands of different lengths to encode each edge,where the longer DNA strand consists of the first segment,the weight segment and the last segment,and the shorter DNA strand is the reverse complement of the weight segment of the longer one.This encoding method is an improvement on the previous DNA encoding methods,and it can more easily find the optimal solutions than the previous ones since it generates stable DNA double strand instead of alternate DNA strand or double strand. For the minimum spanning tree problem,we devise a DNA encoding method based on recognition code of vertex and a DNA encoding method based on reverse complement alignment of DNA sequence,and then give the corresponding DNA computing models.Since nonlinear minimum spanning tree cannot be directly represented with linear DNA strand,we cannot directly design a DNA encoding method and DNA algorithm based on the basic DNA operations for the minimum spanning tree problem.For a weighted and undirected graph G=(V,E),the proposed DNA encoding method based on recognition code use one recognition code r_i of length l=max{[log₄n],6} to encode each vertex v_i and use one DNA strands s_ijof length 2p=2×max{w_ij,l} to encode each edg e_ijwhere the first part of length w_ijis marked with s_wij1,and the last part of length w_ijis marked with s_wij2.For any two adjacent edges e_ijand e_jk,we add one DNA strand s_aijk=-h(s_wij2S_wjk1)of length w_ij+w_jk as an additional code.Based on the proposed DNA encoding method,we give a DNA algorithm based on recognition code for the minimum spanning tree problem,which first obtains an Euler circle and then converts it into a minimum spanning tree. Furthermore,based on the relations of complement/non-complement and same orientation/reverse orientation between the bases in DNA double strand,we propose the definitions of complement alignment and reverse complement alignment and give a method of computing the scores of complement alignment and reverse complement alignment.And then we devise a DNA encoding method and a DNA algorithm based on reverse complement alignments for the minimum spanning tree problem.For a weighted and undirected graph G=(V,E),v_i∈V,e_ij∈E,1≤i,j≤n,where the weight on edge e_ijis w_ij,we use one recognition code r_i of length l=max{[log₄n],6} to encode each vertex v_i and use one DNA strands s_ijof length 2p=2×max{w_ij,l} to encode each edge e_ijAnd then we compute the reverse complement alignmentα_swij1,α_swjk2,α_rjof s_wij1,s_wij2,r_j,and select DNA strand s_aijk=Lower(α_swij2|α_rj+Lower(α_swjk1α_rj)as an additional code.Based on the proposed DNA encoding method,we give a DNA algorithm based on reverse complement alignment for the minimum spanning tree problem,which obtains a minimum spanning tree by means of Euler graph.This DNA encoding method can be generalized to other optimization problems on weighted graph.For the maximum-weight clique problem,we add weight representation in DNA strands on the basis of Ouyang's DNA computing model for the maximum clique problem,and then we give an improved DNA encoding method and DNA algorithm for the maximum-weight clique problem.For a weighted and undirected graph with weights on vertices,we use two DNA strands of different lengths to encode each vertex and use one DNA strand with a length of 20 to encode each edge.The longer DNA strand corresponding to vertex v_i consists of three parts and its center part is with a length of w_i;the shorter DNA strand is the reverse complement of the longer one's center part.Based on the DNA encoding method,we gave a DNA algorithm of solving the maximum-weight clique problem and its biological implementation.The proposed DNA algorithm is with space complexity of O(d_maxⁿ),where n denotes the number of the vertices on the given graph and d_maxdenotes the maximum degree of the vertices on it.In Ouyang's algorithm of solving the maximum clique problem,the space complexity is O(nⁿ).Since the degree of any vertex on a graph is always less than the number of the vertices on the graph,the space complexity in the proposed DNA algorithm is less than that in Ouyang's algorithm.Besides,we give DNA encoding methods and DNA algorithms for the 0/1 knapsack problem and the vertex cover problem.For the 0/1 knapsack problem,we do a little improvement on the previous DNA encoding methods so that it generates stable DNA double strands instead of alternant DNA strand or double strand in the single ligation reaction.For the vertex cover problem,we first improve the previous polynomial transformation from any instance of the vertex cover problem to that of Hamilton circle problem,that is,the cover subgraph with 12 vertices and 14 edges is changed to the improved cover subgraph with 4 vertices and 4 edges so that the number of vertices in the constructed graph G' is reduced to k+4|E| from k+12|E| and the number of edges is reduced to 6|E|+(2k-1)|V]from16|E|+(2k-1)|V|.And then we give a hybrid-based DNA algorithm for the vertex cover problem by means of the basic operations used in Adleman's experiments.Just as other arithmetical operations are implemented through converting them into addition operation in silicon-based computer,other operations in DNA-based computer should be converted to several basic DNA operations.Our work provides a certain foundation in this aspect of DNA computing.