Читать книгу DNA- and RNA-Based Computing Systems - Группа авторов - Страница 18

In 1994, Adleman [2] used the DNA for computation in the first‐ever molecular experiment performed to solve the HPP. Molecular biology experiments were performed to address the instance graph having seven vertices and fourteen edges. A year later, Lipton [3] presented a new model for solving another NP‐complete (nondeterministic polynomial time complete) problem known as satisfiability (SAT) problem using a DNA computer. SAT problem is also solved by Smith et al. [4] and Liu et al. [6] with new surface‐based DNA computing models.

Along with these models, other researchers [7,11,12] also solved NP‐complete problems with a different approach. Sakamoto et al. [5] used DNA hairpin formation to solve the SAT problem. Chao et al. [13] developed a single‐molecule “DNA navigator” to solve a maze. These models of DNA computing are discussed in the next section.