DNA计算原理与发展

DNA计算是一种摸拟生物分子DNA的结构并借助分子生物技术进行计算的新方法,为NP完全问题的解决提供了一种全新的途径,具有广阔的应用前景。本文首先介绍了DNA计算的基本思想;然后综述了DNA算例及其模型;指出了DNA计算的应用及目前存在的问题;最后对DNA计算的发展前景进行展望。     

图的k着色问题的DNA计算模型

DNA计算是一种新的并行计算模式,在解决NP完全问题等方面具有很大的优越性．利用DNA计算的计算特性给出了一个图的k着色问题的DNA计算模型,该算法最多需要3kn（n-1）/2＋6个生物操作即可求出图的色数及相应的着色模式．     

图的最小顶点覆盖问题的质粒DNA计算模型

给出了图的最小顶点覆盖问题的质粒DNA算模型及其实现算法．算法的时间复杂性是O(q),编码最小覆盖问题所需的核苷酸片段种类为n,其中n,q分别是图的规模和边数．在算法中,所用酶的种类也等于图的规模．而且,算法不需要复杂的单链DNA自身退火反应和PCR扩增．     

求解K-闭包问题的DNA算法

给出了解决K-闭包问题的DNA算法，进一步表明了用DNA计算来解决NP-完全问题是非常有前景的。     

解决NP问题的DNA编码技术

NP问题是密码学中的一个难题,用DNA计算解决NP问题是目前DNA密码研究的一个热点。文章阐述了DNA编码问题及约束条件,归纳出用DNA计算解决NP问题的基本步骤,分析了Adleman解决哈密尔顿回路问题的实验中DNA编码的质量,提出了可选的更好的编码,并总结了目前DNA编码研究中存在的问题。     

DNA计算及DNA计算机的研究进展

概述了DNA计算的基本原理、DNA计算的应用和DNA计算机的研究进展及存在问题，基于DNA生化反应的计算机称为DNA计算机，由于其采用一种完全不同于传统计算机的运算逻辑与存贮方式，DNA计算机在解决某些复杂问题时具有传统计算机无法比拟的优势，目前国际上关于DNA计算和DNA分子生物计算机的研究方兴未艾，极大地推进了DNA计算机的研究过程。     

DNA计算在图论中的应用

介绍了DNA计算在图论中应用的一些结果.如中国邮递员问题的DNA计算模型;0-1规划的DNA计算模型最大团问题;图着色问题和最小覆盖问题的表面DNA计算模型等.     

背包问题的三链DNA计算模型

背包问题是组合优化中很重要的NP问题。因为三链DNA的特殊结构在参与反应时可以减少计算模型的错解率,且在生化反应中利用磁珠分离法对解进行分离较方便准确,文章利用三链模型求解0-1背包问题和完全背包问题。首先将背包问题的约束条件进行分解,再将物品质量编码为DNA片段,链接反应后,利用凝胶电泳技术和三链模型检测所包含的物品组合,得到满足约束条件的物品组合,再利用此方法检测价值最大的组合,即问题的解。其他的背包问题也可用此方法来解决。     

一类复合并行机排序问题计算复杂性研究

研究确定性排序理论的一个新模型：考虑４台机器的集合Ｍ＝（Ｍ１，Ｍ２，Ｍ３，Ｍ４）和ｎ个零件的集合Ｊ＝（ｊ１，ｊ２，…，ｊｎ），每个零件同时被２ｉ＝（ｉ＝０，１，２）台机器同时加工。证明了在不允许间断，优化指标为作业排序长度的条件下，该问题是强ＮＰ－完全问题，没有多项式时间算法。     

DNA计算中编码问题的研究

编码是DNA计算的开始,对DNA计算尤为的重要。编码的好坏直接影响计算反应过程的质量。本文简要描述了DNA编码的理论,总结了编码的约束条件和几个模型的DNA序列的设计。最后,指出了编码问题的研究方向。     

基于改进的粘贴模型求解图最大独立集的DNA算法

改进的DNA粘贴模型在解决SAT问题时所需的寡核苷酸片段数量有显著降低,对改进的粘贴模型做了进一步的改进,建立了图最大独立集的一种改进的DNA粘贴模型.首先将图的独立集问题转化为可满足性问题,然后利用本文改进的粘贴模型给出了图的最大独立集的DNA算法.最后通过一个实例给出算法实现并求出了最大独立集.     

DNA计算的应用与展望

DNA 计算机是当前研究的热点问题，我国的研究刚刚起步，本文详细论述了DNA序列的概念及性质，DNA计算的原理，同时介绍了DNA计算的研究进展概况。     

最大匹配问题的三链DNA计算模型

三螺旋结构的DNA链具有稳定性,在一定条件下易分解等特点,因此得到的三链模型具有错解率低的优点。利用三链模型来讨论最大匹配问题,拓展了DNA计算解决问题的方法和应用领域。     

DNA计算的研究现状与展望

基于硅材料的微电子技术由于工艺技术和基本理论上的局限,使得现有电子计算机无法满足科技发展对计算能力的需求.由于具有超强的并行运算能力和巨大的数据存储能力,DNA计算始终是新型计算机领域研究的热门.DNA计算的研究已经涉及到DNA计算模型、 DNA计算机系统、 DNA计算的应用等诸多方面.文章从DNA计算流程、DNA计算模型、DNA计算机、DNA计算应用研究等几个方面,综述了DNA计算研究的现状.同时,也指出了DNA计算存在的问题,并从DNA编码设计、DNA计算噪声控制等方面阐述了未来研究方向.相信随着生物技术、纳米技术等的进一步发展,DNA计算一定能够发挥出自身的优势和潜力,能够为国防建设、信息安全、基础科学研究、生命科学研究等方面提供更好的服务.     

最大团问题的三链DNA计算模型

本文研究利用三链DNA求解最大团问题。首先将最大团问题中的顶点编码为DNA片段,进行生化反应,组合成所有可能的情况,然后利用三链模型对解进行筛选,最终得到图的最大团。该模型降低了编码的复杂度,提高了检测效率,其他的NP(Non-deterministic Polynomial)问题也可用此方法来求解。     

DNA Tile计算简述

自1953年Watson和Crick首次提出DNA双螺旋结构以来,DNA作为遗传物质、信息载体和纳米材料被广泛研究,并成为多个领域的研究对象,如基因工程、DNA酶、生物信息学、信息存储、DNA纳米技术等.DNA作为一种天然的纳米材料,具备自组装的能力(A-T、C-G),使其在纳米结构领域成为备受瞩目的材料之一.以DNA构建的纳米结构形态不一,其构建的方法则主要分为两种:DNA Tile和DNA折纸.文章主要阐述DNA Tile的发展历程及其在纳米结构构建领域的应用,并着重介绍DNA Tile在计算领域的广泛应用.     

求解接点网络问题的DNA算法

利用DNA的二级结构——发卡构形，给出了求解接点网络问题的DNA算法．首先用DNA分子编码接点网络问题，然后利用DNA分子的自组装和形成二级结构的能力来求解问题．算法具有自动化实现计算的特点，计算所需的实验操作比Lipton提出的算法少，同时计算所需的DNA量也比Lipton提出的算法少．     

DNA粘接计算模型及其应用

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