基于汉明距离的DNA编码约束研究

DNA计算是将现实问题进行编码映射到DNA分子上,通过生物实验产生出代表问题的解的DNA分子,最后通过检测技术提取出该DNA分子。高质量的DNA编码可以尽可能避免或减少计算过程中出现的错误,并使检测阶段易于提取出代表问题的解的DNA分子。对DNA编码约束进行了研究,分析了基于汉明距离的编码约束可以有效降低DNA分子间相似程度,减少DNA计算过程中DNA分子间的相互干扰,从而提高DNA计算的有效性和可靠性。还证明了基于汉明距离的编码约束存在等价的序列组合,降低了编码计算的复杂度。     

基于动态遗传算法的DNA序列集合设计(英文)

DNA编码序列的质量与数量直接影响着DNA计算的可靠性和规模,如何找到尽可能好的及尽可能多的DNA序列用于实际的应用一直是DNA计算的一个核心问题．文中首先介绍了研究DNA编码和DNA序列集合对DNA计算的意义,并给出了DNA序列设计的汉明距离和反汉明距离约束条件的定义．DNA序列集合的研究对DNA计算的可靠性和规模有着重要的影响,因此文中利用遗传算法和动态遗传算法来设计满足上述约束条件的DNA序列集合,通过对两种方法所得结果的比较,证明了动态遗传算法明显优于遗传算法．与此同时,将文中所得到的实验结果与前人的研究成果进行比较可知,文中的结果大幅提高了DNA编码的上界,从而进一步缩小了DNA编码界的取值范围．并且文中所给出的实验结果,对以后DNA编码的理论界的研究以及编码理论中关于4元码界的研究,提供了重要的参考值．     

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

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

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

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

基于遗传粒子群算法的DNA编码优化

DNA编码序列的设计是影响DNA计算可靠性的重要手段,该文从DNA编码设计应满足的多约束条件中选取适当的约束条件,针对这些约束条件提出每个DNA个体应满足的评估公式,采用遗传粒子群算法解决该多目标优化问题,并在不同的约束准则下将计算得到的序列与已有的DNA序列进行了对比。仿真结果证明了该方法的有效性。     

基于改进的粒子群遗传算法的DNA编码序列优化

在DNA计算中,DNA编码序列的设计是影响DNA计算可靠性的重要手段.在不同的DNA序列设计中,应该选择适当的约束条件,并且根据相应的约束条件提出每个DNA应该相应满足的评估公式.文中从DNA编码设计应满足的多约束条件中选取适当的约束条件,提出评估公式,并采用改进的粒子群遗传算法来解决多目标优化问题.同时根据得到的序列与已有序列在综合适应度函数结果上进行对比,结果证明了该方法的有效性.     

DNA计算中核酸序列设计方法比较研究(英文)

DNA计算是将现实问题进行编码,映射到DNA分子上,然后通过分子生物实验产生出代表问题解的DNA分子,最后通过检测技术提取出该DNA分子．高质量的DNA编码可以尽可能避免或减少计算过程中出现的错误,并使检测阶段易于提取出代表问题解的DNA分子．文中对基于汉明距离和基于自由能的DNA核酸编码方法进行研究,分析了两类方法的约束条件对DNA编码质量的影响,比较了两类方法排除非特异性杂交的完备性和计算量,进一步分析了两类方法编码DNA序列的效率．通过分析和比较得到,两类DNA计算编码方法都能有效地限制DNA分子间的非特异性杂交,其中基于汉明距离的DNA编码方法的计算量比较小,但是它仅能近似地估计DNA分子间杂交的热力学稳定性,不能完全替代最小自由能的编码方法．在满足DNA计算试验精度要求的条件下,采用基于汉明距离的DNA编码设计方法不仅能有效地的挑选出特异性杂交和非特异性杂交的DNA序列,还能有效地减少计算量,从而提高DNA序列设计的效率．     

一种基于编码等价变换和遗传算法的DNA序列优化设计

针对DNA计算中的DNA序列设计问题,基于6个DNA序列设计约束条件,将DNA序列设计问题转化为多目标优化问题,提出小生境遗传算法进行求解。算法利用DNA序列设计中的相似性约束与H-测度约束,在单链DNA序列集合上定义共享函数,利用两种类型的编码等价变换以及模4算术运算,构造了5个遗传算子,并给出具体的DNA序列设计结果。通过比较,算法可以得到质量更好的DNA序列,且在种群规模与进化代数方面具有更高的计算效率。     

基于聚类小生境遗传算法的DNA编码优化

DNA编码优化问题是DNA计算中的核心问题。分析DNA编码优化的约束条件,在单链DNA序列集合上引入h距离,将聚类小生境技术应用于小种群遗传算法的构造,对DNA编码优化问题进行求解。基于h距离定义DNA序列间的相似函数,将碱基字母编码为4进制整数、DNA编码序列作为个体编码为4进制整数向量、种群编码为4进制整数矩阵,基于模4算术运算,构造相应的遗传算子,并给出DNA编码序列的具体计算结果。实验结果表明,与现有DNA编码序列优化结果相比,该算法可得到更好的DNA编码序列且计算效率较高。     

