基于自组装纳米颗粒的顶点着色问题的DNA计算模型

陈芳，殷志祥

（安徽理工大学 数学与大数据学院，淮南 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]。文献[17]结合3维的DNA自组装模型求解了图顶点着色问题，利用DNA分子的巨大并行性，在线性时间内求得了最佳方案。纳米材料作为一种新材料，已经被广泛应用于生物学领域，具有制备便宜、生物稳定性好等天然优势。结合自组装纳米材料，文献[13]求解了最大团问题，在生成和删除非解只需操作一次即可，简化了传统模型的操作过程。该文借助纳米金属颗粒来求解图的顶点着色问题，利用DNA自组装，将纳米颗粒组装成所需要的结构，通过碱基的互补配对原则生成和筛选着色方案。由于DNA分子的巨大并行性，将会有效的减少运算的时间和空间复杂度。

1 顶点着色问题

在本文中提到的图均是指有限、无环、无重边的无向简单图。通常用V(G)和E(G)分别表示图的顶点集和边集。图G的顶点着色问题就是指给图G的每一个顶点进行着色，并且使得任意相邻的两个顶点分配到不同的颜色。而求顶点着色问题又可以转化为求最大独立集问题，也就是说，简单图G的一个k-顶点着色，就是将顶点集V(G)划分成k个独力集的分类{v1,v2…vk}，其中vi(i=1,2…k)是G的独立集，满足v(G)=v1⋃v2⋃…⋃vk，vi≠∅ ，vi⋂vj=∅，i,j=1,2…k。如果用集合C(k)表示k种颜色，则有C(k)={1,2…k}。更确切地说，求解图顶点着色问题就是寻找从顶点集v(G)到颜色集C(k)的一个映射f:v(G)→C(k)，并且映射f满足u,v∈V(G),uv∈E(G)，f(u)≠f(v)。记全体G的k-着色f构成的集合为Ck(G)，当集合Ck(G)≠∅的时候，称图G是k-顶点着色的。在本文中，仅考虑图的3-顶点着色，图1为一个具有6个顶点的简单图。

图1 6个顶点的简单图

2 计算模型

2.1 基本算法

步骤1 利用自组装的金属颗粒对应每个顶点；

步骤2 利用DNA碱基互补配对生成数据池；

步骤3 删除不满足条件的解；

步骤4 输出着色方案。

2.2 生物算法

步骤1（1）构造代表顶点的纳米金属颗粒：纳米金属颗粒由两部分组成，主体结构为纳米金属颗粒，并且每个金属颗粒都带有连接DNA。在图1的3-着色问题中每个顶点有三种方案可选择，因此针对于每个顶点，需要设计3种不同的纳米金属颗粒。在n个顶点的图中，一共需要构造3n个纳米金属颗粒。

（2）构造连接探针：根据步骤（1）中的连接DNA，构造连接探针，连接探针由两部分组成，第一部分与前面相接的纳米金属颗粒的连接DNA互补，第二部分与后面相接的纳米金属颗粒的连接DNA互补。在具有n个顶点图的3-着色问题中，需要个3×3×(n-1)=9(n-1)个连接探针。

步骤2 将纳米金属颗粒同连接探针加入到溶液中进行生化反应，根据碱基互补配对会生成串珠状结构，即初始数据池。

步骤3 在数据池中，含有非解，需要进行筛选。构造删除探针，删除探针结构与顶点的结构相同，主体部分为纳米金属颗粒，两端连接有单链DNA，两端的单链DNA分别是相邻顶点的连接DNA的补链。这样将删除探针加入到数据池中后，如果相邻两个顶点着相同颜色，删除探针会与代表该方案的串珠进行杂交反应，串珠的质量与结构会发生改变。

步骤4 借助凝胶电泳技术来对非解进行剔除，因为数据池中的非解在加入删除探针过后，质量与体积都会增大，在进行电泳分离的过程中，非解的移动速度慢，因此可以通过分离来得到解。最后采用非放射性标记DNA测序的方法进行测序，可以具体得到每个顶点的着色方案。

3 算法实例

结合图1为例，求解图的3-着色问题。

步骤1（1）将图1的每一个顶点对应自组装为纳米金属颗粒，因为每个顶点都有三种可着色的情况，因此针对于每个顶点，需要设计三种不同的带有特定单链的DNA纳米金属颗粒。并且为了方便后续对解的检测，所选取的每个纳米颗粒的分子量都是相同的，这使得他们在凝胶电泳中的迁移速度是相同的。当顶点为红色（R）时，对应于纳米金颗粒，记为Rn；当顶点为绿色（G）时，对应于纳米银颗粒，记为Gn；当顶点为黄色（Y）时，对应于纳米铜颗粒，记为Yn。（其中n表示的是顶点编号，如R1代表顶点1为红色，G2代表顶点2为绿色）。每一个代表顶点的纳米颗粒都有一个线性的单链DNA与其连接，称它为连接DNA（这样自组装可以使得代表顶点的纳米颗粒与其他的纳米颗粒能够相连接）。并且应该注意到，为了使代表顶点的纳米颗粒能够按照顺序进行连接，需要将序号位于首尾的顶点组装一条连接DNA，序号位于中间的顶点组装两条连接DNA。在此设计纳米金属颗粒的连接DNA：纳米金颗粒上的连接DNA用Sn来表示；纳米银颗粒上的连接DNA用Mn来表示；纳米铜颗粒上的连接DNA用Ln来表示。（其中n表示的是顶点编号，如S1代表顶点1为红色的连接DNA，M1代表顶点1为绿色时的连接DNA，也可更进一步表示为R1-S1和G1-M1）。通过观察图1可知，顶点1、5，顶点2、4，顶点1、6也是有边连接的，为了后面对这些不是通过邻边连接的顶点进行筛选操作，需要加上可对顶点1、2、4、5、6进行识别的探针，并将其记为d。部分顶点的设计如图2[13]所示。

