Question

我最近发现“DNA电子计算”Algorithm(不是基因规划或遗传算法),试图在图表中找到汉密尔顿的路径,但I m 略为混淆不清。可查阅PDF关于DNA计算的文件:

Input: for each node v and edge (u; v),
  Tv contains Sv (and Sv)
  T0uv contains Suv (and Suv)
Mix(fTi; T0 uvg,T)
Remove(T,T0,fSfg)
Remove(T0,T0,fStg)
Move length 20n+10 strings from T0 to T00
if Detect(T0 )
then return ``Yes  
else return ``No

http://people.ibest.uidaho.edu/~foster/Talks/dna-computing.pdf”rel=“nofollow noreferer” 。有些人能否将其翻译成betterpseudo 代码? 我想尝试这一算法,但我拿不出他们与混合——和;驱逐——和特;然后移走Move(20n+10)。

P.S.这一算法是O(n^2),因此,怀疑它可能是一种类似于现有算法的版本。

Answer 1

在一些评论中,计算法意在测试管而不是硅。

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

因此,我们先对图表中的每一分点进行测试,包括显示该分点的DNA碎片,并对图表中的每一对口进行测试。代表 no子的DNA序列随机生成。我们不希望他们能够相互做饭。代表边缘的脱氧核糖核酸序列的设计使其与它们连接的底线相重叠。哪一种意思是,如果与edge有关系的话,那么脱氧核糖核酸将贴上edge。 (这是使整个技术发挥作用的关键要点)。脱氧核糖核酸的顺序需要扩大(既要有足够的脱氧核糖核酸,又要使脱氧核糖核酸的浓度与同一两端的对口数量成正比)。

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

Here we put all of the DNA sequences in a tube, and run the Polymerase Chain Reaction. In the PCR, we use primers which represent the start and end nodes for our Hamiltonian path. The result will be strings of DNA which begin with the Start node sequence, and then go edge-node-edge until the finish node is reached.

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

然后,在“gel上将DNA引入,并用适当的长度摘取DNA序列。这应当是汉密尔顿的道路。对我来说,一个完全不明确的是,它们如何防止对vert子的重复访问,但认为这自然是出于上述正确浓度的原因。

令人感兴趣的理由是,化学基本上同时进行这些计算。所有可能的道路都经过检查——因为所有DNA碎块的相容组合都是制造的——但PCR和gel只选择了代表汉密尔顿之路的道路。而且,这是你在计算机上可以做的,没有时间。

友情链接