【作者】 张征；

【导师】 许进；

【作者基本信息】 华中科技大学 ， 系统分析与集成， 2007， 博士

【摘要】 DNA分子计算的工作原理是对生物系统进行编码,以生物化学反应为基础,利用生物技术实现生物系统的状态转移来实现计算过程。自从Adleman博士1994年成功地给出用DNA计算方法求解有向图的Hamilton有向路问题以来,在短短的10多年内,DNA计算引起了学术界的广泛关注,取得了丰硕的成果。DNA计算具有并行度高,能耗低的特点。利用DNA计算的方法构造的分子自动机是一种纳米尺度的计算机构,与传统的DNA计算的不同之处在于,它能够实现自动机的功能,在纳米尺度进行高度并行的逻辑、推理等运算。因此分子自动机提供了一种研究DNA计算和纳米计算的新思路,对其进行编码理论和运行机理上的研究将有助于开拓DNA计算新的应用领域。本文的主要工作包括:首先分析了Yakoov等人构造的分子有限自动机,总结出该种分子有限自动机的硬件(限制性内切酶)、软件(状态转换分子)、有限自动机的状态以及字符之间的相互制约的关系。根据这一结果编制出了相应的计算机软件,该软件可以在构造该类型的分子有限自动机时,辅助进行字符编码和状态转换分子编码。在该软件的辅助下构造出状态和字符更多的分子有限自动机,其计算能力较yaakov等人设计的分子有限自动机要强。接着提出了一种新的分子下推存储器的模型。首先利用一类特殊的限制性内切酶实现了延长DNA分子链的功能。该类限制性内切酶的特点是具有2个回文结构的识别位点,并且切割位点在2个识别位点之间。接着利用该特性构建了简单的分子存储器,研究了其存储和读取机理,并通过改进编码使这种存储器具有一定的编程能力,从而实现了按一定规律存储字符信息的下推存储器。通过分析表明,这种分子存储器的可编程能力和存储效率除了与所使用的限制性内切酶的特性有关外,还受分子存储器编码的影响,并得出了分子存储器存储效率最高或者编程能力最强的编码方式。研究表明该种下推存储器模型也可以视为一种特殊的有限自动机模型(非全状态转换),通过引入合适的调节分子,可以将其扩展为全状态转换的可编程有限自动机。这种有限自动机模型优点在于:初始DNA分子的合成较为简单;通过分子链的延长而非缩短来实现状态转换,这种状态转换机理可使计算步骤更多;最重要的是它能同时进行状态转换与数据存储,从而可以保存状态转换的历史信息。进而提出了一种分子下推自动机的模型。计算理论表明,具有一个下推存储器的有限自动机的计算能力较单纯的有限自动机强。通过将前述分子下推存储器引入到的分子有限自动机的运算中,获得了计算能力更强的分子下推自动机。最后讨论了分子自动机可能的应用。分子有限自动机的计算能力暂时还不能与电子计算相比,但是分子自动机是纳米计算机的一种,有其自身的优点,有望运用于一些特殊的场合。文中介绍了一些简单的理论计算的例子,同时对其可能的应用领域进行了说明。由于有限自动机可以用于信息加密和解密,因此分子有限自动机也可以实现类似的功能;而利用分子有限自动机进行疾病诊断则是一个较有前景的应用方向。可编程分子存储器可以用于存储信息,同时也可以用于构造一些分子池,文中以构造图顶点着色问题的分子池为例介绍了具体的构造方法。通过改进分子下推存储器可以构造出分子振荡器,进一步的可以作为微量检测的一种手段。更多还原

【Abstract】 DNA computing aims at using nucleic acids for computing. Since Adleman’s successful solution of a seven-vertex instance of the NP-complete Hamiltonian directed path problem by a DNA algorithm initiated the field of biomolecular computing in 1994. In the past ten years, both the theory and the experiment method of DNA computing were improved greatly.DNA solutions can act as billions of parallel nanoprocessors with few consume. The biomoluclar automata base on DNA computing is a kind of nano-computer. It’s difference to the original DNA computing that This DNA computing model can realized the base function of automaton.An automata made of biomolecules can combine the strongpoint of the DNA computing and electrical computing. It can also improve the practicability of DNA computer and extend the application of DNA computing.In this paper, the restriction enzymes were analyzed for detail it infection to construct a finite automata made of biomolecules. Base on this result, a finite automaton with more state and symbol had been constructed.Here a new finite automata made of biomolecules was described, which can be used as a programmable pushdown store. A new kind of restriction enzyme was used in this model. Which have two recognition sites and cut side between two recognitions? The basic mechanism of a simple pushdown store and an improved pushdownstore was studied. The programmable ability and the efficiency of this kind of pushdown store are influenced by the coding of the Symbol biomolucule and the restriction enzyme. Base on this result, a special enzyme and a suitable coding must be choosen to maximize the programmable ability and the efficiency of the biomolucula pushdown store. This pushdown store is also a programmable automaton. A tag molecule should be used to extend the pushdown store to a completely programmable automaton. This programmable automaton gains the advantage over the basic one. Such as simplify the coding, increase the step of computing and keep the transition information.Bimolecular pushdown automatons can construct with a finite automaton and a pushdown store. Obviously, the pushdown automaton is more powerful than the finite automaton.The application of bimolecular automaton is discussed in this paper too. The power of bimolecular automaton is less than electronic computer now. But the bimolecular automaton can used in some special area for it’s a nano-meter computer. Such as diagnosis and treat the disease, detect atom material and use in encrypt the information etc. It’s also can used too store some information, construct some bimolecular pool etc.更多还原