基于DNA折纸术求解图的顶点着色问题的方法

麻晶晶 许 进

①(山西财经大学统计学院 太原 030000)

②(北京大学信息科学技术学院 北京 100871)

1 引言

分子计算的设想是由Feynman[1]在20世纪60年代初首先提出的，他指出单个分子或原子能够被用来构建计算机的组成元件。1994年，Adleman[2]第1次通过生物化学实验求解了一个7个顶点的哈密尔顿路问题，说明了DNA计算在解决复杂的数学问题方面的能力。随着生物学和纳米技术的快速发展，分子计算也得到了极大的发展。许多不同的方法已经证明生物分子能够作为开发更好的计算系统和提高计算能力的新工具。各种不同的DNA计算模型被设计出来，如粘贴模型[3]、剪接系统模型[4]、表面与芯片DNA计算模型[5]、发夹状DNA计算模型[6]、质粒DNA计算模型[7]、基于k-臂的DNA计算模型[8]、自组装DNA计算模型[9]、插入－删除系统模型[10]、试管型DNA计算模型[11]、图灵机DNA计算机模型[12]、布尔DNA计算机模型[13]等，以及将DNA计算的思想应用于基因分析与疾病诊断与治疗的模型等[14]。2016年，Xu[15]提出了一种探针机模型，该模型能够求解当今电子计算机无法处理的NP完全问题。近些年来的研究表明，DNA计算在理论、模型构建、实验方法和检测技术上都取得了很大的进展。

与此同时，DNA自组装技术的研究也取得了巨大的进展。1998年Winfree等人[16]在“简单自组装瓦片结构”的基础上，构建了具有足够刚性的5种DX元件。2003年，LaBean教授的研究组构造出一种十字形的支架结构(即四星元件)[17]，利用这种模块组装成方形DNA自组装芯片。2006年，Rothemund等人[18]成功地应用了一条长为7000个碱基左右的M13噬菌体的单链，借助于200多条短的寡核苷酸链(钉书针链)，通过碱基互补，在特定部位折叠成复杂的2 维D N A 自组装结构。……