A novel computing model of the maximum clique problem based on circular DNA  

作　　者：YANG Jing ZHANG Cheng XU Jin LIU XiangRong QIANG XiaoLi 

机构地区：[1]Institute of Software,School of Electronics Engineering and Computer Science,Key Laboratory of High Confidence Software Technologies,Ministry of Education,Peking University,Beijing 100871,China

出　　处：《Science China(Information Sciences)》2010年第7期1409-1416,共8页中国科学(信息科学)(英文版)

基　　金：supported by the National Natural Science Foundation of China (Grant Nos. 60533010, 30670540,60874036 and 60503002);the National High-Tech Research & Development Program of China (Grant No.2006AA01Z104);the Ph.D. Programs Foundation of the Ministry of Education of China (Grant No. 20070001020);the Postdoctoral Science Foundation of China (Grant No. 20060400344)

摘　　要：A novel DNA-based model is developed to calculate NP-complete problems, which is made of circular DNA molecules, streptavidin-coated magnetic beads and DNA circligase. To test the feasibility of the model, we apply it to compute a five-node maximum clique problem (MCP). During the computation, DNA molecule structures were transformed between linear DNA and circular DNA by streptavidin-coated magnetic beads and circligase, in order to search for the truth solutions. This greatly reduces the quantity of time and space consumed in calculation, and its time and space complexity both are O(n + m). Compared with the brute force method, using this algorithm searching process at most needs in n + 1 test tubes for an MCP with n vertices, while brute force method requires 2n test tubes. Furthermore, the constructed unenumerable initial solution space greatly improved the processing ability of the DNA computer. This novel model indicates that it may be a powerful DNA-based computer for solving some NP-complete problems.A novel DNA-based model is developed to calculate NP-complete problems, which is made of circular DNA molecules, streptavidin-coated magnetic beads and DNA circligase. To test the feasibility of the model, we apply it to compute a five-node maximum clique problem (MCP). During the computation, DNA molecule structures were transformed between linear DNA and circular DNA by streptavidin-coated magnetic beads and circligase, in order to search for the truth solutions. This greatly reduces the quantity of time and space consumed in calculation, and its time and space complexity both are O(n + m). Compared with the brute force method, using this algorithm searching process at most needs in n + 1 test tubes for an MCP with n vertices, while brute force method requires 2n test tubes. Furthermore, the constructed unenumerable initial solution space greatly improved the processing ability of the DNA computer. This novel model indicates that it may be a powerful DNA-based computer for solving some NP-complete problems.

关 键 词：DNA-based computing model circular DNA molecules NP-complete problem circligase streptavidin-coated magnetic beads 

分 类 号：O242.1[理学—计算数学]