运用DNA计算解决最短路径问题

张喆

摘要摘要：用通俗易懂的语言解释了最短路概念以及解决多顶点最短路问题面临的困境，介绍了DNA计算的研究背景，阐明了DNA计算解决最短路的优势以及算法步骤，并对DNA计算的未来发展作出展望。

关键词关键词：最短路；DNA计算；单链；k-臂分子

DOIDOI：10.11907/rjdk.1431049

中图分类号：TP301

文献标识码：A文章编号文章编号：16727800（2015）004003902

1最短路概念及其传统解法

求解最短路的过程即寻求一个图中任意两节点之间最短距离的过程。以某人从第1个城市到第5个城市为例，中间有2、3、4三个城市，需要寻找到第5个城市的最短路径。最短路的求法一般有两种：确定性算法和启发式算法。确定性算法的含义是，将这些城市看成不同的点，并对点与点之间的距离进行赋值。若想找到点V1到V5的最短距离，可以开始从V1开始搜索。比如d1=d{V1，V2}=5，d2=d{V1，V3}=2。V1到V4、V5不存在交通方式（当然这在如今社会几乎是不可能的），认为距离为正无穷大，自然优选d2。此时临时可行解的集合里囊括了V1、V3个点。再进行搜索，此时的搜索要对V1、V3连接的所有边进行搜索。比如d1=d{V1，V2}=5，d3={V2，V3}=1，d4={V2，V4}=5，d5={V2，V5}=5。此时，优先选择d3，即将V2囊入集合中。此时最短路的一部分已经浮出水面，即d2+d3。重复上述过程，直到找出V1到V5的最短距离。可以看出，当点足够多时，这种算法的步骤将呈现指数爆炸的倾向，实际操作的可能性不大。若采用启发式算法，通过迭代可以大大减少计算量，但往往只能得到局部最优解，如图1所示。

例如目标要找到最低点A4，当经过一系列迭代后，寻找到了A2，但从A2再进行搜索时，会发现它周围的点都高于它本身，于是搜索会在此时停止，而真正的最优解A5却被排除在外，只得到了局部最优解A2。虽然模拟退火法会让这种现象大大减少，但启发式算法陷入局部最优解的概率仍然存在。

基于以上原因，寻求一种新的方法解决最短路径问题则显得格外重要。近年来，国内外学者通过研究和实验发现运用DNA自组装方法解决此类问题非常有效。

2DNA计算算法步骤

1994年，Adleman提出了用DNA分子解决7节点的Hamilton路径问题，这是有关DNA计算的开山之作。之后Lipton在Adleman的思想启发下，通过构造一个接触网络图G，将可满足性问题（SAT）的解空间映射成通过接触网络G的始点到终点的所有Hamilton路径，然后对有向图中的顶点和边进行编码，用DNA计算解决了3-变量的可满足性问题；1997年，Ouyang等[1]提出了用DNA计算求解最大环问题的方法，为DNA计算解决NP问题提供了又一佐证；2000年，Faulhammer等[2]提出了用RNA分子取代DNA分子进行计算，求解骑士问题；同年，liu等人[3]提出了在固体表面进行DNA计算的方法，改变了过去在试管溶液中进行DNA计算的生物操作方法，进一步提高了DNA计算的可靠性和效率。随着该技术的进一步发展，2009年，国内的许进等人[4]设计了闭环求解最大团问题的算法；2010年，周康等人设计了基于粘贴模型的最大团问题算法，Brun采用自组装DNA计算给出了路径寻找问题以及可满足性问题的自组装计算模型的解决方案；2011年，杨静等人[5]将Aunp自组装聚合色变与DNA计算相结合，构建了系列基本逻辑计算模型；2012年，李肯力等人[6]设计出了结合DAE块的DNA自组装模型求解最大团问题的算法，并在2013年进一步改进，等等。

DNA计算具有高度并行性，即给予一定数量的试管，相应实验可以在这些试管里同时进行，从而大大减少了计算时间。不仅如此，DNA本身的碱基配对原则使最优解的选择变得很简单，即不需要去“计算”最优解，只需要看到底哪条子链和对应的子链配对成功即可，这种效率是其它计算远不能比拟的。因此，运用k-臂分子解决最短路径问题具有极大的优势。具体操作过程如下：

（1）将所要研究的问题简化，即将具体事物转化为点，事物与事物之间存在联系则表示点与点之间有边相连，否则无边。根据事物与事物之间的“距离”关系，对边进行赋值。

（2）设计DNA链。设计的DNA满足以下几个原则：一个点有几个边相连，则设计成几臂分子；赋值越大，则设计的DNA链越长（可以对权值进行单位化，便于计算）；所有的DNA链都设计为单链形式，方便配对；根据碱基配对原则，同时设计出各个边对应的子链；对顶点和终点设计探针，以便最后用探针处理结果。设计的4-臂分子如图2所示。

（3）复制相同的试管T，在试管中投放根据图2设计的DNA-k臂分子链，通过杂交技术，让单链与其对应的单链配对，再通过退火的方式，让试管冷却，即将单链与单

链分离。因为之前已经在顶点和终点插入了探针，所以运用探针照明技术即可找出同时含有V1、V5的子链。最后利用凝胶电泳筛选出长度最短的子链，再利用探针照明分析出顶点构成即可（此时的探针和之前的探针有所不同，可以对各个点赋予不同颜色）。

3前景展望

在解决最短路问题中，DNA的合成与编码，以及如何运用尽量简单的方式形成解空间是待解决的重要问题，同时如何剔除“伪解”和“错解”，筛选出最优解也非常重要。对于模型的顶点、边以及顶点和边的映射关系等进行DNA编码与合成，并在试管中形成解空间，进行合并、分离、设置、清除等生物操作，最后对筛选出的解进行检测，并转换成问题的实用解。本文用k—臂分子建立了解决最短路问题的模型，具有一定可行性，但是时间操作仍需不断改进。DNA计算的应用范围极其广泛，只要解决了以上问题，DNA计算在未来很多领域都将占据一席之地。

参考文献参考文献：

[1]张成，杨静，许进，等.缩短法计算模型求解最大独立集问题[J].科学通报，2009，54（24）：3913.

[2]张社民，方刚.连通度问题的三维DNA结构进化算法[J].计算机工程与应用，2007，43（7）：41.

[3]高琳，许进，张军英.DNA计算的研究进展与展望[J].电子学报，2001，29（7）：973977.

[4]姜泊，张亚历，周殿元.分子生物学常用实验方法[M].北京：人民军医出版社，2000.

[5]周康，刘朔.基于粘贴模型的最大团问题算法[J].华中科技大学学报：自然科学版，2010，38（9）：8992.

[6]黄布毅.DNA计算中若干理论问题的研究[D].武汉：华中科技大学，2005.

责任编辑（责任编辑：黄健）