An Algorithm in Tile Assembly Model for Maximum Clique Problem

DNA computing is an efficient method to solve computational problems, especially for NP complete problems that cannot be efficiently solved using the traditional Turing machine. However, with the development of DNA computation, it presently suffers from several challenging problems such as relatively high error rates, DNA space explosion, etc. How to decrease error rates has become an important issue for DNA computation. To solve the maximum clique problem which is an NP complete problem, with low DNA hybridization error rates, this paper introduces a DNA self-assembly model and presents a novel DNA computing algorithm. This algorithm decreases error rates by decreasing experiment operations. Moreover, the DNA structures of initial molecular, regular molecular and detection molecular are designed, and encoding scheme of DNA molecular is described, too. The proposed algorithm needs Θ(n+|E|) types of tiles and Θ(1) times of experiment operations, where n and |E| are the numbers of vertex and edge of a graph respectively. According to the analysis, our algorithm can not only improve the accuracy of the solutions, but also greatly reduce the complexity of the experiment, which leads to easier experiment operability, as compared with the other DNA models including sticker model, insert-delete system, etc.