Advanced Search
    Li Kenli, Liu Jie, Yang Lei, Liu Wenbin. An O(1.414\+n) Volume Molecular Solutions for the Exact Cover Problem on DNA-Based Supercomputing[J]. Journal of Computer Research and Development, 2008, 45(10): 1782-1788.
    Citation: Li Kenli, Liu Jie, Yang Lei, Liu Wenbin. An O(1.414\+n) Volume Molecular Solutions for the Exact Cover Problem on DNA-Based Supercomputing[J]. Journal of Computer Research and Development, 2008, 45(10): 1782-1788.

    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.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return