An O(1.414\+n) Volume Molecular Solutions for the Exact Cover Problem on DNA-Based Supercomputing

The scalability problem in DNA computer has been one of the important research areas in DNA computing. According to the requirement of the DNA parallel computing for exact cover problem, a DNA model for good scalability is proposed, which is based on the biological operations in the Adleman-Lipton model and the solution space of stickers in the sticker-based model by simultaneously taking the method of fluorescence labeling and the technique of gel electrophoresis into the model. Based on this model, a DNA-based algorithm for the exact cover problem, by making use of the strategem of divide-and-conquer, is also proposed which consists of three sub-algorithms: Init(), IllegalRemove(), and ParallelSeacher(). Compared with by far the best molecular algorithm for the exact cover problem with n variables and m sets in which O(2\+n) DNA strands are used, this algorithm can solve the same problem only using O(1.414\+n) DNA strands on the condition of not varying the time complexity. Therefore, the cardinal number of the exact cover problem that can be theoretically resolved in a test tube may be enlarged from 60 to 120, and thus the proposed algorithm is an improved result over the past researches.