家庭旅行商问题的三链DNA 计算模型

蒋天怿， 杨 静

（安徽理工大学，安徽 淮南 232001）

长期以来，人们对于著名的NP-完全问题——旅行商问题（Traveling Salesperson Problem，TSP）的求解方法进行了大量的研究，但家庭旅行商问题（Family Traveling Salesperson Problem，FTSP）是近期才被提出的。2013 年，Moran-Mirabal 等首次提出了FTSP 的定义[1]。2021 年，Bernardino 和Paias 提出了2 种元启发式算法来求解FTSP[2]。

1994 年，Adleman 首次利用DNA 计算方法解决了7 顶点的Hamilton 路径问题，开拓了DNA 计算的新纪元[3]。自1957 年Davies 等报道三链DNA 的存在以来，其就被用来解决一些问题，如背包问题、邮递员问题等[4-5]。基于此，本文将尝试利用三链DNA 计算模型来解决FTSP。

1 三链DNA 结构

1957 年，Felsenfield 等发现1 条人工合成的腺嘌呤核糖核苷酸的均聚物能和2 条人工合成的尿嘧啶核糖核苷酸的均聚物形成三链DNA 结构[6]。三链在形成或分离过程中，不易错配或形成发夹结构，且反应前的数据池中皆为双链，在常温下即可操作实现，实验条件较为简单。因此，基于三链的DNA 计算而产生的错误率和编码的复杂度会大大降低，其可用来研究组合优化问题中一些可能的或者可行的计算模型。

2 FTSP 问题

若使用图论的语言，FTSP 可以描述如下：在无向完备图G=（V∪{0}，E）中，0 是原点，V是除了原点0以外的所有顶点的集合，E是不同顶点i与j之间距离的集合，使得d（i，j）＞0，其中顶点i到j的距离和j到i的距离是一样的，故d也可以称为各边的权值。在FTSP 中，具有N个顶点的顶点集合V被划分为h个不同的族vk，其中k为族的索引，且vi∩vj=Ø（i≠j），其表明1 个族内包含多个顶点，但1 个顶点只能属于1 个族。记nk为各个族的顶点数，则顶点数。给定1 个有N个顶点的无向完备图，需要访问M（M≤N）个顶点，给定每个族mk中需要访问的顶点个数，使得。最终目标就是找到访问M个顶点数的最小总路径的往返。

3 FTSP 的三链DNA 算法实现

基于图G=（V∪{0}，E），三链DNA 计算模型的算法步骤如下：

步骤1：对图G的各点以及弧进行精心DNA 编码，将其所对应的寡聚核苷酸片段充分混合，并加入缓冲液、DNA 连接酶使之进行连接反应，生成关于图G的所有途径。还需加入大量聚合酶和引物，不断扩增DNA 分子，使所有单双链都以双链的形式存在，以增加链的稳定性。对反应后的产物进行聚合酶链式反应（Polymerase Chain Reaction，PCR）扩增，让那些起止于原点的链成指数倍增加。保留这些DNA 链，进行纯化处理并分离，把最终所得双链作为初始数据池。

步骤2：在每个顶点补链的单链5′端添加1 个聚酯纤维，再标记生物素。使这些单链和抗原蛋白质在含有腺苷5′-（3-硫代三磷酸）四锂盐（Adenosine5′-3-thiotriphosphate tetralithiumsalt，ATPγS）溶液里混合，生成核蛋白细状体，作为模板，构造DNA 探针。

步骤3：将顶点探针混合到数据池中，将与对应双链结合生成3 链。利用分离操作将没有生成3 链的双链除去，并利用链（霉）亲和素的高度亲和力将所有含有此顶点的3 链分离出来，再形成双链，此时数据池中的双链一定含有此顶点。

步骤4：根据约束条件，重复步骤2 和3，对数据池中的链逐步筛选，可得所需的DNA 链，即可行解。

步骤5：对步骤4 产物进行琼脂糖浆凝胶电泳。切割出长度最短的链，并进行测序，选出代表最优解的链，输出结果，即FTSP 的最优旅行路线。

4 实例分析

4.1 实例

为了说明三链DNA 计算模型的有效性和正确性，本文给出了1 个小规模实例burma14，该实例来自TSPLIB，各城市分布坐标如图1 所示。其中N=13，n1=4，n2=5，n3=4，m1=m2=m3=2，0→1→2→13→6→12→7→0 为满足条件的可行路线。接下来就根据前文所提到的算法实现所对应的生化操作。

图1 无向完备示意图G

4.2 实例操作

1）DNA编码

