马　莹，方　欢

安徽理工大学理学院,安徽淮南，232001



地图着色问题的DNA计算

马莹，方欢

安徽理工大学理学院,安徽淮南，232001

提出了将地图着色问题转化为顶点着色问题，然后把顶点着色问题转化为求最大独立集问题。最大独立集问题的解法采用改进的粘贴DNA计算，即全信息化的DNA粘贴计算。DNA粘贴计算设计了主链和存储链，而且在生物计算中采用并行处理。最后给出了一个实例,详细说明了地图着色问题的解法，得出了最终的解。

DNA计算；粘贴计算；地图着色问题；顶点着色；最大独立集

1994年，Adleman首次用DNA计算解决有向图的哈密顿问题[1]，此后许多研究者对DNA计算进行研究。粘贴模型是由Roweis等人于1996年提出的一种DNA计算模型[2]，给出了图的最大团与最大独立集粘贴DNA计算模型[3]，特别是许进教授的文献[4-5]对DNA粘贴计算的研究有很大的意义。文献[6]把地图着色问题转化成可满足性问题，并采用多级分离装置来实现，文献[7]采用分子信标表面技术实现地图着色问题的DNA计算，文献[8]给出了图的最小顶点覆盖问题的DNA计算，文献[9] 给出了最大匹配问题的粘贴DNA算法。文献[10] 用微流控DNA计算解决图着色问题的DNA算法。本文提出了全信息化的DNA粘贴计算模型。

1　基于DNA计算的粘贴模型

1.1粘贴模型

粘贴模型的DNA分子的编码是一种单链和双链混合的序列，存储混合物由两种类型的单链组成：一种是存储链，另一种是粘贴链。一个存储链含有K个不重叠区域的单链DNA分子，其中不重叠区域有M个碱基；粘贴链也是单链DNA分子，可以设计M个碱基的粘贴链与存储链中的DNA单链分子恰好构成互补。……