许进.生物计算机时代即将来临[J].中国科学院院刊,2014,29(1):42-54.

许进
,wujing@casipm.ac.cn

         生物计算机，非枚举型DNA计算机，并行型DNA计算机，大规模型DNA计算机，密码分析与破译，研究进展，发展建议

        biological computer, non-enumeration DNA computing, parallel DNA computer, large scale DNA computer, cryptanalysis and decipher, research progress, proposals

        生物计算机是以核酸分子作为“数据”，以生物酶及生物操作作为信息处理工具的一种新颖的计算机模型。生物计算的早期构想始于1959 年，诺贝尔奖获得者Feynman 提出利用分子尺度研制计算机；1994 年，图灵奖获得者Adleman 提出基于生化反应机理的DNA计算模型；在生物计算机方面突破性工作是北京大学在2007 年提出的并行型DNA计算模型，将具有61 个顶点的一个3-色图的所有48 个3-着色全部求解出来，其算法复杂度为359，而此搜索次数，即使是当今最快的超级电子计算机，也需要13 217 年方能完成，该结果似乎预示着生物计算机时代即将来临。文章重点介绍了生物计算机的产生背景及意义；DNA计算机，特别是中州I-型DNA计算机的基本原理、计算方法与步骤；DNA计算机的研究进展，特别指出在密码分析与破译等领域的应用；分析了DNA计算机的能力，指出了研究中的难点、 发展趋势，最后对我国生物计算机发展提出了一些建议。

        Biological computer is a novel computer model, which uses nucleic acid molecular as“data”and uses enzyme and biological operations as informational processing tools. In 1959, Feynman conceived a kind of computer in molecular scale. In 1994, Adleman proposed a DNA computing model based on biochemical reaction. The breakthrough of the biological computer is Peking University’s parallel DNA computation model, it was carried out in 2007, in which the 3-coloring problem of a 3-chromatic graph with 61 vertices was solved. The computation complexity is 359, which means that it would take 13217 years to complete the computation process even by the fastest supercomputer. This fact seems to herald the era of biological computer. In this paper, we mainly present the background and significance of biological computer, and give an instruction on the basic principles and calculation method of DNA computer, especially Zhongzhou I-type DNA computer. Then we briefly summarize its applications in the fields of cryptanalysis and decipher. Furthermore, we discuss the computational ability of DNA computers, and point out some difficulties in the study of biological computer. Finally, we predict the possible development trends of DNA computing in the future, and propose some advices to the further research on DNA computing in China.