图的最小顶点覆盖的粘贴DNA计算模型

本文在对经典粘贴模型以及全信息化的粘贴DNA计算模型的基本方法进行充分讨论的基础上,提出一种用粘贴DNA计算模型解决图的最小顶点覆盖问题的新方案,将数学问题的求解同并行生物操作有效结合.     

基于DNA步行者求解最小顶点覆盖问题的计算模型

DNA步行者作为一类可执行复杂操作的新兴动态DNA纳米机器,可以在纳米尺度上以可控的方式在指定轨道内行走.文章将DNA步行者用于解决最小顶点覆盖问题,首先构造出全部顶点覆盖,用删除实验得到顶点覆盖的补集,再通过荧光探针N-甲基卟啉二丙酸(NMM)特异性识别G-四链体结构,产生荧光,最终得到最小顶点覆盖.该模型设计独特新...     

最小顶点覆盖问题的一个近似算法

最小顶点覆盖是图论中的一个重要概念,它是一个NP难的问题．给出了一个求解最小顶点覆盖的近似算法,与现有算法相比具有更优的性能比。     

图顶点着色问题的质粒DNA计算

图的着色问题是著名的NP问题,有着重要的实际意义。比如通讯系统的频道分配、考试排考场问题等方面有直接应用。图的着色问题采用DNA计算方法很多,有表面DNA计算,粘贴DNA计算。本文提出质粒DNA计算,首先把顶点着色问题转化为求最大独立集问题,然后给出了图顶点着色问题的质粒DNA分子生物实验,利用限制性内切酶的特性切割有边相连的顶点,得到最大独立集,在试验中特别引入了一个备用试管,最后给出一个具体的实例。实例给出具体的着色方案,证明了该质粒DNA算法有效并且是可行的。     

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

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

DNA计算问题的研究进展

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

求一般图的最小顶点覆盖集问题的混合贪婪算法

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充.     

图顶点m着色的改进算法

对于解决图顶点着色问题,目前较常使用ＤＦＳ算法,而由于该算法存在效率不高问题,故提出ＤＦＳ改进算法,极大提高了该算法的效率,对于较难的图顶点着色问题,利用该改进算法更为有利。     

DNA计算原理与发展

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

顶点覆盖问题的贪心算法的设计与分析

设计了解顶点覆盖问题的贪心算法 ,并证明其相对比率 η≤H(d) ,d为图中最大的顶点度数 ,H(d) =∑1/ j(j =1,2 ,…… ,d) .当d ≤ 3时 ,解的精确度有明显改善 .     

A surface-based DNA algorithm for the minimal vertex cover problem

Abstract DNA computing was proposed for solving a class of intractable computational problems, of which the computing timewill grow exponentially with the problem size. Up to now, many achievements have been made to improve its performance and increase itsreliability. It has been shown many times that the surface-based DNA computing technique has very low error rate, but the technique hasnot been widely used in the DNA computing algorithms design. In this paper, a surface-based DNA computing algorithm for minimal ver-tex cover problem, a problem well-known for its exponential difficulty, is introduced. This work provides further evidence for the abilityof surface-based DNA computing in solving NP-complete problems.     

DNA computing model based on lab-on-a-chip and its application on solving the timetabling problem

The essential characteristic of DNA computation is its massive parallelism in obtaining and managing information. With the develop- ment of molecular biology technique, the field of DNA computation has made a great progress. By using an advanced biochip technique, laboratory-on-a-chip, a new DNA computing model is presented in the paper to solve a simple timetabling problem, which is a special version of the optimization problems. It also plays an important role in education and other industries. With a simulated biological experiment, the result snggested that DNA comnutation with lab-on-a-chin has the notential to solve a real comtplex timetabling problem.     

DNA computing model based on lab-on-a-chip and its application to solving the timetabling problem

The essential characteristic of DNA computation is its massive parallelism in obtaining and managing information.With the development of molecular biology technique,the field of DNA computation has made a great progress.By using an advanced biochip technique,laboratory-on-a-chip,a new DNA computing model is presented in the paper to solve a simple timetabling problem,which is a special version ofthe optimization problems.It also plays an important role in education and other industries.With a simulated biological experiment,the result suggested that DNA computation with lab-on-a-chip has the potential to solve a real complex timetabling problem.     

DNA计算技术进展

论述DNA计算技术进展。先介绍DNA计算的基本原理,论述DNA计算的特点方法和存在的问题,接着介绍DNA计算的国内外研究现状,最后指出DNA计算研究中需要解决的问题。     

A membrane evolutionary algorithm for DNA sequence design in DNA computing

DNA sequence design has a crucial role in successful DNA computation,which has been proved to be an NP-hard(non-deterministic polynomial-time hard) problem.In this paper,a membrane evolutionary algorithm is proposed for the DNA sequence design problem.The results of computer experiments are reported,in which the new algorithm is validated and out-performs certain known evolutionary algorithms for the DNA sequence design problem.     

Molecular logic computing model based on self-assembly of DNA nanoparticles

In this paper, a logic computing model was constructed using a DNA nanoparticle, combined with color change technology of DNA/Au nanoparticle conjugates, and DNA computing. Several important technologies are utilized in this molecular computing model: DNA self-assembly, DNA/Au nanoparticle conjugation, and the color change resulting from Au nanoparticle aggregation. The simple logic computing model was realized by a color change, resulting from changing of DNA self-assembly. Based on this computing model, a set of operations computing model was also established, by which a simple logic problem was solved. To enlarge the applications of this logic nanocomputing system, a molecular detection method was developed for H1N1 virus gene detection.     

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

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

P4*中保三元正则可离关系函数集非最小覆盖成员的确定

根据部分K值逻辑的完备性理论[1]以及准完备集之间的相似关系理论[2],定出了必不属于部分四值逻辑中保三元正则可离关系函数集之最小覆盖的成员.     

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

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