Molecular computations of the maximal clique problem using DNA self-assembly

In recent years, DNA self-assembly has widely developed in the fields of DNA computing and nanotechnology. Up to now, many kinds of DNA self-assembly structures have been applied to solve some computational problems. In this paper, a novel molecular computing model based on DNA self-assembly is developed to solve a maximal clique problem (MCP) with n-vertices. The assembled hairpin structure plays a key role in searching for the maximal clique. Our model has some significant advantages such as easy detecting, controllable automation and low algorithm complexity. For a graph with n-vertices, using our model, the time complexity is O(m+n), where m is the number of edges of the complementary graph. Moreover, this work demonstrates clear evidence of the ability of DNA computing to solve NP-complete problems.