论文部分内容阅读
DNA计算是一种基于分子和相关酶之间某些生化反应过程的一种新的计算模式。不仅克服了电子计算机存储量小与运算速度慢这两个严重不足，而且表现出了高度并行性、海量存储能力、低能耗与资源丰富四大特点。但是随着DNA计算研究的深入，传统DNA计算模型显现出杂交错误率和生化操作复杂性过高的特点，如何提高DNA计算结果的准确性在DNA计算研究中日显重要。造成这种瓶颈有多方面的原因，DNA计算模型的选择和编码方案的设计是两个重要的因素。 针对NP完全最大团问题的DNA计算求解方法，大多数是利用粘贴、剪接模型等，虽然这些算法能够在多项式时间内提取给定图的最大团，但是其生化操作具有较高的复杂度。生化实验操作步骤越多，相应带来的实验误差也就越大，从而无法保证生化解的准确性。本文首先基于Winfree提出的Tiles自组装理论模型，定义了最大团问题的基本信息到Tiles分子粘性末端的映射。详细给出了初始格局阶段、判定格局阶段、检测格局阶段的编码设计方案，分析了基于这种设计方案Tiles的种类为()(n2)。基于Tiles自组装理论模型的数学描述，理论证明了该设计方案正确性。 然后基于Tiles自组装理论模型最大团问题的设计思路，本文利用双交叉DNA分子中的稳定结构DAE分子作为计算载体。根据DAE分子的结构特点，改进了Tiles自组装模型的数学描述。结合基本的生化实验操作方法，提出了一种求解最大团问题的DNA计算算法。算法过程中的DAE分子分为初始分子、规则分子、检测分子三种类型，且给出了DAE分子的详细设计方案。算法设计的DAE分子种类为()(n+|E|)，生化操作复杂性为()(1)，其中n为图的顶点数，|E|为边数。与求解最大团问题的其它DNA算法的对比分析表明，本算法不仅明显提高了生化解的准确性，且算法的生化实验复杂度低。