DNA计算在整数规划问题中的应用

基于生化反应原理的DNA计算由于在解决一类困难问题,特别是NP-完全问题上具有硅计算机无法比拟的优势,因此对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计算和DNA计算机是目前世界上研究的热点问题，文章介绍了DNA计算及其应用的研究，分析了DNA计算存在的问题与急待解决的问题。     

DNA-纳米颗粒共聚体在最大匹配问题中的应用

该文提出一种DNA计算模型,利用DNA-纳米金颗粒共聚体的自组装来解决图论中的一个NP完全问题——最大匹配问题。根据模型该文设计了能够基于一个具体的图进行自组装的特殊的DNA-纳米金颗粒共聚体,然后利用一系列的实验方法来获得最终的解。这种生物化学算法可以极大地降低求解最大匹配问题的复杂度,这将为DNA自组装计算模型提供一种切实可行的方法。     

DNA-纳米颗粒共聚体在最大匹配问题中的应用

该文提出一种DNA计算模型,利用DNA-纳米金颗粒共聚体的自组装来解决图论中的一个NP完全问题——最大匹配问题.根据模型该文设计了能够基于一个具体的图进行自组装的特殊的DNA-纳米金颗粒共聚体,然后利用一系列的实验方法来获得最终的解.这种生物化学算法可以极大地降低求解最大匹配问题的复杂度,这将为DNA自组装计算模型提供一种切实可行的方法.     

应用神经网络理论的计算机通信网迟延新算法

计算机网络最小平均迟延的求解实质上是一个联合优化问题，进一步的分析表明，它可以近似一个二次型优化问题。我们利用一种具有全局收敛性质的神经网络模型解决了这一问题。计算结果表明，这种方法是可行而有效的。     

DNA纳米颗粒共聚体在图的连通度问题中的应用

本文提出了一种利用DNA纳米金颗粒共聚体的自组装过程解决图论中一个NP完全问题-连通度问题的DNA计算方法,构建了解决图的连通度问题的三维DNA自组装计算模型.根据设计的算法,首先需要根据具体的图的连通度问题设计用于自组装的DNA纳米金颗粒共聚体,然后根据算法经过一系列实验设计来求解连通度问题.本文利用Visual DSD仿真该实验的可行性,为下一步DNA自组装计算模型的应用提供了可行的方案.     

DNA密码中的DNA编码技术

DNA密码是目前新兴的一个前沿研究方向。文章阐述了DNA计算在密码学中几个方面的应用,探讨了DNA编码问题及限制条件,特别是从用DNA计算解决密码学中的一个组合问题的实验步骤中分析了DNA编码的质量,提出了更好的编码。     

Integer Programming Problem Based on Plasmid DNA Computing Model

A DNA algorithm by operating on plasmids was presented to solve a special integer programming, a typical hard computing problem. The DNA algorithm employed double-stranded molecules to encode variables of 0-1 programming problem, the encoded DNA molecules were inserted into circular plasmids as foreign DNA molecules. Followed by, a series of enzymatic treatments to plasmids were performed in order to find feasible solutions to the given problem. The final optimum was obtained by applying founded feasible solutions to object function. Compared with other DNA algorithms of integer programming problem, the proposed algorithm is simple, error-resistant, above all, feasible. Our work clearly showed the distinct advantages of plasmid DNA computing model when solving integer related programming problem.     

图的顶点着色问题的DNA算法

图的顶点着色问题是指无向图中任意两个相邻顶点都分配到不同的颜色,这个问题是著名的NP-完全问题,没有非常有效的算法.但在1994年Adleman^[1]首次提出用DNA计算解决NP-完全问题,设计出一种全新的计算模式—模拟生物分子DNA的结构并借助于分子生物技术进行计算,使得NP-完全问题的求解可能得到解决.本文首先提出了基于分子生物技术的图的顶点着色问题的DNA算法,算法的关键是对图中的顶点和顶点的颜色进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离,依据分子生物学的实验方法,本文提出的算法是有效和可行的;其次指出了该算法的优点、存在的问题及将来进一步的研究方向.     

Ménage问题的一种粘贴DNA算法

 解决图论与排列组合难题是DNA计算领域的研究目标之一.为了使用分子生物方法解决Ménage问题,本文给出了Ménage问题的数学模型;并对解决该问题的难点进行了分析,提出一种解决方案,改进了该问题的数学模型;提出一种解决Ménage问题的粘贴DNA算法并简要分析了该算法的复杂度.为了提高效率,引入广义分离和广义多级分离操作;通过一个实例给出了实验操作步骤,对实验进行了模拟.     

TSP的DNA算法

由于Adleman和Lipton的开创性工作,最近DNA计算引起了人们的极大兴趣,他们提出的分子算法解决了图形的表示方法,但是没有给出如何处理图中节点的弧线的信息。本文的目的是通过提出在图中城市间的距离用简单的弧线代表,延伸了Adleman和Lipton提出的基本的分子算法。并提出只有当算法步骤由当前的需要人工干预被可执行的可在试管中操作的DNA链代替,解决计算难题的真正可行DNA计算可以实现。该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理的范围内寻找旅行商问题的解,较大地简化了问题的复杂度。     

Analog Computation Using Single-Electron Circuits

Analog computation is a processing method that solves a given problem by utilizing an analogy of a physical system to the problem. An idea is presented here for relating the behavior of single-electron circuits to analog computation. As an instance, a method is proposed for solving a combinatorial problem, the three-colorability problem, by using the properties of single-electron circuits. In problem solving, a single-electron circuit is constructed that is analogous to a given problem; then, through an annealing procedure, the circuit is made to settle down to its minimun energy state. The correct solution to the problem can be obtained by checking the final arrangement of electrons in the circuit. Analog computation is a promising architecture for single-electron computing systems.     

基于DNA有穷自动机的素性测试法

有穷自动机,一种计算能力极其有限的计算模型,具有解决素性测试的能力通过构造法得到了证明。既而提出了一种基于有穷自动机的测试一个整数是否为素数的DNA算法,并且详细描述了该有穷自动机的构造方法,将有穷自动机的状态用DNA单链分子来编码,而输入则用DNA双链分子编码,用带环的双链DNA分子来编码状态转移规则,通过限制性内切酶的切割实现状态的转移。该算法的创新之处在于它是基于有穷自动机这种计算能力极其有限的计算模型的,并且该算法不仅能判断一个整数是否是素数,还能用于素因子分解。该算法的优点是实验实现容易,所需的时间是输入的多项式函数而不是指数函数。     

参数法P3P模型在视觉坐标测量中的应用

P3P问题的求解是视觉坐标测量系统建模的数学理论基础,传统上利用通用余弦定理和正弦定理求解.为快速精确地求取控制点三维坐标,提出一种利用参数法求解P3P模型解析解的计算方法,并将该模型应用到视觉坐标测量过程中,通过精确求解共线三控制点在摄像机坐标系下的坐标.进而求出与其位置关系已知的被测点三维坐标.介绍了该测量系统的结构、测量原理、计算模型、实验过程以及实验结果,并与传统的利用通用余弦求解模型的计算结果进行了比较,说明本计算方法不仅简单直观,而且精度较高,非常适合应用在视觉坐标测量过程中.