基于DNA计算的指派问题

给出了推广的闭环DNA计算模型及其生化实验.用闭环DNA计算模型设计出了指派问题的DNA算法.对决策变量进行4组DNA编码来存放决策变量和效益值;通过有目的的终止技术和删除实验得到指派问题的全部可行解;通过批接入实验、电泳实验和检测实验获得最优指派问题的最优解.举例说明了算法的可行性.最后讨论了推广的闭环DNA计算模型的应用前景和不足之处.     

最大权匹配问题的闭环DNA算法

给出并证明了在DNA计算中处理实数问题的策略,即首先在误差限范围内用有理数集合代替实数集合;再取出与有理数集合一一对应的最小的整数集合.针对赋权匹配问题,给出了基于闭环DNA计算模型的赋权匹配问题算法.该算法首先按边进行三组编码并合成初始闭环DNA;再以相邻两条边为约束条件用删除实验获得所有匹配,并用电泳实验得到所有最大权匹配,最后用检测实验输出最优解.证明了算法的正确性,讨论了算法复杂度,并以一个例子说明了算法的有效性.     

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

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

集合覆盖问题闭环DNA算法

介绍了闭环DNA计算模型及其生化实验,分析了集合覆盖问题及其数学模型.根据任何一个元素至少属于一个集合构成可行集合覆盖的原理,设计了集合覆盖问题闭环DNA算法,该算法首先对集合的0-1决策变量按照0和1的取值、对应的价值系数进行两组DNA编码并形成所有可能解;再用接入实验和删除实验筛选出全部可行解;然后用接入实验得到这些可行解的目标函数值,并用电泳实验得到全部最优解;最后通过检测实验输出所有最优解.首次提出基于电泳技术检测实验以"接入-电泳-删除"为实验顺序,可以检测多种DNA编码.算例说明了算法的有效性.     

基于批分离实验的最大独立集问题DNA算法

根据解决最大独立集问题的需要,讨论了简化的粘贴模型,该模型只由单链DNA的存储链和分离板组成.以分离实验为基础提出了批分离实验和生化操作过程,该实验可以快速分离存储链.基于批分离实验设计了最大独立集问题的DNA算法,并给出其生化实现过程:先形成所有顶点子集的初始解空间;接着用批分离实验对每个顶点进行检测,筛选全部满足不相邻要求的顶点子集,从而得到全部独立集;然后通过电泳实验得到全部最大独立集;最后通过检测实验输出实验结果.讨论并证明了算法的正确性和复杂性,算法的操作次数是线性的,通过仿真实验说明了算法的有效性和可行性.     

基于生物芯片技术的地图四着色问题的DNA算法

基于先进的生物芯片技术、多种荧光标记技术和DNA计算理论提出了解决地图四着色问题的DNA算法,通过一个实例阐述了具体的DNA操作步骤,并对生化实验进行了计算机模拟,给出了所有可行的着色方案,证明了该算法的可行性。与已有的模型相比,该模型在解的准确性、计算复杂度以及操作的自动化方面都表现出了很强的优势。     

最小生成树DNA算法

为了改进粘贴模型,提出了用生化实验实现求解割集的计算方法,并基于该方法给出了最小生成树DNA算法.首次将分离实验扩展为基于分离板的分离实验和基于电泳技术的分离实验,所提出的最小生成树DNA算法打破了DNA计算的计算模式——用求解割集的最小边的方法逐步产生最小生成树.用该方法求解割集利用了分离实验运算的高度并行性,最小生成树DNA算法的时间复杂度是线性的,从而降低了算法的时间复杂度.     

移动Ad Hoc网络QoS路由的闭环DNA计算模型

提出针对移动Ad Hoc网络QoS路由问题的闭环DNA计算模型.对每条路径进行弧、费用、探针的3组编码,再采用有目的的终止技术合成所有从起点到终点的弧首尾相连路径,然后通过接入实验和电泳实验得到费用最小路径,并通过检测实验输出所有费用最小路径,同时给出了算法的生化实现过程.实验结果表明:在不增加算法复杂度情况下获得了QoS路由问题的最优解.     

基于粘贴和删除系统求解旅行商问题的DNA算法

旅行商问题（Traveling Salesman Problem,TSP）是一个典型的NP完全问题.粘贴和删除模型是DNA计算的两个基本计算模型.结合上述两个模型的优点,构造粘贴-删除模型,并利用该模型给出求解旅行商问题一种新的DNA算法.     

基于“DNA折纸术”设计图着色问题的解决方案

色数是图论中的一个重要的参数,其属于著名NP(Non-deterministic Polynomial)-完全问题范畴.巨量的着色方案使验证变得相当困难,以至于在传统计算机上无法实现.目前已经有多种算法用于研究图定点着色问题,比如遗传算法,粒子群算法,神经网络算法和模拟退火算法等.随着DNA自组装技术与DNA计算机研究的展开,一些NP-完全问题以及NP-难问题的计算模型被相继提出.除了传统的DNA分子结构被用作计算材料外,其他的DNA分子结构也被用于分子生物计算,比如质粒DNA分子、分子信标结构以及DNA Tile等.采用DNA纳米折纸结构编码信息,借助于纳米结构之间的粘性末端进行自组装,给出了一种非确定性的图着色模型.通过创建数以亿计的参与计算的DNA纳米折纸结构,该算法可以并行的测试每种可能的着色方案.     

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

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

