dna计算在图论中的应用

《dna计算在图论中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、DNA计算在图论中的应用DNA计算是计算机科学和分子生物学互相结合、互相渗透而产生的新兴交叉研究领域。DNA计算具有高度的并行性、运算速度快、信息贮存容量大等优点。这为解决图论中的一些问题尤其是图论中的NP-完全问题提供了新的途径。首先介绍了DNA计算的基本原理。然后详细介绍了图最小生成树的DNA算法以及哈密顿图的DNA算法。最后介绍了DNA计算在图论应用的领域中存在的一些尚待解决的问题。关键词：DNA计算、图论、最小生成树、哈密顿图1.引言　　自从Adleman博士于1994年开创性地用DNA计算实现了7

2、个顶点的有向图的哈密尔顿问题以来，国际上DNA计算在图论应用的研究领域中，主要集中在对哈密顿图问题、图着色问题和图顶点的最小覆盖问题的求解上。继Adleman之后1998年，Romer等人对骑士周游问题用DNA计算进行了求解[1]。2004年，Zu等人提出了一种求解最短有向路问题的一种DNA算法。2006年，AiliHan和DamingZhu提出了解决旅行者问题的一种新的DNA编码方法[2]。　　电子计算机在解决图与组合优化中的NP-问题是非常的困难，特别是规模特别大时几乎是不可能的。DNA计算机将具有以下

3、几个方面的突出优点:(l)具有高度的并行性，运算速度快。(2)DNA作为信息的载体其贮存的容量非常之大。(3)DNA计算机所消耗能量极小。(4)DNA分子的资源丰富[3]。这些决定了DNA计算在解决非线性复杂问题、NP完全问题时具有其他计算模式所无法比拟的优势。2.DNA计算的基本原理　　DNA计算的本质就是利用大量不同的核酸分子杂交，产生类似于某种数学过程的一种组合的结果，并根据限定条件对其进行筛选的。单链DNA可看作由符号A、C、G、T组成的串,同电子计算机中编码0和1一样,可表示成4字母的集合来译码信

4、息。特定的酶可充当“软件”来完成所需的各种信息处理工作[4]。　　DNA计算的基本思想是：利用DNA分子的双螺旋结构和碱基互补配对的性质,将所要处理的问题编码成特定的DNA分子,在生物酶的作用下,生成各种数据池；然后利用现代分子生物技术如聚合酶链反应、聚合重叠放大技术、超声波降解、分子纯化、电泳、磁珠分离等手段破获运算结果；最后通过测序或其它方法解读计算结果。DNA计算的核心问题是将经过编码后的DNA链作为输入,在试管内或其它载体上经过一定时间完成控制的生物化学反应,以此来完成运算,使得从反应后的产物中能得

5、到全部的解空间。3.DNA计算在图论中的应用3.1最小生成树问题　　文中我们考虑的图是连通赋权简单图。若图是连通的无向图或强连通的有向图，则从图中任意一个顶点出发遍历图中的所有顶点，这个过程中经过的边所构成的子图称为原图的生成树。所以最小生成树可描述为：在连通图G的所有生成树中，代价（生成树各边权值之和）最小的生成树称为最小生成树[5]。最小生成树可简记为MST。　　下面讨论求解最小生成树问题的算法。根据最小支撑树的定义，我们可以将最小支撑树的算法简单概括如下:针对图G，从空树T开始，往集合T中逐条选择权最

6、小的边（始终保持边数=顶点数-1），直到无法再扩展为止。具体步骤如下：　　步骤一:从E中选取一条最小权的边，记为el=[v1，vZ]，E={e1}；记n=2，Vn={vl，vZ}。　　步骤二:如果n=G，则T=(Vn,En-1)是最小支撑树；否则执行步骤3。　　步骤三:从[Vn,V-Vn]中选一条权最小的边([Vn,V-Vn]表示连接顶点Vn，V-Vn的边)记为en-1=[Vn-1,Vn]，Vn+1=Vn∪{vn},En=En-1∪{en-1}，把n换成n+1，转入第2步。　　我们来介绍上面提到的算法所对应

7、的分子操作步骤:　　步骤一:对图的顶点、边以及边的权进行DNA编码：对于图G的任意顶点vi，用长度为20的寡聚核苷片断表示(即它包含20个碱基)，并记为Ni(i=1，2，…，n)。然后利用Ni构造n个探针，并分别记为Q1,Q2,……,Qn。对于图G的边eij由三个部分表示:第一部分是寡聚核着酸片断Ni的碱基的补链所构成的寡聚核苷酸片断；第二部分是寡聚核苷酸片断Nj的碱基的补链所构成的寡聚核苷酸片断。第三部分是长度为[30*ax{ax{1，5，4，4，2，3，6，5，7}=7。因此根据上面的公式，可以得到对应

8、于边权so-bidi-font-al;">，举例。顶点1，2，3的编码如下：N1：TCGGTAATGCTAGCTGGAGAN2:TATAGGCCATGCGATCGGTAN3:CGTTAAGCAGTACGAGTCAG根据编码规则，得到e12，e23的编码为：N12：ATCCATTACGATCGACCTCGATCGATTGCTAGGCCATGACGGATATATATCCGGTACGCTAGCCATN23：ATATCC