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

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

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

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

一种启发式的分布式最大独立集算法

从最大独立集问题的0-1整数规划数学描述入手,首先针对树图情形提出了一种基本的分布式树（Tree）算法,并证明该算法在树图情形下是最优的,然后将该Tree算法针对一般图情形进行了启发式的修正,得到一种新的分布式修正树（m-Tree）算法.理论分析表明,当图为树或二分图时,m-Tree算法可以简化为基于信用传播（BP）的分布式算法,是对BP算法的一种推广.仿真结果表明,对于树或二分图情形,m-Tree算法与BP算法都能收敛至最优解;对于一般图情形,m-Tree算法的收敛性能与权和性能均远优于BP算法,并且其权和性能接近最优解.     

基于改进的粘贴模型求解图最大独立集的DNA算法

改进的DNA粘贴模型在解决SAT问题时所需的寡核苷酸片段数量有显著降低,对改进的粘贴模型做了进一步的改进,建立了图最大独立集的一种改进的DNA粘贴模型.首先将图的独立集问题转化为可满足性问题,然后利用本文改进的粘贴模型给出了图的最大独立集的DNA算法.最后通过一个实例给出算法实现并求出了最大独立集.     

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

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

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

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

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

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

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

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

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

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

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 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 development of molecular biology technique, the field of DNA computation has made a great progress. By using an advance technique of biochip, laboratory-on-a-chip, in this paper a new DNA computing model was presented to solve a simple timetabling problem, which is a special version of the optimization problems and plays an important role in education. 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 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.     

A novel DNA computing model based on RecA-mediated triple-stranded DNA structure

The field of DNA computing emerged in 1994 after Adleman’s paper was published. Henceforth,a few scholars solved some noted NP-complete problems in this way. And all these methods of DNA computing are based on conventional Watson-Crick hydrogen bond of doublehelical DNA molecule. In this paper, we show that the triple-stranded DNA structure mediated by RecA protein can be used for solving computational problems. Sequence-specific recognition of double-stranded DNA by oligonucleotide-directed triple helix (triplex) formation is used to carry out the algorithm. We present procedure for the 3-vertex-colorability problems. In our proposed procedure, it is suggested that it is possible to solve more complicated problems with more variables by this model.     

0—1规划新算法的改进

0—1规划是规划论中一种特殊的规划,也是一种很有应用价值的规划。本文在蒲黎明先生给出的新算法(《系统工程理论与实践》1986.4)的基础上作了改进,使占用内存大幅度降低且速度提高约一倍。     

DNA计算技术进展

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

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.