论文部分内容阅读
随着DNA计算机研究的不断深入,如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重要内容之一.为设计可扩展的子集和问题DNA计算机算法,文中将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,通过设计DNA并行搜索器,提出一种求解子集和问题的DNA计算机模型和算法.与已有文献结论的对比分析表明:文中算法在保持多项式生物操作复杂性的条件下,将穷举算法中的DNA分子链数从O(2n)减少至O(1.414n),其中n为子集和问题的维数.因此,文中算法理论上在试管级生化反应条件下能将可破解子集和公钥的维数从60提高到120.
With the deepening of DNA computer research, how to overcome the limit of exhaustive method in DNA biology computing has become one of the important contents of DNA computational research.In order to design scalable subsets and problem DNA computer algorithms, the Aldeman-Lipton model Combined with the solution space of the pasting model, the introduction of fluorescence labeling and gel electrophoresis technology, through the design of DNA parallel search engine, a DNA computer model and algorithm for solving subsets and problems is proposed.Comparison with the existing literature conclusion : The algorithm reduces the number of DNA molecular chains in the exhaustive algorithm from O (2n) to O (1.414n) under the condition of maintaining the complexity of polynomial biological operations, where n is the dimension of the subset and the problem. Therefore, In this paper, the algorithm theoretically increases the dimensionality of crackable subsets and public keys from 60 to 120 under test-tube biochemical reaction conditions.