图的最大团与最大独立集粘贴DNA计算模型

粘贴模型(stickermodel)是DNA计算中一个很重要的模型.其主要原理就是采用单双链混合型DNA分子进行编码,其优点在于在生物操作过程中不需要DNA链的延伸,不需要生物酶的作用以及DNA链可重复使用等,因此引起了来自不同学科的学者们的广泛关注与兴趣.文中提出了一种求解图的最大团问题的DNA计算模型,该模型采用了两种基本并行计算处理思想,一种是将图分解成小的子图来处理的并行思想;另一种是进行并行生物操作.     

甲骨文检索的粘贴DNA算法

为了能更好地研究和保护甲骨文,设计了一种适合DNA计算机的甲骨文编码方式,并据此提出了进行甲骨文检索的粘贴DNA算法。根据DNA双链分子具有双螺旋结构的特性,甲骨文标准字库的编码和待检索文字的编码采用了互补的方式,以利于生化操作的执行。仿真结果表明该算法具有可行性和有效性。     

可满足性问题的一种DNA表面计算模型

可满足性问题的一种DNA表面计算模型是一种特殊的DNA计算方法,该模型是采用荧光标记的策略和荧光猝灭技术,通过观察荧光灭光情况排除非解,从而有效的解决可满足性问题(SAT).该模型方法具有错误率低、编码简单、读取方便等很好的性能,能够大大减少实验过程中的错差.     

基于粘贴模型的图顶点着色问题的DNA算法

为了用生化实验的方法解决图的顶点着色问题,基于粘贴模型的巨大并行性,将着色问题转化为可满足性问题,提出一个基于粘贴模型的DNA算法。通过一个实例给出了操作步骤,并对生化反应过程进行了模拟,得出具体的着色方案,证明了该算法的可行性。     

一类禁位排列问题的粘贴DNA算法

提出了广义的分离操作和广义的多级分离操作的概念,简要说明了二者的区别,并给出了其实现方法。基于粘贴模型的巨大并行性,给出了一类禁位排列问题的粘贴DNA算法,分别使用扩展的分离操作和扩展的多级分离操作实现了该算法。通过一个实例说明了给出的实验操作步骤,并对生化实验进行了模拟,得出了模拟结果,从而证明了该算法的可行性。最后,对算法的操作复杂度进行了分析。     

基于粘贴模型的两类全排问题的DNA算法

基于粘贴模型的巨大并行性,分别给出了线性全排列和圆周全排列问题的粘贴DNA算法;分析了两类问题的DNA算法的不同之处;通过一个实例给出了实验操作步骤,并对生化实验进行了模拟,得出了正确的结果,从而证明了算法的可行性。最后,对算法的操作复杂度进行了分析。     

可满足性问题的巨磁电阻型DNA计算模型

DNA计算是一种新的计算模式,因其海量的信息存储能力、高度的并行性及低能耗等优点而被广泛地应用于求解各类NP完全问题.文中利用免疫磁标记和巨磁电阻(GMR)效应,对生物特异性反应进行检测,构建了可满足性问题的巨磁电阻型DNA计算模型,并用实例说明了模型的有效性和可行性.与传统的荧光标记法DNA计算模型相比,巨磁电阻型DNA计算模型的输出结果是电信号形式,因而具有检测信号易处理、检测时间短、解可靠性高、无需标记和读解简单等优点.     

DNA自组装的可满足性问题模型

DNA自组装技术在DNA计算和纳米技术领域都发挥着极其重要的作用,许多小规模NP完全问题都可以通过自组装模型得以解决.文中以可满足问题为模型,通过构造范式中变量的特殊补链,使其与初始数据库中初始DNA链发生杂交反应,形成发夹结构,利用形成发夹结构的DNA链与没形成发夹结构的DNA链长度不同的特点,通过凝胶电泳将这些带发夹的DNA链提取出来;然后加入与这些特殊补链完全互补的DNA链,在一定温度下,通过碱基互补配对原则,发夹结构又将被重新打开.该模型充分利用了DNA分子间的自组装能力,在计算过程中只需要用到凝胶电泳操作,在一定程度上大大减少了因生物操作过多而引起的各种实验误差.     

