【2019年整理】DNA算法在Hamilton路径中的应用.doc

摘要DNA计算是生物计算中最受关注的一种计算,目前的DNA计算领域始于1994年Adleman先生的著名实验。DNA算法解决计算问题的基本思想是:以DNA碱基序列作为信息编码的载体,利用现代分予生物学技术,在试管内控制酶的作用下进行DNA的序列反应,Watson-Crick互补序列反应作为实现运算的过程。本文通过DNA计算寻找Hamilton路径存在从而判定Hamilton路径是否存在。该算法的创新之处在于通过一种新的计算方法解决图论中的一些NP完全问题。关键词:DNA算法Adleman实验Hamilton路径引言随着计算机科学与数学的发展,图论已经应用到了各个领域,其中包括物理学、化学、通讯科学、计算机技术、生物遗传学等等。图论为任何一个包含二元关系的系统提供了一个数学模型;利用图直观、。如互联网、交通网、通讯网、集成电路、分子结构等都可用图来描述。图论已经成为人们研究自然科学及社会科学的一个重要工具。其中Hamilton图及相关领域,其应用己越来越重要。Hamiton路径问题众所周知,图的Hamiton路径问题一直是图论中的一个十分重要且十分活跃的研究课题。十九世纪中期爱尔兰的皇家天文学家哈密顿(WilliamRowanHamilton)提出,在一个有多个城市的地图网络中,寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。通常所说的Hamiton路径问题是设G是一个有向图,V1,V2是G的两个顶点,如果存在一条从V1出发到达V2,且经过G中其它每个顶点一次且只有一次的有向路P,则称P是G中从V1到V2的一条有向Hamilton路。寻找一个给定有向图的有向Hamilton路问题是所谓的有向Hamilton路问题,简记为HPP问题。,以传统的图灵机(Turing-Machine)为原型的现代电子计算机很难从真正意义上实现并行算。于是人们将目光投向了其它领域,以求获得完全不同的计算方式和计算理念。1994年Adleman的实验,标志DNA计算领域的开始。DNA算法解决计算问题的基本思想是:以DNA碱基序列作为信息编码的载体,利用现代分予生物学技术,在试管内控制酶的作用下进行DNA的序列反应,Watson-Crick互补序列反应作为实现运算的过程。以反应前的DNA序列作为输入的数据,反应后的DNA序列作为运算的结果。DNA计算的操作方法一般有抽取、切割、溶解、退火、合成、杂交、扩增PCR、检测、分离、电泳、磁珠分离、连接和合并等一系类操作。DNA(脱氧核糖核酸)是所有生物主要的遗传物质,它是一种高分子化合物,组成它的基本单位是脱氧核苷酸。每个脱氧核苷酸是由一分子磷酸、,腺嘌呤(A)、鸟嘌呤(G)、胞嘧啶(C)和胸腺嘧啶(T)。DNA分子不仅具有一定的化学成分,还具有规则的双螺旋结构。结构的主要特点是:(1)DNA分子是由两条平行的脱氧核苷酸长链盘旋而成;(2)DNA份子中的脱氧核糖和磷酸交替连接,排列在外侧;(3)DNA两条链上的碱基通过氢连接起来,形成碱基对。碱基对的组成有一定的规律,这就是嘌呤与嘧啶配对。A和T配对,C和G配对。这就是著名的碱基互补配对原则。组成DNA的碱基虽然只有四种,而且这四种碱基的配对方式只有两种,但由于碱基对具有多种不同的排列顺序,因而就构成了DNA分子的多样性。图1简单的描述了DNA分子的双螺旋结构。图1:,取一个只有四个顶点的图,图2如下所示图2简单模型图现在我们的问题就是找到这个网络中,从北京到上海的Hamilton径。当然这个问题的答案很简单,实际路线显然是北京→成都→南京→上海。不过我们的真正问题在于怎样用DNA分子计算来得到这个结果。无论如何,对于DNA分子来说,其所有的信息都用碱基顺序来表示的。而两条DNA链如果其上的碱基顺序可以互补配对的话,那它们就会形成局部的或者整条链的双链结构,这就是著名的DNA双螺旋。配对规则A—T;T—A;G—C;C—G。(注意DNA链是具有方向性的,互补配对的双链方向相反)。编码:每个节点:随机生成一个8个核苷酸的字母链,并且保证每一个节点的编码是唯一的和可识别的。代表各个城市的碱基顺序以及它们的互补链上的碱基顺序。北京:5'-AGGCTTGA-3' 3'-TCCGAACT-5'成都:5'-TACA-3' 3'-CTGGATGT-5'南京:5'-CCGAAATT-3' 3'-GGCTTTAA-5'上海:5'-TTAGCGAT-3' 3'-AATCGCTA-5'上面的碱基顺