基于文化进化粒子群算法的DNA序列设计

DNA编码序列的设计是影响DNA计算可靠性的重要途径,从DNA编码应满足的多约束条件中选取适当的约束条件,针对这些约束条件提出每个DNA个体应满足的评估公式以及目标序列集合的评价函数,采用文化进化粒子群算法解决DNA序列设计的多目标优化问题,仿真结果表明该混合算法针对DNA序列设计问题,在求解最优值能力,解的稳定性方面都取得了不错的效果。     

基于离散粒子群的DNA编码序列组合优化方法

本文分析了DNA编码序列设计的目标及需要满足的约束条件H-measure、连续性、相似度、发夹结构、GC含量等约束,建立一种组合优化评价模型,通过引入基于权重的适应度函数来评价DNA序列集合的优劣,最后提出基于该模型的离散粒子群优化算法(DPSO)生成有效的DNA编码序列.根据优化问题的约束条件及离散量的特点,对粒子的...     

基于h-距离的DNA编码序列设计

针对DNA编码序列设计问题,将其转换为带约束的多目标优化问题,在单链DNA集合中引入h-距离,构造了DNA序列间的共享函数,应用小种群遗传算法,对DNA编码序列设计问题进行求解。与已有结果比较,算法可以得到更好的DNA序列且计算效率较高。算法可用于DNA计算中编码序列的具体设计。     

Software Tools for DNA Sequence Design

The design of DNA sequences is a key problem for implementing molecular self-assembly with nucleic acid molecules. These molecules must meet several physical, chemical and logical requirements, mainly to avoid mishybridization. Since manual selection of proper sequences is too time-consuming for more than a handful of molecules, the aid of computer programs is advisable. In this paper two software tools for designing DNA sequences are presented, the DNASequenceGenerator and the DNASequenceCompiler. Both employ an approach of sequence dissimilarity based on the uniqueness of overlapping subsequences and a graph based algorithm for sequence generation. Other sequence properties like melting temperature or forbidden subsequences are also regarded, but not secondary structure errors or equilibrium chemistry. Fields of application are DNA computing and DNA-based nanotechnology. In the second part of this paper, sequences generated with the DNASequenceGenerator are compared to those from several publications of other groups, an example application for the DNASequenceCompiler is presented, and the advantages and disadvantages of the presented approach are discussed.     

最小自由能约束的DNA编码设计研究

首先介绍了DNA编码设计中自由能约束的重要性,以及自由能约束的计算公式,进而采用一种改进的蚁群优化算法来求解。仿真实验表明此算法产生一组能满足特定自由能约束和统一的解链温度约束的DNA序列,算法利用蚁群算法的并行性提高了编码设计算法的效率,利用最小自由能约束产生更稳定的DNA序列。     

隐私保护DNA序列汉明距离计算问题

DNA序列承载着人体重要的生物学信息，如何在保护隐私的情况下正确地对不同的DNA序列进行比对，成为亟待研究的科学问题。汉明距离在一定程度上刻画了两个DNA序列的相似程度，在保护隐私的情况下，研究DNA序列的汉明距离计算问题。首先定义了DNA序列的0-1编码规则，该规则将长度为n的DNA序列编码成长度为4n的0-1串，证明了两个DNA序列的汉明距离等于它们的0-1编码串的汉明距离的一半。以此结论为基础，以GM加密算法为主要密码学工具，构造了计算DNA序列汉明距离的一个安全两方计算协议。在半诚实攻击者模型下，证明了协议的正确性，给出了基于模拟器的安全性证明，并对协议的效率进行了分析。     

A hybrid quantum chaotic swarm evolutionary algorithm for DNA encoding

DNA encoding is crucial to successful DNA computation, which has been extensively researched in recent years. It is difficult to solve by the traditional optimization methods for DNA encoding as it has to meet simultaneously several constraints, such as physical, chemical and logical constraints. In this paper, a novel quantum chaotic swarm evolutionary algorithm (QCSEA) is presented, and is first used to solve the DNA sequence optimization problem. By merging the particle swarm optimization and the chaotic search, the hybrid algorithm cannot only avoid the disadvantage of easily getting to the local optional solution in the later evolution period, but also keeps the rapid convergence performance. The simulation results demonstrate that the proposed quantum chaotic swarm evolutionary algorithm is valid and outperforms the genetic algorithm and conventional evolutionary algorithm for DNA encoding.     

k-长DNA子序列计数算法研究

基因组的结构与功能存在密切联系，其功能主要通过DNA子序列来表达，因此研究DNA序列结构对于生物信息学来说具有重要的意义。该文研究了k-长DNA子序列在DNA全序列中出现频数的计数问题，设计并实现了k-长DNA子序列内部计数算法和外部计数算法。该算法通过一个哈希函数把k-长DNA子序列映射为整数关键字从而把k-长DNA子序列出现频数的计数问题转化为整数关键字的重复计数问题，使得能够利用经典B树算法来解决k-长DNA子序列的出现频数计数问题。针对所要解决的问题提出3种改进措施以进一步提高算法的性能。