最大匹配问题的粘贴DNA算法

最大匹配问题(MMP)是图论中经典的组合优化问题。针对此问题提出了基于DNA粘贴计算模型的求解算法,阐述了该算法如何利用DNA链构建最大匹配问题的初始编码,说明了应用粘贴计算模型寻求最终解的生物操作过程,同时分析了此DNA并行算法的计算复杂度,最后给出了该算法的计算机模拟仿真结果和应用实例,得到了所给问题的最大匹配解,并对算法的可行性进行了验证和总结。     

粘贴与删除系统求解最短有向路的DNA计算模型

最短有向路问题是在一个有向网络中的两个指定顶点之间找出一条具有最小权的有向路,它在工程实践中具有广泛的应用。粘贴系统与删除系统是DNA计算形式模型中的两种基本模型。论文利用粘贴与删除系统的巨大并行性给出了求解图最短有向路问题的DNA计算模型及其实现算法。     

基于DNA粘附子模型的并行乘法算法

提出了一种基于DNA计算的粘附子模型的并行乘法算法,该算法首先将两个二进制数相乘转变成根据被乘数对乘数进行一系列的移位相加。将被乘数与乘数编码在同一条存储链上,通过组合、分离、设置、清除等四种运算计算出积的值。由于表示输出的DNA链的结构与表示输入的DNA链的结构相同,因此表示输出的DNA链无需做任何改变,就能在后面的运算中重复使用。该算法不仅能用于整数乘法中,还可以很方便地推广到包含小数的乘法运算及多个因数参与的乘法运算中。该算法的突出优点是充分发挥了DNA计算内在的并行计算性,如果参与乘法运算的因数的个数相等,则计算多组乘法运算与计算一组乘法运算所需的时间相同,并且多组乘法运算能从同一个试管内开始。     

基于粘贴和2-臂DNA模型的层次聚类算法

为了充分利用DNA分子在生物计算中的高度并行性和强大的存储能力,将DNA计算引入层次聚类实现对数据集的全局搜索。提出了粘贴模型与2-臂DNA分子相结合的混合模型求解最近邻层次聚类的DNA算法。针对二维数据空间,算法首先基于最小生成树思想产生图的边的所有组合链;其次筛选含n-1条边的链,基于边附着顶点,并选择包含全部顶点的复合链;再将复合链末尾连接相应边的权值片段,电泳出最短链;最后通过荧光分析法读解,得到最终的聚类结果。与已有文献同类算法对比表明,该算法在保持多项式操作时间下,更充分考虑连接边的长度,并将读解步骤数限定为常数步。     

基于粘贴系统的有向哈密顿路问题分析

通过构造粘贴模型模拟解决有向哈密顿路问题,然后用此粘贴系统所产生语言的性质对有向哈密顿路问题进行分析,继而给出了有向哈密顿路的充要条件。对于规模为n有向哈密顿路问题,构造的粘贴系统至多运行n-1步。     

DNA计算在产品创新设计中的应用

将DNA计算应用于产品创新设计的建模过程中。建立经验产品模型库,对产品的功能、结构、外观等因素进行DNA编码。针对用户需求,对目标产品进行编码,利用DNA计算实现联想记忆,构建计算模型。采用进化技术对建立的模型进行杂交、变异、布尔运算等创新操作,产生各种创新产品。通过一个桌子创新设计实例验证该方法的可行性和实用性。     

可满足性(SAT)问题的几种DNA计算模型

DNA计算是一种新的计算方式，其高度并行性和巨大的信息存储容量为NP-完全问题的解决提供了一种全新的方法。主要介绍了几种可满足性(SAT)问题的DNA计算模型，并在编码问题、实现方式、及算法设计等三个方面对其进行了比较。     

构造对角Ramsey图的DNA算法设计*

Ramsey数问题是一个著名的组合优化问题, 同时也是一个NP完全问题。构造对角Ramsey图是一个难处理的计算问题,使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸,穷举的DNA算法也不例外。提出了一个构造对角Ramsey图的递阶式DNA粘贴—剪接算法,该算法通过逐个添加顶点的思想, 逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解的空间扩散。特别地, 专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析, 分析结果充分地肯定了该算法的有效性。