哈密顿回路问题的DNA表面计算模型

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。论文采用荧光标记的策略,给出了一种新的哈密顿回路问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得哈密顿回路问题的所有解。在新模型中,解空间的生成过程与边的排列顺序无关。     

一种新的求解最小生成树问题的DNA算法

基于生化反应的生物智能计算是现阶段计算领域研究的热点,DNA计算是通过DNA分子之间的生化反应来进行计算的一种计算模式,凭借运算巨大的并行性和海量存储的优势,DNA计算在解决复杂运算问题方面的计算能力显而易见。设计了一种利用DNA计算来求解图的最小生成树的计算模型,采用一种特殊的编码方式来对顶点,边和权值进行编码,并且描述了MSTP解的计算过程。     

最小顶点覆盖问题的闭环DNA算法

提出了闭环DNA计算模型的基本概念及其基本生化实验,并给出了解决最小顶点覆盖问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造顶点覆盖补集的构想;再通过电泳实验得到最小顶点覆盖的补集,由补集得到最小顶点覆盖。这使得算法的设计独特而新颖;由于算法仅用到基本的生化实验,这使得算法的实现简捷、可靠。     

一种新型DNA自组装磁珠光电检测系统及其在DNA计算机研制中的应用

文中提出了一种基于硅芯片集成自组装磁珠颗粒的新型DNA光电检测系统,该系统利用普通照射光源及光电二极管进行光电信号转换,通过比较DNA杂交反应前后的光电流值,来识别DNA杂交信号.该系统是一种首次将磁珠和光电二极管相结合的新型DNA杂交检测系统,具有成本低廉、快速检测及高精度的特点.这种检测方法不需要信号增强步骤,就能够有效区分DNA单碱基错配及完全杂交的情况;由于采用了磁珠颗粒,易于在DNA计算中删除问题的非解.文中给出了求解图的最小顶点覆盖问题DNA计算模型实例,该实例证实了文中所提出的检测系统较传统检测系统具有明显的优势,有利于实现DNA计算机检测系统中解的自动化检测.     

最佳匹配问题的DNA表面计算模型

基于最佳匹配问题的问题解空间,采用荧光标记的策略,给出了一种新的最佳匹配问题的DNA表面计算模型,该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得最佳匹配问题的所有解.与已有的最大匹配问题的DNA表面计算模型相比,新模型在检测边的过程中不需要使用观察法,且边的排列顺序不影响解空间的生成过程.因此,新模型具有更好的性能.     

一类特殊整数规划问题的DNA计算

基于生化反应原理的DNA计算由于在解决一类困难问题,特别是完全问题上具有硅计算机无法比拟的优势,因此对DNA计算的研究具有重要意义．提出了约束方程组的“秩”以及约束方程的3种“约束补链”概念,并基于这些概念,利用在基于表面的DNA计算中采用荧光标记的策略,给出了一类特殊整数规划问题最优解的一种基于DNA计算的求解算法．新算法利用荧光猝灭技术来排除非解,从而得到满足约束条件的所有可行解,最后再通过比较所有可行解的目标函数值来求得问题的所有最优解．算法分析表明,新算法具有解读、编码简单和错误率低的特点。     

哈密尔顿回路问题的DNA表面计算模型

首次提出用DNA表面计算模型来解决无向图哈密尔顿回路问题。该模型基于哈密尔顿回路问题的解空间,将问题解空间的DNA分子固定在固体载体上,对其进行荧光标记,然后通过相应的生化反应筛选出哈密尔顿回路问题的所有解。与已有的哈密尔顿路径问题的其它模型相比,新模型具有错误率低,编码简易,读取方便等更好的性能。     

赋权图上优化问题的DNA计算方法研究(英文)

对赋权图上经典优化问题的DNA计算方法进行探讨,改进原有DNA计算模型中的权值编码方法,提出一些新的DNA编码方法及DNA算法．具体地说,通过设计赋权无向图的相对长度图给出了旅行商问题的一种相对长度DNA编码方法及DNA算法,通过设计赋权无向图的广义边图给出了中国邮递员问题的一种广义边图DNA编码方法及DNA算法,通过选取DNA序列的最佳逆补比对给出了最小生成树问题的一种基于逆补比对的DNA编码方法及DNA算法,通过设计从顶点覆盖问题到Hamilton回路问题的一种改进多项式变换给出了顶点覆盖问题的一种基于多项式变换的DNA编码方法及DNA算法．所设计的DNA计算方法提高了DNA计算中表示数值和处理数值的能力．     

精确覆盖问题的O(1.414~n)链数DNA计算机算法

DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法.算法由初始解空间生成算法Init()、冗余解删除算法IllegalRemove()和并行搜索器ParallelSeacher()共3个子算法组成.与同类算法的性能比较分析表明:本算法在保持多项式生物操作复杂性的条件下,将求解n维精确覆盖问题的DNA链数从O(2n)减少至O(1.414n),从而将DNA计算机在试管内可求解的精确覆盖问题集合的基数从60提高到120,改进了相关文献的研究结果.     

图的最小顶点覆盖问题的面上DNA解法

