Application of DNA Self-Assembly on 0-1 Integer Programming Problem

Self-assembly of DNA is an efficient method of executing parallel DNA computing where information is encoded in DNA tiles and a large number of tiles can be self-assembled via sticky end associations We investigate how basic ideas on tiling can be applied to solving 0-1 integer programming problem. It suggests that these procedures can be realized on the molecular scale through the medium of self-assembled DNA tiles. By creating billions of billions of copies of the participating DNA tiles, the algorithm will run in parallel on all possible solutions. The potential of DNA computing by self-assembly for the 0-1 integer programming problem is promising given the operational time complexity of O(m * n). This work shows further evidence for the ability of DNA computing to solve NP-complete problems