最大匹配问题Tile自组装模型

Tile自组装模型凭借其自组装、可编程等特性在解决NP问题方面具有巨大优势.文中提出了一种求解最大匹配问题的Tile自组装新模型,该模型主要由初始配置子系统、选择子系统及检测子系统3大部分构成.新模型中首先设计Tile分子存储问题信息,其次通过Tile分子自组装操作生成最大匹配问题解空间,最后通过Tile检测分子筛选得到最大匹配问题的解.对模型从所需Tile分子种类、计算时间和计算空间3个方面进行性能分析,并通过实验模拟论证了模型的有效性和正确性.     

三维DNA自组装在多维背包问题中的应用研究

利用DNA自组装执行计算的思想已从实验上被证明了其可行性．已有多种理论模型被提出用以解决各种NP问题．基于DNA Tile自组装模型理论在二维下的扩展,本文设计了可以实现这一算法的三维DNA Tile组装系统,提出了一种用于解决多维背包问题的三维DNA自组装模型．该模型可以非确定性的输出可行性解决方案．分析表明系统可以在线性组装步骤内完成计算,所需的Tile种类数与问题维数无关．为探索三维DNA自组装的计算能力进行了一次有意义的尝试．     

DNA自组装与信息存储

脱氧核糖核酸(Deoxyribonucleic acid, DNA)作为未来数据的存储介质具有巨大的潜力.近年来,DNA自组装技术发展迅速,其中DNA折纸(origami)和DNA瓦片(tile)设计及组装技术已经实现了纳米结构的原子级精度.DNA自组装纳米结构因其具有空间可寻址性、可编程性等优点,为基于DNA自组装的信息存储提供了发展平台.文章综述了基于DNA自组装技术的两种组装模型及DNA信息存储领域的发展现状,总结了当前基于DNA单链、DNA origami和DNA tile的信息存储,概述了当前基于DNA的信息存储领域中面临的挑战,并展望了DNA自组装及其在信息存储领域的应用前景.     

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

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

基于DNA自组装的全错位排列问题模型

针对全错位排列这类NP完全问题,提出了一种基于DNA自组装的全错位排列问题计算模型。该模型利用了DNA分子间的自组装能力,在具体操作时只用到凝胶电泳技术,在一定程度上减少了实验误差。     

基于DNA计算的最大权团问题设计

介绍了最大团和最大权团的概念和国内外学者运用DNA计算解决最大团的研究成果;结合前人运用质粒、二进制、粘贴模型等方式进行DNA计算操作的原理,设计了新的用于解决最大权团问题的算法步骤,大大提高了算法效率,实现了最大团和最大权团的同步求解,对市场分析、方案选择等领域有一定的意义。     

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

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

基于粘贴模型的最大团问题算法

对粘贴模型的组成、基本实验及其生化实现过程进行了分析,根据解决最大团问题的需要简化了粘贴模型.在粘贴模型中,提出了基于电泳技术和分离实验的DNA序列检测方法,可以检测多种存储链.基于分离实验提出了最大团问题的DNA算法,并给出其生化实现过程:先形成所有非空顶点子集的初始解空间;然后对每条边用分离实验进行检测,保留全部满足不相邻要求的顶点子集,从而得到全部团;再通过电泳实验得到全部最大团.通过检测实验输出实验结果,证明了算法的可行性和有效性.     

DNA自组装的全错位排列问题模型

全错位排列问题是组合数学中的一种经典问题,可转化为可满足性问题,利用自组装DNA计算模型得到解决.基于DNA自组装产生发夹结构,通过凝胶电泳技术进行筛选,控制温度使发夹结构重新打开得到问题的可行解.该模型只用到凝胶电泳操作,在一定程度上有效避免了生物操作过多产生的实验误差.     

基于DNA自组装模型解决图的最大独立集问题

为了寻找图的最大独立集问题,先利用DNA自组装模型解决可满足性问题,再把最大独立集问题转化为可满足性问题,从而解决最大独立集问题。整个过程只用到凝胶电泳操作,在很大程度上减少了误差。     

基于离散粒子群算法的近似最大连通分量抽取

