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

作者：杨静; 殷志祥^*; 唐震; 杨新木

来源：广州大学学报(自然科学版), 2020, 19(01): 14-41.

• 杂交链式反应
• DNA折纸术
• 工序问题
• 分子信标

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

• 单位
  安徽理工大学; 上海工程技术大学