基于杂交链式反应工序问题的DNA计算模型

DNA computing model for process problem based onhybridization chain reaction

杂交链式反应是一种无酶参与的自主组装反应.文章利用杂交链式反应和折纸术给出工序问题的求解过程.首先,将工序问题映射为一个有向图,将调整时间之和t+(Ji)最小的点作为根节点,将问题映射为一个有向树.然后,将有向树锚定在矩形的折纸基底上,利用杂交链式反应来求解问题的最优解.此模型在试管中进行,只有加入了启动链以后,反应才可进行.当发夹结构打开后,反应是不可逆的,最终生成的都是以根节点为起点,以叶子为终点的有向路径.最后,利用荧光光谱仪检测每条有向路上的荧光个数,从而确定问题的最优解.通过仿真可得该模型的复杂度为Θ(depth(T))+Θ(n).

Hybrid chain reaction is an enzyme-free self-assembly reaction.In this paper,hybrid chain reaction and origami are used to solve process problems.Firstly,the process problem is mapped to a directed graph.The point where the sum of the adjustment times t+(Ji)is the smallest as the root node.After that,the problem is mapped to a directed tree.Then the directed tree is anchored on the rectangular origami base,and the hybrid chain reaction is used to solve the optimal solution of the problem.The model is carried out in a test tube,and the reaction can be carried out only after the start-up chain is added.When the hairpin structure is opened,the reaction is irreversible.Therefore,the final generated directed path is based on the root node as the starting point and the leaf as the end point.Finally,the fluorescence number of each directed path is measured by fluorescence spectrometer to determine the optimal solution of the problem.The simulation result show that the complexity of the model isΘ(depth(T))+Θ(n).