Solid phase based DNA solution of the coloring problem

摘要

DNA computing has the potential to tackle computationally difficult problems that have real-world implications. The parallel search capabilities of DNA make it a valuable tool for approaching intractable computational problems, for which conventional computers have limited potentials. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. In this paper, the coloring problem has been solved by means of molecular biology techniques. The coloring pro blem is a well-known NP-complete problem This work represents further evidence for the ability of DNA computing to solve NP-complete problems.