DNA Computing Model Based on a New Scheme of Encoding Weight for Chinese Postman Problem

Weight encoding method is an important but challenging issue in DNA computing. A new DNA encoding scheme to represent weights on a weighted graph is devised inthis paper and a corresponding DNA algorithm for the Chinese postman problem is proposed using the encoding scheme. The random procedure of generating various paths in the DNA algorithm is analyzed by means of Markov chain. For any weighted graph G=(V,E), it is firstly converted into its general edge graph G′=(V′,E′) through mapping from edges to vertices. Each edge e\-i in G is mapped as a vertex v′\-i in G′, and the vertices v′\-i and v′\-j in G′ are linked if e\-i and e\-j are adjacent in G. If v\-i in G is an odd degree vertex, the self-loops are added to the vertices in G′ which are mapped from the edges linked to v\-i. The length of DNA strand s\-i, which is used to encode vertex v′\-i, is equal to the value of weight on edge e\-i. The DNA strand s\-\ij\, which is used to encode edge v′\-iv′\-j, is the reverse complement of the second half of s\-i and the first half of s\-j. The proposed DNA encoding scheme has characteristics of easy encoding, easy generalizing and low error rate. This work improves the capability of representing and dealing with data and extends the range of solving numerical optimization problems in DNA computing.