A surface-based DNA algorithm for the maximal clique problem

The maximal clique problem is an NP (nondeterministic polynomial time)-complete problem. We present an algorithm that solves maximal clique problem within the framework of a surface-based model of computation. The time complexity of our algorithm is O(n(2)), and the number of kinds of short oligonucleotides needed to encode maximal clique problem is n + 3, where n is the size of the graph. In our algorithm, immobilizing DNA (deoxyribonucleic acid) strands to a solid surface reduces the possibility of error resulting from the loss of DNA strands in solution. A solution-based algorithm solving maximal clique problem has previously been proposed by Qi Ouyang et al.. In their algorithm, the number of enzyme is equal to the number of vertices of the graph, which causes the difficulty of encoding and scaling up, because the DNA sequences of restriction enzyme sites should not be present in otherwhere. Using surface-based model, we designed an algorithm for maximal clique problem, which needs only one enzyme.