1994年，Adleman提出一种解决NP完全问题的新方法-DNA计算．之后又出现了许多关于DNA计算的改进操作并增加了其可靠性，其中面上操作是一种很有效的方法．本文利用DNA计算的固态处理(面上计算)解决了图论中又-NP完全问题一图的最小顶点覆盖问题．构造了含有6个顶点10条边的图的顶点集子集对应的数据池之后，进行了一系列的合成、杂交、清洗、变性等生物操作，得到所有覆盖对应的DNA序列，然后通过编址过程得到所要求的最小覆盖．     

顶点覆盖变体问题的确定参数可解算法研究

参数复杂性作为算法研究的一个重要分支,近十年来在国际上受到了广泛的关注,确定参数可解算法是参数复杂性研究的一类重要问题,因此被广泛研究。本文主要研究了顶点覆盖问题的两个变体问题：一个是连接的顶点覆盖问题,二是含权的树型顶点覆盖问题。这两个问题都是对原始的顶点覆盖问题加入了一些限制的变体问题。本文给出了这两个问题的确定参数可解算法,并且是目前的最好结果。     

求解简单多边形间最小距离的一个线性时间算法

计算简单多边形间的最小距离,在所有与几何图形计算有关的领域中,一直以来都是一个基本问题。为了更快地求解简单多边形的最小距离,提出了一个基于关联多边形三角化分割的简单多边形间最小距离的求解算法。该算法的主要思想是:首先构造一个关联多边形把两个多边形联系起来,其目的是把最小距离限制在这个关联多边形内;然后根据两个多边形的最小边界矩形包围框间的不同位置关系,详细阐述了关联多边形的构造过程,同时论述了关联多边形是一个简单多边形。为了计算最小距离,首先要对关联多边形进行三角化分割,并使最小距离位于三角化分割结果中某一个三角形区域内,或者至多位于两个相邻三角形区域内;之后通过对所有三角形进行遍历来找出最小距离及其所在的位置。该算法的时间复杂度是线性的。     

基于可满足解空间的DNA算法--解决最小顶点覆盖问题

论文给出了基于可满足解空间的最小顶点覆盖问题的DNA算法,该算法直接生成可满足解空间,无须在全体解空间中进行各种过滤过程。在对图中的顶点进行适当的编码后,使用常规的生物操作完成可满足解空间的产生及最终解的分离。最后指出了该算法的优点、存在问题及下一步的研究方向。     

一种基于邻居信息的最大派系过滤算法

最大派系问题(Maximal Clique Problem, MCP)是组合优化中经典而重要的问题之一,在信息抽取、信号传输、计算机视觉、社会网络及生物信息学等众多领域有着重要的应用。学者们根据不同的思想策略,提出了许多方法求解最大派系问题,如分支定界、遗传算法、模拟退火、交又嫡及DNA方法等。现根据派系的部居信息提出一种基于派系邻接顶点和邻接边的派系过滤算法。算法从一个已知派系(初始为一个单独顶点)出发,每次考察派系的部接顶点,并以派系的邻接边为基础,扩展已有派系而得到更大的派系。用两个大规模的科学家合作网络对提出的算法进行了分析,并讨论了大规模社会网络中的派系分布情况。实验表明,提出的算法可有效地抽取网络中的最大派系。     

基于面上DNA计算求解最小集合覆盖问题*

利用DNA分子结构推得DNA计算机理及实现方式,提出用面上DNA计算模型求解最小集合覆盖问题,给出了具体应用和算法评价;在计算模板表面穷举了所有可能的结果,同一时间验证结果是否满足条件,实现DNA计算的强大并行性;同时在互补的寡聚核苷酸片段发生退火反应时,通过催化剂来决定是否杂交,减少人工参与、提高计算效率。最后,通过计算机仿真模拟验证了本模型的可行性。     

Minimal covering problem and PLA minimization

Solving the minimal covering problem by an implicit enumeration method is discussed. The implicit enumeration method in this paper is a modification of the Quine-McCluskey method tailored to computer processing and also its extension, utilizing some new properties of the minimal covering problem for speedup. A heuristic algorithm is also presented to solve large-scale problems. Its application to the minimization of programmable logic arrays (i.e., PLAs) is shown as an example. Computational experiences are presented to confirm the improvements by the implicit enumeration method discussed.This work was supported in part by the National Science Foundation under Grants Nos. MCS77-09744 and MCS81-08505 and also by the Department of Computer Science.M.-H. Young was with the Department of Computer Science, University of Illinois, Urbana, Illinois.     

基于最小集合覆盖的属性约简算法

在粗糙集理论的各种应用中,属性约简算法具有重要的意义,因而对属性约简算法的研究一直是粗糙集理论研究中的重点问题之一。在对属性约简算法充分研究的基础上提出一种基于最小覆盖集的粗糙集属性约简算法,即通过构造知识系统的一种改进的相关矩阵将属性约简简化为最小覆盖问题。将该算法与文献[7]中的算法进行实验比较并对结果进行分析,实验结果表明,当随着数据量增大时该算法具有更小的时间复杂度。