论文研究-哈密顿路径问题的一种基于有穷自动机的DNA算法.pdf-其它代码类资源-CSDN下载

论文研究-哈密顿路径问题的一种基于有穷自动机的DNA算法.pdf

所需积分/C币：10 2019-09-08 15:02:48 854KB .PDF
2

收藏
举报

提出了一种基于有穷自动机的解决哈密顿路径问题的DNA算法,将有穷自动机的状态用含有DNA限制性内切酶的识别位点的DNA双链分子来编码,通过限制性内切酶的生物化学反应来实现状态的转移。算法的创新之处在于用DNA计算模拟有穷自动机的运行过程中,保留了其经过的各个状态,以便最后筛选出经过各个顶点的路径。算法的优点是实验实现简易,大大减少所使用的DNA分子的数量。
杨学庆,柳重堪:哈密顿路径问题的一种基于有穷自动机的DNA算法 2007,43(18)89 每一个编码状态的DNA分子的L与R的组成均相同,只的DNA算法陆续被提出来,这些算法的实质都是穷举算法,本是黑色的部份不同,如状态0就可以用图6所示的双链DNA质都是先用DNA分子建立一个数据库,再从该数据库中筛选分子来编码,而状态1则可以用图7所示的双链DNA分子来出满足给定条件的数据。因此,所需的DNA分子的数量都非常编码,状态转移则是由两个状态分子按以下规则连接而成的一庞大。例如 Adleman解决哈密顿路径问题的算法第一步是形成条DNA分了来编码:其前半部分是编码当前状态的DNA分所有的路径,假设该哈密顿路径问题由n顶点组成,那么这些子,而后半部分则是编码下一个状态的DNA分子,例如从状态路径不仅包括经过n个顶点的路径,还包括经过m(1≤m≤n) 0转移到状态1的状态转移分子则由图8所示的DNA分子来个顶点的路径,并且这些路径的起始点与终点也是各种各样,而编码。记所有从起始状态开始的状态转移规则的集合为P,在本文所使用的基于有穷自动机的算法,只形成所有从起始顶点本例中P由0-1,0-6,0-2组成,记所有到达接受状态的状态出发,到达终止顶点,且经过n个顶点的路径,因此能极大地减转移规则的集合为F,在本例中F由5-6,0-6组成,记所有的少了DNA分子的数量。从本质上讲,就是用本文的方法建立的状态转移规则为A,A-F→P表示在A中减去F与P后所有其数据库所含数据的个数远远小于 adleman建立的数据库的数它的状态转移规则。将所有的A用相应的限制性内切酶处理量。但由于本文用到了有穷自动机,又容易使人产生误解,认为 (能切割第一个状态的限制性内切酶处理,如所有的P都用用有穷自动机这样计算能力有限的机器就能解决非常复杂的 Eco限制性内切酶处理)。以下反应中所使用的编码A的双链NP问题。其实本文的方法是将哈密顿路径问题分解成两个子问 DNA分子都是经过相应的限制性内切酶处理过的。题,第一个子问题是判断所给的图中是否存在从起始点出发、经个A人过n个顶点并且结束于指定的终止点的路径,该问题能用有穷自动机解决;第二个子问题是判断该路径是否经过每个顶点图6编码状态0的DNA分子 (即每个状态),因为第一个子问题中的有穷自动机所经过的各个状态都保留下来,所以该问题只需通过亲和层析就能解决 GTAC CA丁C 6结论图7编码状态1的DNA分子夲文提出了一种基于有穷自动机的哈密顿路径问题的 DNA算法,对任给的哈密顿路径问题,先将它用有向图表示, CiAATTCGGTACC R 然后将此有向图转化成有穷自动机的状态图。用DNA计算模 [1+AtTIC 拟此有穷自动机的运行时,用含限制性内切酶的识别位点的双图8编码状态转移-1的DNA分子链DNA分子编码其状态,通过酶解反应实现其状态转移。本文所提出的算法的优点是能极大地减少DNA分子的数量,而创 52实验步骤新之处在于用DNA计算模拟有穷自动机时,将有穷自动机所 (1)将编码起始状态的DNA分子吸附在磁珠上,在本例经过的各个状态都保留了下来。本文所使用的生物学实验都是中,即将图6所示的DNA分子吸附在磁珠上,这可让有穷自动非常通用的实验手段,所使用的试剂也是分子生物学实验常用机处于起始状态, 的,如限制性内切酶早已商业化,无需从细菌中提取,直接就能 2)用Eco限制性内切酶处理,这时发生酶切反应,双链购买到,因此本文的DNA算法是切实可行的。 DNA分子被切割,形成粘性末端,加入所有编码P的双链DNA(收稿日期:2006年8月) 分子与连接酶,DNA连接酶能将两段同源DNA分子连接成个DNA分子。这两个反应完成后,自动机的状态就发生了转参加文献: 移,从当前状态进入了下一个状态。在本例中,进入到3个不同 [1 Adleman L Molecular computation of solutions to combinatorial 状态,即状态1、6、2。加入核酸外切酶来分解未参加反应的起始 Problems[ J, Science,1994,266(9:1021-1024. 状态分子以及状态转移分子;接着将核酸外切酶分离出去。加入2 Garzon M, Rose j a,CaoY, et aldna implementation of finitestate 相应的Eco甲基化酶进行甲基化,图5所示的DNA分子被甲基 machine C/Genetic Programming 1997: Proceedings of the Secone 化,使其不再被Eco限制性内切酶切割。这可让有穷自动机从 Annual Conference, Stanford University, July 13-16, 1997: 472-478 起始状态开始,经过一个状态的转移,进入到下一个状态 3 Gao Y, Garzon M, Murphy R C, et al. DNA implementation of (3)加入相应的限制性内切酶处理,接着加入所有编码A nondeterminism[Cy/Rubin H, Wood D H. Proceedings of the Third F-P的双链DNA分子与连接酶。然后加入核酸外切酶来分解 DIMACS Workshopon DNA Based Computers, Providence, RI, 1997 未参加反应的状态分子以及状态转移分子。将完成反应的核酸 137-148 外切酶分离出去。加入相应的甲基化酶进行甲基化。这可让有14 Benenson,Pax- izu, , Rutka,ta. rogrammable and au 穷自动机经过一次状态转移。这时有穷自动机经过3个顶点。 tonomous computing machine made of biomolecules [J]. Nature, 4)重复步骤(3)n-2次。这可让有穷自动次经过n-2次状 2001,1414(11):430-434 5]Wilhelm P, Rothemund K A DNA and restriction enzyme imple- 态转移,而有穷自动机总共经过n-1个顶点。 mentation of turing machines[C]//Baumand E, Lipton J DIMACS 5)加入相应的限制性内切酶进行处理,接着加人所有编 Seriesin Discrete Mathematics and Theoretical Computer Science 码F的双链DNA分子与连接酶。这时有穷自动机经过n个顶 Princeton: American Science Society, 1996: 128-130 点,这样就完成了算法的第(1)步 16 Sipser M. Introduction to the theory of computation [M-S.1. ]: Pws (6)应用亲和纯化法,用磁珠标记的各状态分子与回收产 Publishing Company, 1997 物(经变性为单链)结合,这样就完成了算法的第(2)步。 [7 Sambrook J, Frtisch E F, Maniatis T Molecular cloning a laboratory 自美国科学家 Adleman创建DNA计算后,许多NP问题 manual[M].2nd ed.[S.L. ] Cold Spring Harbor Laboratory Press, 1989

...展开详情

论文研究

试读 3P 论文研究-哈密顿路径问题的一种基于有穷自动机的DNA算法.pdf