Linearly programmed DNA-based molecular computer operated on magnetic particle surface in test-tube

The postgenomic era has seen an emergence of new applications of DNA manipulation technologies, including DNA-based molecular computing. Surface DNA computing has already been reported in a number of studies that,however, all employ different mechanisms other than automaton functions. Here we describe a programmable DNA surface-computing device as a Turing machine-like finite automaton. The laboratory automaton is primarily composed of DNA (inputs, output-detectors, transition molecules as software), DNA manipulating enzymes and buffer system that solve artificial computational problems autonomously. When fluoresceins were labeled in the 5‘ end of (-) strand of the input molecule, direct observation of all reaction intermediates along the time scale was made so that the dynamic process of DNA computing could be conveniently visualized. The features of this study are: (i) achievement of finite automaton functions by linearly programmed DNA computer operated on magnetic particle surface and (ii)direct detection of all DNA computing intermediates by capiilary electrophoresis. Since DNA computing has the massive parallelism and feasibility for automation, this achievement sets a basis for large-scale implications of DNA computing for functional genomics in the near future.     

An autonomous molecular computer for logical control of gene expression

Early biomolecular computer research focused on laboratory-scale, human-operated computers for complex computational problems. Recently, simple molecular-scale autonomous programmable computers were demonstrated allowing both input and output information to be in molecular form. Such computers, using biological molecules as input data and biologically active molecules as outputs, could produce a system for 'logical' control of biological processes. Here we describe an autonomous biomolecular computer that, at least in vitro, logically analyses the levels of messenger RNA species, and in response produces a molecule capable of affecting levels of gene expression. The computer operates at a concentration of close to a trillion computers per microlitre and consists of three programmable modules: a computation module, that is, a stochastic molecular automaton; an input module, by which specific mRNA levels or point mutations regulate software molecule concentrations, and hence automaton transition probabilities; and an output module, capable of controlled release of a short single-stranded DNA molecule. This approach might be applied in vivo to biochemical sensing, genetic engineering and even medical diagnosis and treatment. As a proof of principle we programmed the computer to identify and analyse mRNA of disease-related genes associated with models of small-cell lung cancer and prostate cancer, and to produce a single-stranded DNA molecule modelled after an anticancer drug.     

DNA计算研究的新进展

DNA计算(DNA computing)是伴随着分子生物学的兴起和发展而出现的．作为一种全新的算法，DNA计算显示了其进行复杂运算的可行性．该文介绍DNA计算的机理，探讨了目前DNA计算的研究进展，并介绍了表面固定的生物计算和由输入DNA分子同时提供数据和燃料的生物分子自动机．     

Autonomous forward inference via DNA computing

Recent studies direct the researchers into building DNA computing machines with intelligence, which is measured by three main points: autonomous, programmable and able to learn and adapt. Logical inference plays an important role in programmable information processing or computing. Here we present a new method to perform autonomous molecular forward inference for expert system. A novel repetitive recognition site (RRS) technique is invented to design rule-molecules in knowledge base. The inference engine runs autonomously by digesting the rule-molecule, using a Class IIB restriction enzyme PpiI. Concentration model has been built to show the feasibility of the inference process under ideal chemical reaction conditions. Moreover, we extend to implement a triggering communication between molecular automata, as a further application of the RRS technique in our model.     

Autonomous forward inference via DNA computing

Recent studies direct the researchers into building DNA computing machines with intelligence, which is measured by three main points: autonomous, programmable and able to learn and adapt. Logical inference plays an important role in programmable information processing or computing. Here we present a new method to perform autonomous molecular forward inference for expert system. A novel repetitive recognition site (RRS) technique is invented to design rule-molecules in knowledge base. The inference engine runs autonomously by digesting the rule-molecule, using a Class IIB restriction enzyme PpiI. Concentration model has been built to show the feasibility of the inference process under ideal chemical reaction conditions. Moreover, we extend to implement a triggering communication between molecular automata, as a further application of the RRS technique in our model.     

广义分子计算模型在整数问题中的应用