无向图中的最大连通分量抽取(Maximum Clique Problem,MCP)是一种具有重要应用价值的组合优化问题,已被证明属于NP问题．传统的深度优先、分枝限定等算法可以处理规模较小的MCP问题,所以提出处理大规模MCP问题的算法是非常必要的．粒子群优化算法是一种基于群智能的演化计算技术,离散粒子群算法(DiscretePSO)是其中解决离散编码的算法．提出了一种基于离散粒子群算法的近似连通图的抽取算法,通过定义连通图编码、合法随机初始化过程,编码校正算法使得DPSO能够解决最大连通图的抽取问题．为验证其效果及效率,将该算法与RAClique进行了比较．实验结果表明,该算法在解决此类问题时,执行的速度受节点规模变化不大,效率略优于RAClique其他算法．     

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

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

Logical computation using algorithmic self-assembly of DNA triple-crossover molecules

Recent work has demonstrated the self-assembly of designed periodic two-dimensional arrays composed of DNA tiles, in which the intermolecular contacts are directed by 'sticky' ends. In a mathematical context, aperiodic mosaics may be formed by the self-assembly of 'Wang' tiles, a process that emulates the operation of a Turing machine. Macroscopic self-assembly has been used to perform computations; there is also a logical equivalence between DNA sticky ends and Wang tile edges. This suggests that the self-assembly of DNA-based tiles could be used to perform DNA-based computation. Algorithmic aperiodic self-assembly requires greater fidelity than periodic self-assembly, because correct tiles must compete with partially correct tiles. Here we report a one-dimensional algorithmic self-assembly of DNA triple-crossover molecules that can be used to execute four steps of a logical (cumulative XOR) operation on a string of binary bits.     

一种蛋白质结构同源建模的DNA算法

将一种新的智能计算方法——DNA计算引入到蛋白质结构预测中,试图建立当蛋白质结构与母板结构相似度比较低的情况下的蛋白质结构比较模型的DNA计算方法。将氨基酸序列中的一个残基的可能构型映射为一段DNA序列,将一个蛋白质结构预测问题转化成一个边赋权的图的最大权团问题,结合最大权团问题的DNA计算模型,建立蛋白质预测问题的DNA算法,并通过仿真实验说明了算法的有效性。     

Arithmetic computation using self-assembly of DNA tiles: subtraction and division

Recently,experiments have demonstrated that simple binary arithmetic and logical operations can be computed by the process of selfassembly of DNA tiles.In this paper,we show how the tile assembly process can be used for subtraction and division.In order to achieve this aim,four systems,including the comparator system,the duplicator system,the subtraction system,and the division system,are proposed to compute the difference and quotient of two input numbers using the tile assembly model.This work indicates that these systems can be carried out in polynomial time with optimal O(1)distinct tile types in parallel and at very low cost.Furthermore,we provide a scheme to factor the product of two prime numbers,and it is a breakthrough in basic biological operations using a molecular computer by self-assembly.     

Sticker DNA computer model ——PartⅡ: Application

Sticker model is one of the basic models in the DNA computer models. This model is coded with sin-gle-double stranded DNA molecules. It has the following advantages that the operations require no strands extension and use no enzymes; What抯 more, the materials are reusable. Therefore, it arouses attention and interest of scientists in many fields. In this paper, we extend and improve the sticker model, which will be definitely beneficial to the construction of DNA computer. This paper is the second part of our series paper, which mainly focuses on the application of sticker model. It mainly consists of the following three sections: the matrix representation of sticker model is first presented; then a brief review of the past research on graph and com-binatorial optimization, such as the minimal set covering problem, the vertex covering problem, Hamiltonian path or cycle problem, the maximal clique problem, the maximal independent problem and the Steiner spanning tree problem, is described; Finally a DNA algorithm for the graph iso-morphic problem based on the sticker model is given.     

地图着色问题的粘贴DNA算法

提出多级分离的概念,给出一个多级分离装置的模型,并介绍粘贴模型中的多级分离操作、将地图着色问题转化为可满足性问题、基于粘贴模型的巨大并行性及多级分离的优势,提出解决该问题的粘贴DNA算法。通过一个实例给出实验操作步骤,并对生化反应过程进行模拟,得出具体的着色方案,从而证明了该多级分离装置的有效性以及该算法的可行性。     

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

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