以病毒的230 kb DNA分子为模板的DNA序列测定

目的：为确认Tn3-gpt已插入小鼠巨细胞病毒(mouse cytomegalovirus，MCMV)基因组的特定位置，改进大分子病毒DNA的测序方法，建立以230kb DNA为模板直接进行DNA序列测定的方法。方法：待测MCMV的Tr3-gpt插入突变株感染NIH3T3细胞后，从培养液中制备病毒颗粒并从中纯化得到基因组DNA，以此DNA为模板，合成的寡核苷酸为引物，用热循环方法按Promega公司的DNA Cycle Sequencing System试剂盒的方法进行测序。结果：获得纯度较高可直接作为模板进行测序的：DNA，测序所得放射自显影图片条带清晰明亮，间隔正常，分辨率较高，可顺利读出插入位点的MCMV的DNA序列，证实Tn3-gpt插入在特定的位置。结论：长达230kb的大分子病毒DNA可直接作为模板，用热循环测序方法进行测序，无需切割成小片段后才进行测序。     

DNA计算机

脱氧核糖核酸（简称DNA）是生物体内的一种具有双螺旋结构的遗传物质,用DNA可以进行运算,即构成的DNA计算机能很快地求解复杂的问题;以DNA编码为信息的载体,DNA计算机中的输入和输出设备都是DNA的,链用一系列二进制的数代表所求问题中的变量,用DNA中特有的寡核苷酸序列表示这些二进制的数,再将DNA利用分子生物和化学组装技术组装到芯片上,利用DNA杂交化学方法,排除各种代表不正确解的寡核苷酸序列,最后通过聚合酶链式反应（PCR）和各种检测技术读出保留在芯片上的DNA序列,读出的DNA序列所代表的二进制数即为所求问题的解,本文将从DNA运算过程入手,介绍DNA计算机的原理和DNA计算机的若干最新研究进展。     

DNA计算的应用与展望

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

近交系大鼠DNA指纹图和微卫星DNA多态性的分析

实验动物常规生化标记监测方法主要是通过蛋白质的变化来推测相应的基因的变化 ,而在某种程度上存在着一定的局限性。而DNA指纹图和微卫星DNA是对遗传物质DNA的直接监测 ,比生化标记更准确、更可靠 ,更直观。实验中选取国内常用的SHR、SHRSP、WKY、F344、RCS、LEW等 6个近交系大鼠群体 ,采用DNA指纹图和微卫星DNA技术对 6个近交系大鼠群体进行DNA多态性分析 ,以期筛选出具有精确可靠、快速简便、灵敏性高的遗传监测方法。结果 :(1)DNA指纹图①在 4 0kb— 2 3 1kb之间各组的平均图带数在 14— 19条 ,同一群体不同个体间的相…     

DNA微阵列方法与应用

本文系统扼要介绍了DNA微阵列的技术方法和应用。包括DNA微阵列的制造原理、杂交和检测的方法,数据结果分析方法,DNA微阵列应用范围,优缺点和发展趋势。     

基于分子重组技术的DNA计算

DNA计算是计算科学和分子生物学相结合的新领域。目前关于DNA计算的研究主要是抽象的计算模型和简单的原理性试验。DNA剪接计算模型是以生物DNA分子重组技术为基础的文法系统。本文主要介绍DNA剪接计算模型的文法结构及计算方法,证明了DNA剪接模型可以计算所有图灵机可计算函数。     

关于几类DNA标号图和DNA图的结果

在分子生物学中,DNA链的杂交测序的计算和重构阶段可用DNA图作为数学模型,因此,DNA图得到广泛的研究^[1.2]．为了读取DNA序列,Blazewicz等人提出了可（α,k）-标号有向图的概念,并称有向图D是DNA图,如果D是可（4,k）-标号的．2008年,原军等证明了可（α,k）-标号的有向路和有向圈的充要条件．本文证明了有向路和有向圈可（α,k）-标号的一个性质,并利用有向线图的理论证明了本文所指的伪二部单向完全图D0（A,B）、k部广义路P（V0,V1,…,VK-1）、k部广义圈C（V0,V1,…,Vk-1）以及k部广义树T（V0,V1,…,Vk-1）均是DNA标号图．进而给出并证明了二部单向完全图D（V1,V2）和k部广义路P（V0,V1,…,Vk-1）为DNA图的充要条件．     

解决NP问题的DNA编码技术

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

电化学DNA传感器研究进展

电化学DNA传感器是一种新型的生物传感器,对其基本原理、组成及其在基因检测、基因疾病诊断药物机理研究等方面作了介绍,并对其发展趋势进行了展望.