|
|||||
|
|
| Solid phase based DNA solution of the coloring problem | |
| 作者姓名： | PAN Linqiang LIU Guangwu XU Jin LIU Yachun |
| 作者单位： | Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China;Research Group on Mathematical Linguistics,Rovira i Virgili University,Pl. Imperial T?_rraco 1,43005 Tarragona,Spain,Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China,Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China,Department of Mathematical and Physical Science,Nanhua University,Hengyang 421001,China |
| 基金项目： | Supported by Spanish Ministry for Education,Culture and Sport (DGU-SB2001-0092),Chinese Postdoctoral Science Foundation,the National Natural Science Foundation of China (Grant No.60373089),and Huazhong University of Science and Technology |
| 摘 要： | DNA computing has the potential to tackle computationally difficult problems that have real-world implications.The parallel search capabilities of DNA make it a valuable tool for approaching intractable computational problems,for which conventional computers have limited potentials.Up to now,many accomplishments have been achieved to improve its performance and increase its reliability.In this paper,the coloring problem has been solved by means of molecular biology techniques.The coloring problem is a well-known NP-complete problem.This work represents further evidence for the ability of DNA computing to solve NP-complete problems. |
| 关 键 词： | DNA computing NP-complete problem coloring problem |
Solid phase based DNA solution of the coloring problem |
|
| PAN Linqiang,LIU Guangwu,XU Jin,LIU Yachun.Solid phase based DNA solution of the coloring problem[J].Progress in Natural Science,2004,14(5):459-462. | |
| Authors: | PAN Linqiang Liu Guangwu XU Jin LIU Yachun |
| Institution: | 1. Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China;Research Group on Mathematical Linguistics,Rovira i Virgili University,Pl. Imperial Trraco 1,43005 Tarragona,Spain 2. Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China 3. Department of Mathematical and Physical Science,Nanhua University,Hengyang 421001,China |
| Abstract: | DNA computing has the potential to tackle computationally difficult problems that have real-world implications.The parallel search capabilities of DNA make it a valuable tool for approaching intractable computational problems,for which conventional computers have limited potentials.Up to now,many accomplishments have been achieved to improve its performance and increase its reliability.In this paper,the coloring problem has been solved by means of molecular biology techniques.The coloring problem is a well-known NP-complete problem.This work represents further evidence for the ability of DNA computing to solve NP-complete problems. |
| Keywords: | DNA computing NP-complete problem coloring problem |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《自然科学进展(英文版)》浏览原始摘要信息 | |
| 点击此处可从《自然科学进展(英文版)》下载免费的PDF全文 | |