分子计算是一种新型的并行计算模式. 作为信息载体和计算载体的DNA,生化反应时存在不可控性. 构建具有通用性的分子计算机存在许多困难和限制. 将分子计算黏贴模型与图灵机相结合,已提出一种不依赖于特定生物技术的广义分子计算模型(generalized turing model,GTM). 对GTM模型进行扩展,通过实验说明了该广义分子计算机能够在多项式时间内求解NP完全的整数规划问题,该模型具有编码简单、错误率低等特点.     

CFSM模型的有限自动机语义

研究CFSM模型的自动机语义,提出了一种从CFSM到自动机转换的算法。该算法的核心思想是构造一个包含控制自动机、输入自动机、输出自动机的有限状态自动机系统,利用自动机的同步性模拟CFSM的异步行为。本文的工作为进一步利用自动机理论和工具对CFSM模型进行分析和验证奠定了基础。     

DNA粘接计算模型及其应用

DNA计算是应用分子生物技术进行计算的新方法。应用形式语言及自动机理论技术研究DNA计算理论,有利于推动理论计算科学的发展。本文根据DNA分子的结构及特点给出了DNA分子的形式化描述,介绍了DNA粘接计算模型的文法结构和计算能力,并应用DNA计算方法求解3-SAT问题。     

分子生物计算在逻辑演算中的应用

DNA计算是一种基于生化反应机理的新型信息处理模式,与基于图灵机思想的电子计算机原理截然不同。近年来,DNA分子生物计算理论、实验技术的快速发展为DNA计算机的实现技术提供了一种新的理论和手段。文章首次尝试了DNA计算在逻辑演算中的应用,拓宽了DNA计算的应用领域。模型的最大优点是反应物可以在溶液中充分混合接触而进行生化反应,充分体现了DNA计算巨大并行性的优点,另外编码数和操作数都是线性增加的。     

二维二方向有限自动机的识别能力研究

研究了3种有限自动机,即二维二方向的确定型、非确定型以及Las Vegas有限自动机.证明存在语言能被二维二方向的Las Vegas有限自动机识别,但不能被相应的确定型有限自动机识别;存在语言能被二维二方向的非确定型有限自动机识别,但不能被相应的Las Vegas有限自动机识别.研究结果表明,二维二方向的Las Vegas有限自动机所识别的语言真包含确定型有限自动机所识别的语言;二维二方向的非确定型有限自动机所识别的语言真包含Las Vegas有限自动机所识别的语言.     

一种DNA计算系统的有限自动机模型

通过一个实例给出了粘贴系统模型的基本定义，讨论了粘贴系统模型的正则文法特性，并从自动机的角度给出了相当于正则文法表达能力的有限自动机模型。     

Solid phase based DNA solution of the coloring problem

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.     

非确定型有穷自动机的极小化

利用自动机状态集上的等价关系对自动机的状态集进行极小化, 从而得到与原自动机功能等价的极小化自动机. 通过两台确定型有穷自动机（DFA）的连接, 构造一台非确定型有穷自动机（NFA）. 利用这两台确定型有穷自动机状态集上的等价关系, 可以构造这台非确定型有穷自动机状态集上的等价关系, 从而对这台非确定型有穷自动机进行极小化. 结果表明这台非确定型有穷自动机的极小化自动机的状态复杂 度, 不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度; 并且自动机在等价关系基础上进行极小化时不改变识别语言.     

一种广义分子计算模型在集合覆盖中的应用

在分子计算原理和传统计算机模型基础上,提出了一种新的基于图灵机的广义分子计算模型,又称广义图灵模型,该模型的具体实现不依赖于特定生物技术. 模型继承分子计算大存储高并行的特点,通过时空复杂度转换,在求解NP完全问题上具有通用性. 模型由一台基本图灵机、一个只写带和一条工作带及读写网络这3部分组成,其中只写带和工作带之间存在一种特殊拓扑映射. 通过数据规模为4的集合覆盖问题,证明该算法能在多项式时间内求解集合覆盖问题,验证了算法和模型的有效性.     

有限制的通用模糊图灵机研究

