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

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

基于部分字的DNA编码设计与分析*

DNA编码问题是DNA计算中的第一步也是最重要的一步,是DNA计算中的一个基本问题。引入部分字与其洞的定义,研究了部分字的洞与沃森—克里克汉明距离的内在联系,得到沃森—克里克汉明距离与DNA编码的关系;通过分析不完全匹配部分字中洞的出现位置,对发生错误匹配的DNA码进行了优化。解决了DNA编码中除去洞分散分布在DNA双链中的不完全匹配问题,有效弥补了杂交过程中出现的假阳性的缺陷,为DNA编码的研究注入了活力。     

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

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

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

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

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

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

基于差异性汉明距离的变分推荐算法

目前基于哈希技术的推荐算法常用汉明距离表示用户和项目哈希码的相似性,但忽略了哈希码中每位的潜在区别信息,为此提出了一个差异性汉明距离,通过考虑哈希码之间的差异性为哈希码赋予位权重;为差异性汉明距离设计了一个变分推荐模型,该模型分为用户哈希组件和项目哈希组件两部分,以变分自编码器结构连接。首先,模型利用编码器为用户和项目生成哈希码,为提高哈希码的鲁棒性,在哈希码中加入高斯噪声。其次,通过差异性汉明距离优化用户和项目哈希码,以最大限度地提高模型重构用户-项目评分的能力。在两个公开的数据集上的实验结果表明,在计算开销不变的前提下与最先进的哈希推荐算法相比,所提模型在NDCG上提高了3.9%,在MRR上提高了4.7%。     

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

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

DNA编码问题及其复杂性研究*

高质量的DNA编码可以避免DNA分子间的非特异性杂交,提高DNA计算的有效性和可靠性。首先对DNA编码的约束条件进行归类,分析了各编码约束对编码质量的影响;然后研究了编码质量、编码数量、序列长度与DNA计算可靠性、有效性、可扩充性之间的关系;最后通过类比DNA编码问题和图的独立集问题,说明了求解最大DNA序列集合问题是NP完全的。     

保护隐私的汉明距离与编辑距离计算及应用

随着信息技术的快速发展,在保护数据隐私的条件下进行多方合作计算越来越普及,安全多方计算已成为解决这类问题的核心技术。在科学研究及实际应用中,人们常根据两个字符串之间的汉明/编辑距离度量其相似程度,研究汉明/编辑距离的保密计算具有重要意义。文中主要针对汉明距离与编辑距离的两方保密计算问题进行研究。首先将汉明距离的计算问题转化为向量内积计算问题,应用加密选择技巧以及Okamoto-Uchiyama(OU)密码系统设计保密计算协议。然后通过对参与者字符串中各字符进行统一编号的方法,将编辑距离的计算问题转化为判定隐私数据的差是否为0的问题,应用OU密码系统设计编辑距离保密计算协议。应用模拟范例严格证明了协议的安全性,分析了协议的计算复杂性,测试了协议的实际执行效率,并与目前已有相关结果进行了分析比较。理论分析和实验结果都表明了协议的高效性。     

DNA计算中核酸序列设计方法比较研究

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

Speeding up the detection of evolutive tandem repeats

We recently introduced evolutive tandem repeats with jump (using Hamming distance) (Proc. MFCS’02: the 27th Internat. Symp. Mathematical Foundations of Computer Science, Warszawa, Otwock, Poland, August 2002, Lecture Notes in Computer Science, Vol. 2420, Springer, Berlin, pp. 292–304) which consist in a series of almost contiguous copies having the following property: the Hamming distance between two consecutive copies is always smaller than a given parameter e. In this article, we present a significative improvement that speeds up the detection of evolutive tandem repeats. It is based on the progressive computation of distances between candidate copies participating to the evolutive tandem repeat. It leads to a new algorithm, still quadratic in the worst case, but much more efficient on average, authorizing larger sequences to be processed.     

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序列不会产生不想要的结构,尤其是假阳性是解决此问题的关键.传统方法是要求码字间的Hamming距离足够大.因此考虑用部分字的方法来解决DNA编码问题,利用部分字的洞的定义及其性质得到了关于部分字的洞、Hamming距离和Watson-CrickHamming距离的3个命题,通过部分字对DNA编码进行了优化,解决了DNA编码中的部分疑难问题.     

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

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

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

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