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

Genetic algorithm is one of the possible ways tobreak the limit of brute-force method in DNA computing.Using the idea of Darwinian evolution, we introduce a geneticDNA computing algorithm to solve the maximal clique prob-lem. All the operations in the algorithm are accessible withtoday‘s molecular biotechnoiogy. Our computer simulationsshow that with this new computing algorithm, it is possible toget a solution from a very small initial data pool, avoidingenumerating all candidate solutions. For randomly generatedproblems, genetic algorithm can give correct solution withina few cycles at high probability. Although the current speedof a DNA computer is slow compared with silicon computers,our simulation indicates that the number of cycles needed inthis genetic algorithm is approximately a linear function ofthe number of vertices in the network. This may make DNAcomputers more powerfully attacking some hard computa-tional problems.

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.