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序列的0-1编码规则，该规则将长度为n的DNA序列编码成长度为4n的0-1串，证明了两个DNA序列的汉明距离等于它们的0-1编码串的汉明距离的一半。以此结论为基础，以GM加密算法为主要密码学工具，构造了计算DNA序列汉明距离的一个安全两方计算协议。在半诚实攻击者模型下，证明了协议的正确性，给出了基于模拟器的安全性证明，并对协议的效率进行了分析。     

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

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

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

针对DNA计算中的DNA序列设计问题,基于6个DNA序列设计约束条件,将DNA序列设计问题转化为多目标优化问题,提出小生境遗传算法进行求解。算法利用DNA序列设计中的相似性约束与H-测度约束,在单链DNA序列集合上定义共享函数,利用两种类型的编码等价变换以及模4算术运算,构造了5个遗传算子,并给出具体的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序列集合问题是NP完全的。     

基于DNA计算的RNA序列多点“突变”与首段碱基的数字编码及其运算法则

RNA序列的高维空间二进制编码有以下优点:除可以对RNA序列的碱基结构、功能基团、碱基互补、氢键强弱等性质进行编码之外,还可方便的进行数学与逻辑运算。该文研究了RNA序列高维空间数字编码的更一般、更深刻的运算法则:(1)进一步研究RNA序列高维空间的表观维数NV,数值维数NX以及差异维数Nd,具体刻给出了当Nd=0,1,2,2n或2n+1(n=0,1,2,…)时,RNA序列的首段碱基及其数值取值范围。(2)推导出RNA序列多点“突变”(单核苷酸多态性SPN)的运算法则,将以前的结果推广到一般情形,深刻探讨了RNA序列之汉明距离、汉明值的变化及其数值变化情况。(3)利用RNA序列的定值部Xi和定位部Wi及其计算公式,从新的角度导出RNA重复序列的编码法则和运算法则,进而统一了以前的结果。     

基于汉明距离的文本相似度计算

传统的文本分类中相似度的计算,是根据欧氏空间中向量之间夹角的余弦值来表征的,它根据余弦值的大小来反映文本之间的相互关系。该文则首先建立文本集与码字集之间的1-1对应关系,然后借用编码理论中汉明距离的概念,由汉明距离的计算公式,得到了一种全新的文本相似度的计算方法,与传统的方法相比较,它具有简便,快速等优点。     

用线性码构造DNA计算编码的海明距离

最小海明距离是DNA计算编码性能的重要评价标准。利用线性码来构造DNA计算编码的最小海明距离是一种有效的方法,关键在于构造相应的监督矩阵。为了寻找监督矩阵,提出了监督矩阵的搜索算法和优化方法,及两个必要性定理;作为介于最小海明距离上限与下限之间的编码存在性的判断依据,给出了两个关于线性码存在性定理;最后给出了三字母表DNA计算编码相关的监督矩阵搜索算法结果,以及当最小海明距离一定时,接近编码数量上限的部分线性码的存在性结果。根据这些结果和存在性定理,可以推断常用DNA计算编码最小海明距离的存在性。     

A Linear-Time Algorithm for Hamming Distance with Shifts

The Hamming distance with shifts was introduced by Bookstein et al. as a generalization of the traditional Hamming distance to allow a tunable degree of fuzziness when comparing two binary sequences of the same length. We present a linear-time algorithm for computing this distance. The previous best time bound was quadratic.     

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

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

区间复模糊软集的距离测度及其应用

基于区间复模糊软集的概念,定义了多种区间复模糊软集的距离测度公式,包含Hausdorff距离、Hamming距离、Euclidean距离、广义Hausdorff距离、广义Euclidean距离、广义加权Hausdorff距离、广义加权Euclidean距离、加权Hausdorff距离、加权Hamming距离、加权Euclidean距离。提出了除交、并、补运算外的区间复模糊软集的加法、乘法、部分隶属度和部分非隶属度运算以及距离测度之间的运算性质。基于区间复模糊软集距离测度构造了一种TOPSIS决策方法,并将这种决策方法应用于经济分析中,验证了所提方法的可行性。     

DNA编码限制条件与编码策略

以评价DNA编码的基本限制条件之一——Hamming距离为出发点分析了DNA编码的三个参量：码字个数、码字长度与Watson-Crick Hamming距离,并得到它们之间的内在联系;讨论了Watson-Crick Hamming距离与DNA码字重量之间的关系;在此基础上得到了DNA编码的编码策略;提出了适合DNA编码的改进Watson-Crick Hamming距离及DNA编码模块化的定义,对DNA编码的优化做出了详细分析,为DNA计算的发展注入了活力。     

一种基于相对海明距离的地图复杂性度量

提出一种适用于分层路径搜索算法的地图复杂性度量方法。针对不同规模的地图,将其实际复杂度与可达到的最大复杂度之比作为相对复杂度,提出基于相对海明距离的度量方法,并引入地图区域间方差,从而更好地计算障碍物分布不均匀地图的复杂度。实验结果证明,该方法能准确地反映不同规模与障碍物分布不均的地图复杂程度,并与HPA*算法的搜索效率有较强关联性。     

用于DNA编码的部分字

寻找合理的DNA编码是DNA计算中一个基本的问题.因此要给出一种方法使得DNA序列不会产生不想要的结构,尤其是假阳性是解决此问题的关键.传统方法是要求码字间的Hamming距离足够大.因此考虑用部分字的方法来解决DNA编码问题,利用部分字的洞的定义及其性质得到了关于部分字的洞、Hamming距离和Watson-CrickHamming距离的3个命题,通过部分字对DNA编码进行了优化,解决了DNA编码中的部分疑难问题.