基于DNA粘贴系统的可满足性问题研究

发布时间：2018-01-23 11:49

本文关键词： DNA计算粘贴系统可满足性问题 Adleman实验　出处：《伊犁师范学院》2012年硕士论文　论文类型：学位论文

【摘要】：DNA计算是生物计算中最受关注的一种计算,目前的DNA计算领域始于1994年Adleman的著名实验. DNA分子巨大的并行计算能力使得在多项式时间内解决NP完全问题成为可能.本文探讨了形式语言的一些性质,并采用基因生物技术,通过DNA计算给出了粘贴系统可满足性问题的一些算法. 本文分三个部分进行论述:第一章介绍形式语言和乔姆斯基文法,给出形式语言的相关概念,并对乔姆斯基文法做了相关介绍. 第二章首先介绍DNA计算的产生背景,研究状况,生物学基础, DNA计算解决4Hamilton路径的基本原理和操作方法.其次指出DNA计算机的优点,应用前景与存在的技术问题. 第三章给出了Adleman实验第一个是基于Adleman实验的计算方案.第二个是利用粘贴模型给出了粘贴系统的解决方案,第三个是构建可以处理可满足性问题的粘贴系统模型.
[Abstract]:DNA computing is one of the most concerned calculations in biological computing. The current field of DNA computing began with Adleman's famous experiment in 1994. The huge parallel computing power of DNA molecules makes it possible to solve NP-complete problems in polynomial time. Some properties of formal languages are discussed in this paper. Some algorithms for the satisfiability of sticker system are given by using genetic biotechnology and DNA calculation. This paper is divided into three parts: the first chapter introduces formal language and Chomsky grammar, gives the related concepts of formal language, and introduces Chomsky grammar. The second chapter introduces the background, research status and biological basis of DNA calculation. The basic principle and operation method of 4Hamilton path are solved by DNA calculation. Secondly, the advantages, application prospects and technical problems of DNA computer are pointed out. In the third chapter, the first one is based on the Adleman experiment, the second is the solution of the paste system based on the sticker model. The third is to build a paste system model that can handle satisfiability.
【学位授予单位】：伊犁师范学院
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP384

【参考文献】