陈芳，殷志祥

（安徽理工大学 数学与大数据学院，淮南 232001）

顶点着色问题是图论中一个经典的组合优化问题，属于NP完全问题，传统的算法无法有效的解决此类NP问题。随着分子生物学的发展，人们将DNA计算引入到NP问题中，着手利用DNA分子的高并行性和高信息储存量的优势来求解NP问题。1994年，Adleman教授[1]首次提出了使用生物分子来求解NP问题，并成功的求解了一个7个顶点的有向Hamilton路问题，开创了DNA计算的先河；文献[2]将图的顶点及颜色进行适当编码，借助生物酶的作用，实现了着色方案的生成与筛选；文献[3]建立了一种基于酶切技术和PCR技术的图顶点着色的DNA计算模型，使得模型实现充分的自动化操作；文献[4]将问题进行了转化，利用求解最大独立集的思想来进行编码，利用质粒DNA分子来进行试验，有效的得到了图的着色方案；文献[5]提出了一种基于微流控制来求解图顶点着色的DNA计算模型，实现了模型的自动化，提高了DNA计算的可靠性；文献[6]利用分子自组装，构建瓦片粘贴模型来求解图顶点着色问题，着色方案清晰易读；文献[7]构造了一个发夹结构探针，将顶点进行适当编码，直接生成解空间，利用常规生物操作即可获得着色方案。

DNA自组装是指DNA分子通过分子间的相互作用力，形成的一种较为稳定、结构更复杂的分子结构的过程。20世纪80年代，Seeman[8]就提出DNA能通过碱基互补配对产生稳定的连接结构，并且可以精确组装复杂多维空间对象，并称之为结构DNA纳米技术。在自组装技术诞生以来，人们利用该方法，求解了许多图论中的问题[9-16]。……