DNA计算机原理、进展及难点(Ⅰ):生物计算系统及其在图论中的应用

DNA Computer Principle, Advances and Difficulties (I):Biological Computing System and Its Applications to Graph Theory

基于生化反应机理的DNA计算机模型受到科学领域内许多不同学科学者们的关注与兴趣 .DNA计算已经形成国际科学前沿领域内研究的一个新的热点 .DNA计算机的研制需要诸如生物工程、计算机科学、数学、物理、化学、信息科学、微电子技术、激光技术以及控制科学等许多学科的共同协作攻关 .该系列文章拟对DNA计算机的基本原理、研究进展、DNA计算的模型以及当前研究中的难点给予研讨 .该文属首篇 ,重点讨论了DNA计算机的基本原理 ,引入了生物计算系统的概念 。

Biomolecular computing is computation at the molecular scale, using biotechnology engineering techniques. Recently, Many scientists in different fields are interest in DNA computer model based on reaction of biochemistry Because DNA computer has been formed a new science field. The studying and making DNA computer needs many science subjects such as biological engineering, computer science, mathematics, physics, chemistry, information science, micro electronics, laser technology, and control science, etc. Based on this, the advances of DNA computer are considered in detail in this four part paper such as fundamental principle, several models of DNA computing, and difficulties. In this paper, authors discuss the fundamental principle, introduce the notion of biological computing system, and summarize in detail the applications of DNA computing to some NP complete problems in Graph Theory and Optimizations, such as directed Hamiltonian Path problem, satisfaction problem, maximal clique and maximal independent problem, 0 1 programming problem, etc.