共查询到18条相似文献,搜索用时 171 毫秒
1.
Tile自组装模型凭借其自组装、可编程等特性在解决NP问题方面具有巨大优势.文中提出了一种求解最大匹配问题的Tile自组装新模型,该模型主要由初始配置子系统、选择子系统及检测子系统3大部分构成.新模型中首先设计Tile分子存储问题信息,其次通过Tile分子自组装操作生成最大匹配问题解空间,最后通过Tile检测分子筛选得到最大匹配问题的解.对模型从所需Tile分子种类、计算时间和计算空间3个方面进行性能分析,并通过实验模拟论证了模型的有效性和正确性. 相似文献
2.
3.
求解接点网络问题的DNA算法 总被引:1,自引:0,他引:1
利用DNA的二级结构——发卡构形,给出了求解接点网络问题的DNA算法.首先用DNA分子编码接点网络问题,然后利用DNA分子的自组装和形成二级结构的能力来求解问题.算法具有自动化实现计算的特点,计算所需的实验操作比Lipton提出的算法少,同时计算所需的DNA量也比Lipton提出的算法少. 相似文献
4.
针对全错位排列这类NP完全问题,提出了一种基于DNA自组装的全错位排列问题计算模型。该模型利用了DNA分子间的自组装能力,在具体操作时只用到凝胶电泳技术,在一定程度上减少了实验误差。 相似文献
5.
介绍了最大团和最大权团的概念和国内外学者运用DNA计算解决最大团的研究成果;结合前人运用质粒、二进制、粘贴模型等方式进行DNA计算操作的原理,设计了新的用于解决最大权团问题的算法步骤,大大提高了算法效率,实现了最大团和最大权团的同步求解,对市场分析、方案选择等领域有一定的意义。 相似文献
6.
脱氧核糖核酸(Deoxyribonucleic acid,DNA)作为未来数据的存储介质具有巨大的潜力.近年来,DNA自组装技术发展迅速,其中DNA折纸(origami)和DNA瓦片(tile)设计及组装技术已经实现了纳米结构的原子级精度.DNA自组装纳米结构因其具有空间可寻址性、可编程性等优点,为基于DNA自组装的信... 相似文献
7.
本文研究利用三链DNA求解最大团问题。首先将最大团问题中的顶点编码为DNA片段,进行生化反应,组合成所有可能的情况,然后利用三链模型对解进行筛选,最终得到图的最大团。该模型降低了编码的复杂度,提高了检测效率,其他的NP(Non-deterministic Polynomial)问题也可用此方法来求解。 相似文献
8.
《华中科技大学学报(自然科学版)》2010,(9)
对粘贴模型的组成、基本实验及其生化实现过程进行了分析,根据解决最大团问题的需要简化了粘贴模型.在粘贴模型中,提出了基于电泳技术和分离实验的DNA序列检测方法,可以检测多种存储链.基于分离实验提出了最大团问题的DNA算法,并给出其生化实现过程:先形成所有非空顶点子集的初始解空间;然后对每条边用分离实验进行检测,保留全部满足不相邻要求的顶点子集,从而得到全部团;再通过电泳实验得到全部最大团.通过检测实验输出实验结果,证明了算法的可行性和有效性. 相似文献
9.
为了寻找图的最大独立集问题,先利用DNA自组装模型解决可满足性问题,再把最大独立集问题转化为可满足性问题,从而解决最大独立集问题。整个过程只用到凝胶电泳操作,在很大程度上减少了误差。 相似文献
10.
《牡丹江师范学院学报(自然科学版)》2016,(4)
全错位排列问题是组合数学中的一种经典问题,可转化为可满足性问题,利用自组装DNA计算模型得到解决.基于DNA自组装产生发夹结构,通过凝胶电泳技术进行筛选,控制温度使发夹结构重新打开得到问题的可行解.该模型只用到凝胶电泳操作,在一定程度上有效避免了生物操作过多产生的实验误差. 相似文献
11.
无向图中的最大连通分量抽取(Maximum Clique Problem,MCP)是一种具有重要应用价值的组合优化问题,已被证明属于NP问题.传统的深度优先、分枝限定等算法可以处理规模较小的MCP问题,所以提出处理大规模MCP问题的算法是非常必要的.粒子群优化算法是一种基于群智能的演化计算技术,离散粒子群算法(DiscretePSO)是其中解决离散编码的算法.提出了一种基于离散粒子群算法的近似连通图的抽取算法,通过定义连通图编码、合法随机初始化过程,编码校正算法使得DPSO能够解决最大连通图的抽取问题.为验证其效果及效率,将该算法与RAClique进行了比较.实验结果表明,该算法在解决此类问题时,执行的速度受节点规模变化不大,效率略优于RAClique其他算法. 相似文献
12.
根据解决最大独立集问题的需要,讨论了简化的粘贴模型,该模型只由单链DNA的存储链和分离板组成.以分离实验为基础提出了批分离实验和生化操作过程,该实验可以快速分离存储链.基于批分离实验设计了最大独立集问题的DNA算法,并给出其生化实现过程:先形成所有顶点子集的初始解空间;接着用批分离实验对每个顶点进行检测,筛选全部满足不相邻要求的顶点子集,从而得到全部独立集;然后通过电泳实验得到全部最大独立集;最后通过检测实验输出实验结果.讨论并证明了算法的正确性和复杂性,算法的操作次数是线性的,通过仿真实验说明了算法的有效性和可行性. 相似文献
13.
Logical computation using algorithmic self-assembly of DNA triple-crossover molecules 总被引:25,自引:0,他引:25
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. 相似文献
14.
将一种新的智能计算方法——DNA计算引入到蛋白质结构预测中,试图建立当蛋白质结构与母板结构相似度比较低的情况下的蛋白质结构比较模型的DNA计算方法。将氨基酸序列中的一个残基的可能构型映射为一段DNA序列,将一个蛋白质结构预测问题转化成一个边赋权的图的最大权团问题,结合最大权团问题的DNA计算模型,建立蛋白质预测问题的DNA算法,并通过仿真实验说明了算法的有效性。 相似文献
15.
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. 相似文献
16.
XUJin LISanping DONGYafei WEIXiaopeng 《科学通报(英文版)》2004,49(9):863-871
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. 相似文献
17.
《河南师范大学学报(自然科学版)》2015,(4):144-150
作为自组装DNA计算领域中一门新技术,DNA链置换反应在分子计算领域得到了广泛的应用.基于自组装DNA计算原理,设计了对应不同逻辑门的DNA分子电路.基于DNA链置换反应机理构建了编码器逻辑电路的分子计算模型.当输入DNA分子信号链时,将不同分子浓度比的DNA分子逻辑门电路混合,借助分子间的特异性杂交反应及分子间链置换反应,最终可输出信号链分子.Visual DSD仿真结果表明了本文设计的编码器逻辑计算模型的可行性与准确性.为拓展分子逻辑电路的应用做出有益的探索. 相似文献
18.
分析了最大团问题的数学性质,根据推导出来的性质设计求解最大团问题的竞争决策算法,且算法的时间复杂度分析结果为O(n~3)。并用提出的算法求解最大团问题中的标准测试示例,测试结果表明,算法具有良好的求解效果。 相似文献