DNA计算中编码问题的研究

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

DNA计算问题的研究进展

DNA计算是近十年发展起来的一门新学科,目前的研究已经取得了很大的进展.本文首先介绍了DNA计算的机理,然后说明了DNA分子的结构及DNA计算的特点.最后分析了目前DNA计算所存在的问题,并展望了DNA计算的应用发展前景.     

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

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

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

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

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

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

DNA计算原理与发展

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

基于人工鱼群遗传算法的DNA编码优化

针对DNA计算中的编码序列设计问题,分析DNA编码序列设计的目标和需要满足的约束条件,从中选择适当的约束条件,给出评估公式,提出人工鱼群遗传算法生成有效的DNA编码序列。经实验结果表明,所述算法比遗传算法及遗传粒子群算法产生的DNA编码序列质量更加稳定可靠。     

若干NP完全问题的特殊情形

讨论了图算法中若干ＮＰ完全问题在所给的图是一棵树时的特殊情形－ 利用树结构的前序编号表示法提出了解树的最大独立集问题、最小顶点覆盖问题和最小支配集问题的线性时间算法－在渐近意义下这些算法都是最优算法     

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

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

DNA编码的模型分析

提出了适应DNA计算的DNA编码问题.对等码长的DNA编码问题的数学模型进行分析.以优化码长作为目标,分析了约束条件.以杂交反应为核心将约束条件分为基本约束和控制生化实验的约束,而控制生化实验的约束包含组合约束和热力学约束.控制移动不匹配的下值才能控制杂交反应,由此改进了移动距离.引入窗口距离解决了错配总量和分布的控制问题.     

基于人工鱼群的DNA编码序列组合优化算法研究

分析DNA编码序列设计的目标及需要满足的约束条件,提出全局人工鱼群算法(GAFSA)生成有效的DNA编码序列.根据优化问题的约束条件及人工鱼群的特点,对人工鱼的视野和步长按进行动态调整.实验结果表明,所述GSFSA算法比遗传算法、多目标进化算法、遗传粒子群算法算法产生的DNA编码序列具有更高的质量.     

New field of cryptography： DNA cryptography

The vast parallelism, exceptional energy efficiency and extraordinary information density inherent in DNA molecules are being explored for computing, data stor- age and cryptography. In such research area, novel computers, data storage and cryptography mi…     

一种求解TSP问题的新型遗传编码方案

针对利用传统的遗传编码求解TSP中,普遍存在的不能在两条染色体间的任意位置进行交叉、编码空间过大等缺点．提出了一种新的编码方案：比较编码法。理论分析和实验结果表明,所提的编码方案较传统编码方案有明显的优势。     

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

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

特征统计算法及其在NP组合优化问题上的应用

特征统计算法是为了解决复杂多极值优化问题而开发的一种新的全局优化算法。为了检验该算法的性能,应用它在一类具有代表性的NP组合优化问题-旅行商问题(TSP)上作了计算。结果发现,该算法虽不是专为TSP问题而开发,却在该问题上取得了很好的结果。所得到的结果表明,特征统计算法可以作为解决这类NP组合优化问题的一个新的途径。     

解 packing 及 CNF-SAT 问题的拟物拟人方法

提出拟物拟人方法．论述了如何按此种方法为ＮＰ难问题设计出高效实用的快速求解算法．作为例证，所得出的关于ＣＮＦ－ＳＡＴ问题及ｐａｃｋｉｎｇ问题的算法，其先进性在国际竞赛及工业生产中得到了显示．     

NP最优化问题的可近似性

研究了NP最优化问题的可近似性。按照不同的可近似性将问题分类,证明了这些类是不同的 （在P≠NP的假设下）,并定义了问题之间保持近似比的归约,为每一类找到了在此归约下完 全的问题。     

A global heuristically search algorithm for DNA encoding

A new efficient algorithm is developed to design DNA words with equal length for DNA computing. The algorithm uses a global heuristic optimizing search approach and converts constraints to a carry number to accelerate the convergence, which can generate a DNA words set satisfying some thermodynamic and combinatorial constraints. Based on the algorithm, a software for DNA words design is developed.