三维DNA自组装在多维背包问题中的应用研究

Application of 3D DNA Self-assembly in Multi-dimensional Knapsack Problem

利用DNA自组装执行计算的思想已从实验上被证明具有可行性。利用DNA瓦片自组装执行计算的方法,由于其通用性正被广泛研究,已有多种理论模型被提出以解决各种NP问题。基于DNA Tile自组装模型理论在三维下的扩展,设计了可以实现这一算法的三维DNA Tile组装系统。提出了一种用于解决多维背包问题的三维DNA自组装模型;该模型可以非确定性的输出可行性解决方案。分析表明系统可以在线性组装步骤内完成计算,所需的Tile种类数与问题维数无关。为探索三维DNA自组装的计算能力进行了一次有意义的尝试。

DNA computing by self-assembly has been proved scalable experimentally. Owing to its computational universalism, computing by self-assembly of DNA tiles is widely studied, and diversified theoretical models have been proposed to solve various NP problems. Based on 3 D extension of the Tile Assembly Model, a 3 D DNA self- assembly model for the knapsack problem is presented. The analysis shows that the tile types required in our model is independent to the size of the problem, and assembling time is linear. This study makes a significant attempt for exploring the computational power of 3D DNA self-assembly.