A New DNA Computing′s Algorithm for 3-Dimensional Matching Problem Based on Divide and Conquer Strategy

At present,it is how to decrease the DNA volume that plays an important role in the development of DNA computing.In this paper,for the objective to reduce the DNA volume of 3-Dimensional Matching Problem which is a famous NP-complete problem,an improved DNA computing model based on the operations in Adleman-Lipton′s model and the solution space of the sticker-based model is put forward.Then,the divide and comquer is introduced into the DNA computing and a new DNA computing′s algorithm is proposed.In a computer simulation,the DNA strands of maximum number required was O(1.414n),the time complexity was O(15×n+30×q),the test tube complesity was O(1) and the longest DNA strand was O(15n/2+45q).Hence,the scale of 3-Dimensional Matching Problem may be enlarged from 67 to 134.This new algorithm is highly space-efficient and error-tolerant compared to the conventional brute-force searching,and can be scaled-up to solve large and hard 3-Dimensional Matching Problem.By the approach,we can also show DNA computing′s vast potentials for resolving NP problems.