Abstract: In order to avoid the complexity of filtering the initial solution space and take full advantage of the superiority of sticker model in biological process, an improved DNA algorithm based on the sticker model has been designed. For the minimum dominating set and the minimum vertex cover problem, what has been designed here can generate the solution space composed of all the feasible solutions directly,making the space complexity less than O(2n) and being convenient to screen the optimal solutions. Finally, two concrete examples illustrate the feasibility of the new algorithm.

Key words: DNA computing, Sticker model, Minimum dominating set, Minimum vertex cover