精确覆盖问题的O(1.414~n)链数DNA计算机算法

DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法.算法由初始解空间生成算法Init()、冗余解删除算法IllegalRemove()和并行搜索器ParallelSeacher()共3个子算法组成.与同类算法的性能比较分析表明:本算法在保持多项式生物操作复杂性的条件下,将求解n维精确覆盖问题的DNA链数从O(2n)减少至O(1.414n),从而将DNA计算机在试管内可求解的精确覆盖问题集合的基数从60提高到120,改进了相关文献的研究结果.     

基于分治的子集积问题DNA计算机算法

如何减少DNA计算机在求解大型科学问题中以问题输入纯指数增长的DNA链数，已成为DNA计算机研究的重要内容。本文将分治策略应用于子集积问题的DNA分子计算中，提出一种求解子集积问题的新的DNA计算机算法。该算法由n位数据搜索器和其它五个子算法组成，其DNA链数可达到亚指数的O（2^q/2），其中q为子集积问题的维数。与最近文献结结论进行的对比分析表明：新算法将求解子集积问题所需的DNA链数从O（2^q）减少至O（2^q/2），最大链长度减少为原来的1／2。因此，利用新算法在试管级水平上能将可
破解的子集积公钥的维数从60提高到120。     

基于分治的背包问题DNA计算机算法

如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容.将分治策略应用于背包问题的DNA分子计算中,提出一种求解背包问题的新的DNA计算机算法.算法由n位并行减法器、n位数据搜索器和其他4个子算法组成.算法的DNA链数可达到亚指数的O(2q/2),其中q为背包问题的维数.与最近文献结论进行的对比分析表明:算法将求解背包问题所需的DNA链数从O(2q)减少至O(2q/2),最大链长度减少为原来的1/2,因此,理论上新算法在试管级水平上能将可破解的背包公钥的维数从60提高到120.     

一种最大匹配问题DNA计算算法

DNA计算作为基于生化反应的一种新的计算模式,凭借其巨大的并行性和海量的存储能力已经成为解决NP难题的潜在解决方案之一.把传统计算机中的剪枝技术引入到DNA计算算法的设计中,提出一种基于Adleman模型生物操作与粘贴模型解空间的最大匹配问题DNA计算新算法.算法由图编排器、预解空间生成器、匹配生成器及最大匹配搜索器组成.与已有同类算法的对比分析表明:该算法在保持多项式操作时间的条件下,将求解最大匹配的解空间从O(2m)减少到O(1.618m),将DNA计算机在试管内可求解的最大匹配问题的规模从60(260≈1018)提高到86(1.61886≈1018).同时,与传统的穷举算法相比,该算法具有高效的空间利用率及容错技术的优点.     

基于质粒分子数子集O（1．414^n）DNA计算机算法

文章提出了一种求解背包问题的新的基于质粒DNA计算机算法.本算法的DNA链数可达到亚指数的O(1.414n),其中n为背包问题的维数.将提出的算法与已有文献结论进行的时比分析表明:本算法将穷举算法中所需的DNA链数从O(2n)减少至O(1.414n),因此利用本DNA计算机算法在试管级水平上能将可破解的背包公钥的维数从60提高到120,显示出了一定的优越性.     

一种改进的最大团问题DNA计算机算法(英文)

随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中,提出一种最大团问题的新DNA计算机算法．算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成．与已有文献同类算法的对比分析表明：文中算法在保持多项式操作时间的条件下,将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O（2^n）减少至O（√3^n）,同时文中算法还具有高效的空间利用率及容错能力的优点．     

基于自组装模型的最大团问题DNA计算算法

DNA计算在解决NP完全问题时,有着传统图灵机无法比拟的优势.但是随着DNA计算研究的不断深入,传统DNA计算模型显现出杂交错误率和生化操作复杂性过高的缺点.如何提高DNA计算结果的准确性在DNA计算研究中日显重要.针对NP完全的最大团问题,引入DNA自组装模型,提出了一种求解最大团问题的DNA计算算法.算法通过减少实验的操作步骤数,以降低生化解的错误率,给出了DNA分子的编码方案及结果检测的实验方法.算法设计的tiles种类为(O)(n+|E|),生化操作复杂性为(o)(1),其中n为图的顶点数,|E|为边数.与求解最大团问题的其他DNA算法的对比分析表明,本算法不仅明显提高了生化解的准确性,且算法的生化实验复杂度低,具有良好的实验操作性.     

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

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