给出了模糊图灵机的几种等价形式,包括具有分明转移函数的模糊图灵机(FNTMc)、模糊图灵机(FNTM)以及模糊多带图灵机.利用模糊图灵机,定义了模糊递归枚举语言与模糊递归语言,并给出它们的层次刻画,证明了不存在通用模糊图灵机;如果限制模糊集的隶属函数为单位区间[0,1]的固定有限子集D,对应的模糊图灵机称为限制型模糊图灵机,则存在通用的限制型模糊图灵机,而且这类图灵机可以以任意给定精度模拟其他模糊图灵机,从而通用模糊图灵机在逼近意义下是存在的.     

Fuzzy树自动机的等价性

在给出模糊树自动机概念的基础上,讨论了模糊树自动机与传统字符自动机、模糊有限自动机相类似的性质,即指确定性模糊树自动机与非确定性的模糊树自动机的等价性、FNBTA与FNTTA 等价,及FDBTA和FNBTA等价;这为模糊树自动机的进一步研究奠定了基础.     

构件化嵌入式软件设计的能耗性质分析与验证

从嵌入式软件设计模型层对构件化实时嵌入式软件系统中能耗相关性质进行研究,包括:扩展了实时接口自动机在能耗语义方面的描述能力,通过引入状态能量消耗率,建立了能耗接口自动机形式化模型以及自动机网络,用以建模嵌入式软件设计阶段系统构件及其构件组合的能耗行为特征;对能耗接口自动机网络的状态空间进行了形式化分析,构造了相应的可兼容整型空间的可达图,并在此基础上给出了最小能耗计算和最大能耗验证的算法.     

分子计算机的诞生与现状

介绍了计算机领域的一项最新成果———分子计算机 .分子计算机利用脱氧核糖核酸 (DNA)来进行计算 .腺嘌呤、鸟嘌呤、胞密啶、胸腺密啶 (核苷酸 )在计算中起了重要的作用 .使用限制内切酶、接合酶、转移酶、外切核酸酶、修饰酶来实现计算所需要的各种操作 .介绍了分子计算机完成的第 1个计算———解哈密顿通路问题的方法 ,用这种方法使NP完全问题在很短的时间内就得到解决     

基于DNA链置换反应的编码器逻辑运算模型研究

作为自组装DNA计算领域中一门新技术,DNA链置换反应在分子计算领域得到了广泛的应用.基于自组装DNA计算原理,设计了对应不同逻辑门的DNA分子电路.基于DNA链置换反应机理构建了编码器逻辑电路的分子计算模型.当输入DNA分子信号链时,将不同分子浓度比的DNA分子逻辑门电路混合,借助分子间的特异性杂交反应及分子间链置换反应,最终可输出信号链分子.Visual DSD仿真结果表明了本文设计的编码器逻辑计算模型的可行性与准确性.为拓展分子逻辑电路的应用做出有益的探索.     

幽默计算及其应用研究

幽默作为一种特殊的语言表达方式,是生活中活跃气氛、化解尴尬的重要元素。随着人工智能的快速发展,如何利用计算机技术识别和生成幽默成为自然语言处理领域热门的研究内容之一,并逐渐形成一个新兴研究领域:幽默计算。幽默计算致力于利用自然语言处理技术理解和识别包含幽默的文本表达,挖掘幽默表达潜在的语义内涵,构建面向幽默表达的计算模型。首先对当前幽默计算的背景进行概述,阐明幽默的可计算性和幽默计算对于人工智能的意义;在此基础上,对幽默研究的发展情况进行回顾,给出幽默研究的语言学基础;然后综述当前幽默计算在幽默识别和幽默生成两个方面的进展情况,分别给出针对幽默识别和幽默生成的计算框架;最后,对幽默计算在聊天机器人、机器翻译、儿童教育软件和外语教学等多个自然语言处理任务中的应用前景和应用模式进行展望。希望通过对幽默计算及其应用研究的总结和概述,完善现有幽默计算模型,增进计算机对于自然语言的理解,推动人工智能的进一步发展。