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 problem. All the operations in the algorithm are accessible with today's 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 computational problems.
作 者： LI Yuan Fang CHEN OUYANG Qi 作者单位： Center for Theoretical Biology and Department of Physics, Peking University, Beijing 100871, China 刊 名： 科学通报(英文版) SCI 英文刊名： CHINESE SCIENCE BULLETIN 年，卷(期)： 2004 49(9) 分类号： Q5 关键词： DNA computer genetic algorithm NP-complete problem