基于纠错码编码理论的DNA编码研究*

作为一种新的计算模式,DNA计算有着强大的计算能力,编码问题在DNA计算中占据重要的位置,有效的编码设计能够提高DNA计算的可靠性。基于纠错码编码理论,提出了一种新的DNA编码方法,该方法可以找出具有一定长度且满足汉明距离约束的DNA编码序列。最后,给出了该算法的仿真,结果表明了该算法的有效性。     

DNA计算中编码序列的过滤函数研究

构造了用于DNA编码序列过滤的函数,并给出了DNA序列编码的算法,采用该文设计的过滤函数和算法所得到的DNA编码序列,能够满足一定的组合约束条件,并满足一定热力学条件,大大提高了DNA编码字的质量,有利于提高DNA计算的可靠性。     

基于最小自由能的DNA编码设计算法

为了提高DNA计算的有效性和可靠性,提出了一种启发式的全局搜索DNA编码算法.算法生成一组等长的DNA序列,这组DNA序列满足统一的解链温度约束和最小自由能约束.通过枚举所有可能的DNA杂交的二级结构,根据Nearest-Neighbors热力学模型计算出这些组合结构的最小自由能,可极大地提高DNA序列自由能的计算精度.该算法比传统基于汉明距离的DNA编码算法设计的DNA序列具有更好的稳定性和可靠性.     

求解TSP算法

首先提出旅行商问题(TSP),并将其转化为最短有向图哈密尔顿回路问题,然后介绍了三种类型的求解TSP的算法。第一种为传统算法,包括分支定界法、改良回路法、贪婪算法、MST算法、MM算法、插入法等;第二种为现代优化算法,包括模拟退火算法、人工免疫算法、遗传算法、蚁群算法、粒子群优化算法、禁忌搜索算法、Hopfield神经网络算法等;第三种为论文提出的DNA计算算法。并对这些算法的复杂度、误差范围以及优劣点进行了分析。     

基于粘贴DNA计算模型的数据存储技术

提出了一种新的基于粘贴DNA计算模型的数据存储技术的实现方法。该方法以重组DNA技术作为实现DNA数据存储的技术基础，以DNA计算理论研究中的粘贴模型作为信息编码工具。具体实现过程包括选择DNA载体，选择受体细胞，通过创建粘贴DNA计算模型的ASCⅡ字符编码进行信息编码，创建数据索引，最后实现数据的存储与检索。     

基于环形DNA分子的一种求解最大集团的计算模型

文中提出了一种基于环形DNA分子的新型计算模型.该模型的核心构成包括环形DNA分子,链霉亲和素包被的磁珠及环化酶.通过应用该模型解决了一个5个顶点的最大团问题,证明了该模型的可行性.在整个计算过程中,真解的搜索是借助于磁珠和环化酶,DNA分子结构在线性和环形之间相互转化.环形DNA分子的应用极大地减少了计算所需的时间和空间,算法的时间和空间复杂度均为O(n+m).对于解决一个n个节点的最大团问题,这种算法和枚举型算法相比,在搜索过程中所需试管数较少,只需n+1个试管,而利用枚举型算法则需要2n个试管.另外,文中构建的非枚举型初始解空间大大提高了DNA计算机的存储和计算能力.在将来,这种新型的DNA计算模型或许会成为一种解决某些NP完全问题的有效工具.     

图顶点着色问题的DNA计算模型

DNA计算是以DNA分子作为数据的一种新型计算模式.为了减少DNA计算中编码的数量,不降低生化实验操作的可靠性,文中建立了一种基于酶切技术和PCR技术的图顶点着色DNA计算模型,给出了实现该模型的双编码的编码方案.分析表明,利用酶切技术和PCR技术能够有效删除非解并读取真解.该模型的解的检测方法类似于DNA测序技术,使得该模型更容易实现自动化操作.     

一种邻域重心反向学习的粒子群优化算法

粒子群优化算法使用反向学习技术可以提高性能.然而,现有的反向学习粒子群优化算法仅采用粒子最大最小边界计算反向解,没有充分利用群体搜索经验.针对此问题,提出了一种邻域重心反向学习策略,使用邻域重心作为参考点计算反向解,充分吸收群体搜索经验的同时保持种群多样性;采用收缩因子拓展反向解搜索范围,增加找到更高质量解的机率.在典型的基准测试函数、CEC'13测试函数和一个实际工程优化问题上进行验证,实验结果说明了邻域重心反向学习策略的有效性和本文算法的竞争力.     

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

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

求解0-1规划问题的DNA计算模型(英文)

DNA计算是以DNA分子作为数据的一种新型计算模式．在DNA计算中首要面对的问题是编码问题．文中提出了一种双编码方法,利用这种编码方法可以使得在DNA计算的读解过程类似于DNA测序过程,容易实现自动化操作．基于该编码方法所建立的DNA计算模型可用于求解0-1规划问题,只需4次PCR反应即可读取问题的可行解．与其他DNA计算模型相比,该模型具有操作简单、易于实现的优点．