一种基于DNA计算的指定结点路由算法

带指定结点约束的路由问题是一个NP难问题,该问题是电信行业路山智能化和交通电力运输等领域的关键问题之一.基于DNA计算的高度并行性,文中提出一种将电子计算机与DNA计算机相结合的方法求解指定结点路由问题.算法由转化算法Transform()、首末结点搜索切割算法FirstEndSearcher()、转化图结果搜索算法DNASearcher()和结果读取算法ResultReader()共4个子算法组成.分析表明:算法的电子计算机部分缩小了问题结点和边的规模,从而使解决问题所需的DNA分子链数数量级从O((n-2)!)减少至O((m-2)!)(n≥2为图中结点数,m≥2为图中指定必经结点数).算法的DNA计算机部分采用了有针对性的DNA编码新方案,提高了边权值编码的信噪比,通过一系列生物操作,筛选出问题的精确解.和单纯DNA超级计算或电子计算机指定结点路由算法相比,文中算法可显著扩大理论上待求解问题的规模.     

Fast Parallel Molecular Algorithm for Solving the Discrete Logarithm Problem over Group on Zp+ DNA-based Computing

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用.研究一种加群Zp+上离散对数问题的DNA计算算法.算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成.其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间.本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数).最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性.     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

Molecular Verification of Rule-Based Systems Based on DNA Computation

Various graphic techniques have been developed to analyze structural errors in rule-based systems that utilize inference (propositional) logic rules. Four typical errors in rule-based systems are: redundancy (numerous rule sets resulting in the same conclusion); circularity (a rule leading back to itself); incompleteness (deadends or a rule set conclusion leading to unreachable goals); and inconsistency (rules conflicting with each other). This study presents a new DNA-based computing algorithm mainly based upon Adleman's DNA operations. It can be used to detect such errors. There are three phases to this molecular solution: rule-to-DNA transformation design, solution space generation, and rule verification. We first encode individual rules using relatively short DNA strands, and then generate all possible rule paths by the directed joining of such short strands to form longer strands. We then conduct the verification algorithm to detect errors. The potential of applying this proposed DNA computation algorithm to rule verification is promising given the operational time complexity of O(n*q), in which n denotes the number of fact clauses in the rule base and q is the number of rules with longest inference chain.     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

一种加群Z上离散对数问题的DNA计算算法

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用。研究一种加群Zp+上离散对数问题的DNA计算算法。算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成。其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间。本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数)。最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性。     

A Fast Approximation Algorithm for the Subset-sum Problem

The subset-sum problem (SSP) is defined as follows: given a positive integer bound and a set of n positive integers find a subset whose sum is closest to, but not greater than, the bound. We present a randomized approximation algorithm for this problem with linear space complexity and time complexity of O( n log n ). Experiments with random uniformly-distributed instances of SSP show that our algorithm outperforms, both in running time and average error, Martello and Toth's (1984) quadratic greedy search, whose time complexity is O( n ²). We propose conjectures on the expected error of our algorithm for uniformly-distributed instances of SSP and provide some analytical arguments justifying these conjectures. We present also results of numerous tests.     

On the scalability of biocomputing algorithms: The case of the maximum clique problem

The paper aims at demonstrating and confirming that breadth first search or pruning techniques can substantially improve the effectiveness of biomolecular algorithms. A breadth first search-based DNA algorithm solving the maximum clique problem for a graph is presented, and its complexity and scalability parameters are studied. The analysis shows that parameters like the number of steps, the length and volume of DNA strands, the number of enzymes and the concentration of the molecules encoding solutions are dramatically improved in comparison with previous approaches to the same problem and, theoretically, they would allow to process graphs with thousands of vertices. These parameters are also compared with several related results focusing on the scalability of DNA computing methods. Finally, an analysis of error-resistance of the algorithm is given.