为规范算法表达，其编码方式如下：

对各点进行等码长编码：

其中qk是用来区分不同族的顶点，令以原点为起点的编码为#A0B0，以原点为终点的编码为A0B0#。

对弧进行不等码长编码：

2）生成初始数据

利用上述编码生成初始数据，首先通过几步生化反应得到从原点开始并返回原点的解：

Step 1生成从原点开始并返回原点的初始数据（1-1）（1-2）（1-3）（1-4）（1-5）（1-6）（1-7）（1-8）Merge（P，Q）Linkaging（P）Amplification（P）PCR（P，{#A0B0，A0B0#}）Separation（P，{#A0B0}，T0）Discard（P）Separation（P，{A0B0#}，T0）Discard（T0）；

操作（1-1）是将含有点vi和弧vivj的大量寡聚核苷酸片段分别储存在管P和管Q，并混合，即P=P∪Q且Q=Ø。（1-2）和（1-3）表示加入缓冲液、引物、聚合酶等，生成稳定结构的双链DNA。（1-4）是对反应后的产物进行PCR 扩增，使得起止于原点#A0B0、A0B0#的DNA 链成指数倍增加。操作（1-5）—（1-8）则表明进行纯化处理，先将含有#A0B0的DNA链保留在临时管T0中，丢弃管P，再将临时管T0中含有A0B0#的DNA链保留在管P中，丢弃临时管T0。至此，已将所有起止于原点，以双链形式存在的DNA 链为初始数据，并将其保留在管P中，即管P中包含了图G的所有解。

3）筛选经过所有族的解

Step 2筛选出经过所有族的解（2-1）（2-2）（2-3）（2-4）For k=1 to k=h Separation（P，{qk}，T0）；Discard（P）；Copy（T0，P）；Discard（T0）；End

此时有些链不满足约束条件，因此，Step 2 利用For 循环进一步处理：（2-1）和（2-2）表示将的探针放入初始数据池中，与含有qk的双链生成3 链，并将其存储到临时管T0中。与磁珠混合后，得到含有qk的双链DNA，（2-3）—（2-4）则是纯化处理。重复此步骤h次后，可以筛选出未通过所有族的解并剔除。

4）筛选每个族经过2 个点的解

类似地，构造各个顶点vi的探针，并生成3 链。如Step 3 所示是1 个嵌套循环。在内循环中，（3-1）和（3-2）是将管P中生成关于Ai qk Bi三链的双链存储到临时管T0中，如果在该双链中存在2 处三链结构，则表明该族经过了2 个顶点。然后将3 链分离，重新形成双链，（3-3）和（3-4）是纯化处理。重复h步后，最终管P中的所有双链都经过了每个族的2 个顶点。

Step 3筛选出每个族只经过2 个点的解（3-1）For k=1 to k=h For i=1 to i=N Separation（P，{AiqkBi}，T0）；（3-2）（3-3）（3-4）If T0=2 Discard（P）；Copy（T0，P）；Discard（T0）；Else（3-5）Continue；End End

5）筛选经过同一顶点1 次的解

由于顶点可能被多次访问，还需进一步筛选。运用上一步所构造的探针，以每个顶点为单位，将管P中生成关于Ai qk Bi的三链存储到临时管T0中，如果存在2 处三螺旋结构，表明同一顶点经过2次，将临时管T0丢弃；否则，重新形成双链，并进行纯化处理。重复N 次后，可筛除经过同一顶点2 次的解。

6）选出最优解

经过上述步骤，已删除所有不符合约束条件的解，只需在所剩的解中选择最优解。对其进行凝胶电泳，切割下长度最短的双链并测序，即可找到最优解的DNA链：#A0B0w0，1A1q1B1w1，2A2q1B2w2，13A13q3B13w13，7A7q2B7w7，10A10q3B10w10，8A8q2B8w8，0A0B0#，与之对应的最优路线为：0→1→2→13→7→10→8→0。

4.3 复杂度评估

步骤1 和步骤2 分别是编码设计和生成初始数据，而步骤3 到步骤5 则是在逐步筛选可行解，最后是选出最优解。综上所述，以上6 步的总复杂度为：

为了解决FTSP，本文提出了一种简单的编码规则和并行能力较强的三链DNA 计算模型，可在O（Nh）复杂度内找到最优解。三链模型在理论层面已经解决了不少多项式复杂程度的非确定性问题（Non-deterministic Polynomial，NP）问题，随着生物技术的发展和完善，未来可使其成为解决更复杂大数据问题的方法之一，进一步提高模型的有效性和通用性。