图2 部分顶点的设计

（2）以上设计了代表顶点的纳米颗粒以及连接DNA，现在为了使每个顶点能够进行有序连接，需要设计能够将顶点进行连接的探针。探针共由两部分组成：第一部分与前面所连接的纳米颗粒的连接DNA互补，第二部分与后面所连接的纳米颗粒的连接DNA互补。在图1中，所要研究的是3-顶点着色问题，因此每个顶点有三种连接DNA。由于图1具有6个顶点，要满足依次相连，需要5个连接探针，因此一共需要设计(3×3×5=45)种连接探针，连接探针的具体设计见图3。

图3 连接探针的设计

在依次相邻的顶点中，若要满足顶点着色的定义，两个相邻的顶点一定不能连接相同的颜色，所以不需要设计相邻顶点颜色相同的连接探针，即无需设计图3中虚线框中的连接探针。

步骤2 将代表顶点的纳米金颗粒和连接探针同时加入到溶液中进行生化反应，由于连接探针的设计，纳米金颗粒会按照顶点的序号依次进行排列，即生成了初始的数据池，并且该数据池满足依次排列的顶点着不同的颜色。部分结果图4所示。

图4 数据池的生成

步骤3（1）在按照上面的方法，生成了所有可能的三着色情况，并且满足了在序号依次排列时，每相邻的两个顶点为不同的颜色。现在需要对其他相邻的两个顶点的颜色进行检验，即删除部分不满足条件的解。结合图1来看，除了依次相邻的顶点连接，还有顶点2、4，顶点1、5，顶点1、6相连，为了满足这个三组相邻的顶点也互相为不同的颜色，需要设计相应的删除探针，记为探针Dn-m（其中n、m分别指在图中有被邻边之外的边所连接的顶点）。删除探针的主体结构为纳米金颗粒，两端连接有单链DNA。删除探针的结构如图5所示。

图5 删除探针的设计

（2）在初始数据池中，加入删除探针，如果相邻的两个顶点着相同的颜色，可以对其进行检测。由于删除探针两端所连接的单链DNA与顶点上的识别探针互补配对，通过杂交反应可以形成新的结构。如果数据池中的解满足顶点着色的条件，那么，加入的删除探针不会与纳米颗粒串珠发生反应，游离在溶液中。假设顶点2、4着相同的颜色，在遇到删除探针D2-4时，两者会进行杂交反应，形成新的结构，形成过程如图6所示。

图6 删除探针杂交过程

步骤4 在数据池中加入删除探针后，含有非解的串珠链会同删除探针进行配对杂交，形成新的结构，加入了删除探针后的串珠链总的分子量变大，在凝胶电泳中的迁移速度会变慢。通过凝胶电泳技术，观察串珠链的运动速度，回收运动速度较快的串珠链，此时所得到的串珠链都是满足相邻点为不同颜色的串珠链。最后采用非放射性标记DNA测序的方法进行测序，得到顶点着色问题对应的解。

4 复杂度分析

时间复杂度：在本文中讨论的是3-顶点着色，而每一个顶点的着色颗粒需要一个单位的操作时间，所以需要3n个操作时间；为了检测着色方案，需要设计删除探针，假设在图中有m条边不是通过邻边所连接的，因此共需要设计3m个删除探针，消耗了3m个操作时间；在生成和删除解时各占用一个时间单位。因此该模型的时间复杂度为ο(3n+3m+2)。

空间复杂度：每个顶点的需要3个不同的纳米金颗粒来代表不同的颜色选择，所以占据了3n个空间单位；同理于时间复杂度，删除探针也占据3m个空间单位；在生成和删除解也各需要占用一个空间，因此该模型的空间复杂度也是ο(3n+3m+2)。

5 结论

本文通过自组装纳米颗粒来求解图的3-顶点着色问题。将图的顶点和边分别转化为纳米颗粒和DNA片段，利用生物分子的巨大并行性来生成数据池。在删除非解时，直接使用凝胶电泳技术即可，避免了在加热、解链、退火过程中产生伪解的可能，与以往借助限制性内切酶删除解的模型相比，自组装模型更具有通用性，应用范围更广。