Fast Parallel Solution for Set-Packing and Clique Problems by DNA-Based Computing

Michael (Shan-Hui) HO  Weng-Long CHANG  Minyi GUO  Laurence T. YANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.7   pp.1782-1788
Publication Date: 2004/07/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Hardware/Software Support for High Performance Scientific and Engineering Computing)
Category: Scientific and Engineering Computing with Applications
Keyword: 
biological computing,  molecular computing,  DNA-based computing,  

Full Text: PDF(978.7KB)
>>Buy this Article


Summary: 
This paper shows how to use sticker to construct solution space of DNA for the library sequences in the set-packing problem and the clique problem. Then, with biological operations, we propose DNA-based algorithms to remove illegal solutions and to find legal solutions for the set-packing and clique problems from the solution space of sticker. Any NP-complete problem in Cook's Theorem can be reduced and solved by the proposed DNA-based computing approach if its size is equal to or less than that of the set-packing problem. Otherwise, Cook's Theorem is incorrect on DNA-based computing and a new DNA algorithm should be developed from the characteristics of the NP-complete problem. Finally, the result to DNA simulation is given.