Genetic algorithm in DNA computing: A solution to the maximal clique problem

Genetic algorithm is one of the possible ways to break the limit of brute-force method in DNA computing. Using the idea of Darwinian evolution, we introduce a genetic DNA computing algorithm to solve the maximal clique prob-lem. All the operations in the algorithm are accessible with todays molecular biotechnology. Our computer simulations show that with this new computing algorithm, it is possible to get a solution from a very small initial data pool, avoiding enumerating all candidate solutions. For randomly generated problems, genetic algorithm can give correct solution within a few cycles at high probability. Although the current speed of a DNA computer is slow compared with silicon computers, our simulation indicates that the number of cycles needed in this genetic algorithm is approximately a linear function of the number of vertices in the network. This may make DNA computers more powerfully attacking some hard computa-tional problems.