用DNA计算图的哈密顿路径

正如一些评论中推测的那样,该算法是在试管上而不是硅上进行的。

Input: for each node v and edge (u; v),
  Tv contains Sv (and Sv)
  T0uv contains Suv (and Suv)

因此,我们为图中的每个节点初始化一个试管,其中包含代表该节点的DNA片段,并为图中的每个边初始化一个试管。代表节点的DNA序列是随机生成的。我们不想让他们彼此接触。代表边缘的DNA序列被设计成与它们连接的节点重叠。也就是说,如果节点与边缘相连,那么节点的DNA会粘附在边缘的DNA上(这是使整个技术发挥作用的关键点)。DNA序列需要被放大(两者都要有足够的DNA,这样DNA的浓度就与相同两个节点之间的边数成正比)。

Mix(fTi; T0 uvg,T)
Remove(T,T0,fSfg)
Remove(T0,T0,fStg)

我们把所有的DNA序列放在一个试管里,然后运行 Polymerase Chain Reaction. 在PCR中,我们使用表示哈密顿路径起始和结束节点的引物。 结果将是以起始节点序列开始的DNA串,然后沿着节点边缘移动,直到到达结束节点。

Move length 20n+10 strings from T0 to T00
if Detect(T0')
then return ``Yes''
else return ``No''

那么我们 run the DNA on a gel ,并挑选出正确长度的DNA序列。这应该是一条哈密顿路径。有一件事我还不完全清楚,他们是如何防止重复访问顶点,但我认为这是自然的,有正确的浓度,如上所述。