A DNA Strand Displacement-Based Computing Model for Solving Intractable Graph Problems

Graphs are the primary means of describing the relation between individuals in society, and have been extensively used for analysing various types of networks, such as social networks, biological networks, and electric networks. Many practical problems can be abstracted to graph problems, and cannot be solved efficiently due to their NP-hard nature. DNA computing, leveraging the vast parallelism and high-density storage of DNA molecules, provides a new way for solving intractable problems. However, existing DNA computing models are limited by single computing function. This paper proposed a novel DNA computing model with two DNA modules-a graph representation module (GRM) and a detection module (DM)-that can solve a variety of NP-hard problems. To show the feasibility of the proposed model, we conducted simulation and biochemical experiments on multiple NP-hard problems, such as the minimum dominating set, maximum independent set, and minimum vertex cover. Experimental results showed that the GRM is a universal graph representation module, based on which multiple graph problems can be solved by cascading a proper designed detection module. Our method also highlighted the potential for DNA strand displacement to act as a computation tool to solve intractable graph problems.