组合优化中的DNA计算

组合优化中的DNA计算殷志祥董亚非许进(华中科技大学控制科学与工程系,武汉430074 )E-mail zxyin@mail.hust.edu.cn摘要由于电子计算机的存贮量小运算速度慢智能化低特别是制造工艺趋于极限等特点,因此,目前采用DNA计算的可能性引起了人们的广泛关注尤其是它的良好的并行性。该文在简要介绍DNA计算的实施方法后探讨了DNA计算及其相关的数学模型指出了DNA计算的优点及存在的问题。最后简述了DNA计算与图论、遗传算法、人工神经网络、纳米材料等的联系。关键词图论遗传算法 人工神经网络 纳米科技 计算文章编号1002 -8331-( 2002 )19- -0025- -03文献标识码 A中图分类号 TP301.6DNA Computing in Combination and OptimizationYin Zhixiang Dong Yafei Xu Jin( Department of Control Science and Engineering ,Huazhong University ofScience and Technology ,Wuhan 430074 )Abstract: Due to electronie computer of small storage capacity slow operation speed and low intelligence particularlylimited manufacture technics recently ,the possibility of using DNA as a computing tool arouses abroad interests ofresearchers.Especially it is highly parallel.After a brief introduction on implementation of DNA computing ,this paperdiscusses DNA computing and correlational mathematics models.The paper points out the advantages and existingproblems.Finally it simply introduces the contact between DNA computing and graph theory Genetic algorithm artificialneural networks and Le meter material.Keywords : Graph theory ,Genetic algorithm Artificial neural networks Le meter material ,Computing1引言过交叉互相交换链.上的核苷酸。从DNA的原理来看,它与数学电子计算机在人类社会起到了巨大的促进作用但由于电操作非常类似,单连DNA可看作由四个不同符号A、T、C、G组子计算机的存贮量小运算速度慢智能化低导致人们迫切希成的串。它在数学上就像电子计算机中编码0”和1"一样可望寻找一种能克服上述缺点的新型计算机。1953 年Waston和表示成四字母的集E={A T C G)来译码信息。DNA链可作为Crick发现DNA之后,人们发现许多操作DNA的方法。如酶译码信息酶可看作模拟在DNA链上简单的计算。不同的酶用切、粘、贴、电泳、聚合链反应、加热、退火等。这些操作DNA的于不同的算子,如,限制内切酸酶可作为分离算子,DNA 连结方法有助于人们解决内存及信息的输入和接收。酶可作为联结算子,DNA 聚合酶可作为复制算子,外 切酶可作为删除算子等。2计算的原理DNA计算的研究涉及许多方面,DNA 计算具有通用性、时DNA是重要的基因物质,它携带着生物的遗传信息。DNA空复杂性、有效性及容错性。由于DNA分子计算技术的应用潜的基本元素是核苷酸。由于化学结构的不同核苷酸划分为四力十分巨大,DNA计算机的构想是一种创新 ,它的运算速度极类碱基:腺嘌呤(A )鸟嘌呤(G)胞嘧啶(C )和胸腺嘧啶(T)。快如果两个分子DNA的连接被看作一次运算那么这种基于DNA是由两条极长的单链核苷酸组成,这两条极长的单链核DNA分子的运算每秒钟可大约进行10'5 次或更多次,其运算苷酸利用碱基之间的氢键而结合在一起形成-条双链的螺旋速度超过当前超级计算机1000倍淇次其存贮量巨大,1立结构,且一条单链中的碱基序列与另-条单链中的碱基序列互方米的DNA溶液可存储1万亿位二进制的数据,超过当前所补A和T配对C和G配对。每个染色体是-段双链螺旋的有计算机的存贮量;另外它的高度并行性及极低的能耗(DNADNA.遗传信息以A、T、C、G在核苷酸中的排列顺序而体现其运算反应过程中所消耗的能量只有-台普通的计算机的十亿.排列顺序的多样性构成了丰富的遗传信息细胞利用遗传信息分之一)。Agsymetrix公司制造的生物芯片能正确地诊断出主要有三种复制、转录和翻译。通过DNA的复制而保留遗传BACAI基因中国煤化工博土等的试验室使信息。遗传信息从细胞核传到细胞质,是把DNA转录成mR-用已知的39!YHCNMHGE经制备了-种Ag-NA。tRNA起调节作用将氨基酸插入到多聚氨基酸的合适位gy metrix芯片，开且止在研究更新的心片。其可以携带2000置。重组或交叉是DNA交换遗传信息的过程，两条DNA链通.种位点变异的样本,这类芯片进行遗传病家谱的研究。Aggy基金项目:国家自然科学基金资助(编号:60174047 60103021 )作者简介:殷志祥男副教授博士主要从事图论与DNA计算的研究。计算机工程与应用2002.19 2metrix公司正在尝试将更多的DNA探针放到芯片上,通过压DNA计算与遗传算法的集成遗传算法(GA)用于模拟生缩DNA探针生产出160万DNA探针的芯片。这为DNA计算命的自适应和进化被用于设计好的机器和编制自进化的计算机的产生提供了有力的依据。机程序,由于常规GA用于实际问题,尤其是处理复杂的、混淆的和多任务问题时不够灵活,且计算速度慢,- 些学者提出了3计算与组合优化问题基于DNA机理的改进的GA。如带有双链DNA的GA用于促1994年Adleman首次用试验显示了DNA计算的可能性,进DNA复制的非对换变异21类似DNA编码的系统描述"用介绍了采用DNA进行特定目的计算的可行性"成功地解决了于各种进化系统细胞特定化的模型叫。在细胞特定化的过程中,有向图的Hamilton 路径问题。先将图中各个顶点口;用一个任每个细胞具有相同的DNA,硬件建模和计算机仿真显示了细意的20个碱基单链DNA片断来代替D0; 弧分别用0;顶点的胞特定化具有自组织特性。另外还提出了基于生物学DNA编后10个碱基的互补碱基和n;的前10个碱基的互补碱基构成码方法的GA.这种方法具有DNA染色体中的重复性和基因表的DNA片断来代替。然后将足量的上述DNA片断放入溶液达的重叠性并使交叉和变异操作变得容易。模糊系统在许多中通过连接反应随机生成若干条有向路径。再利用引物通过领域中已获得成功应用,但对于复杂的多输入多输出模糊系统PCR技术对上一步的产物进行扩增就可以有选择地扩增那些目前仍缺乏有效的设计方法。虽然常规GA能用于获取模糊控自起点到终点的链。接下来利用琼脂糖凝胶电泳得到的140制规则,但有时难以胜任复杂系统,如多输入多输出模糊系统碱基对的谱带就是恰恰经过7个顶点的路径的DNA链。割下的优化工作。故一些作者提出了基于DNA编码机理的GA并这条带浸入双蒸水中提取DNA(凝胶分离)PCR扩增及凝胶用于多变量模糊系统的优化。它能用于模糊系统的输入变量的分离多次重复可有效提高纯度。然后利用探针挑选出只经过选择和映射函数参数的调整,从而自动获取模糊控制规则。并每个顶点一次的DNA链最后用凝胶电泳检测它的存在性。且病毒和酶操作也用于这种DNA编码方法。机器人运动控制1995年Lipton在Adleman的试验基础上,解决了更有趣的研究中初步显示了这种方法的可行性。集成生物的神经组织的NP完备问题(可满足问题尸。首先利用DNA链表示问题的.的生成和功能受DNA遗传信息作用故DNA遗传信息可用于所有可能解然后利用生物反应删除无效解,从而表明了DNA神经网络的建模和优化。-种采用DNA序列译码的框架被用计算能起到高效搜寻机制的作用。对于计算机科学与数学在于建立神经网络(NN)模型。这种神经网络模型与采用常用寻找适当的问题和有效分子算法去解决更为复杂的系统模型CODE-4译码框架的神经网络相比能更好地预测分开DNA序的计算问题。Adleman和Lipton分别解决了有向图的Hamilton列的topoisomerase可能性,且该网络大小是后者的1/4 ,因而路径问题和求解SAT问题。T.Head等解决了最大独立集问题叭。该神经网络模型的参数数目减少了近75%。纳米技术为DNA而且以上所述问题都是用DNA计算来完成的。不仅如此用提供了可行性和理论依据,它使得人们能在极小的芯片上集成DNA计算还能解决最小覆盖问题图着色问题图的可平面性大量的DNA探针,从而可以利用DNA芯片进行复杂的计算和问题,图同构问题,Ramsey 问题等等著名的NP问题和一些待大量的信息存储,纳米芯片的提出及进展将直接推动DNA计解决问题。Qinhua Liu 等成功地解决了SAT问题4这象征着算机的研制和产生。DNA计算向DNA计算机迈进了更大一步。Beave 提出了如何建立和操作含单个DNA分子的图灵机凹Smith和Scheweitzer表5DNA的优点及目前存在的问题明DNA分子和标准实验室技术可用于建立一个非确定性图灵DNA计算的优点主要在于DNA具有高度的并行性,目 前机问,Winfree描述了一种基于自装配单链核酸链网络的空间图最快的巨型机每秒能执行102个操作。而DNA计算机的重要灵机”。另外连结方法也被用于模拟图灵机。Daum 显示了使特点在于它的巨大并行处理。在LAdleman的初始实验中通用DNA和分子生物学工具能达到编码1020 个字的联想记过适当估计,DNA链的并行操作数目可达104。 虽然DNA计算忆%。RooB和Wagner则表明,若没有时间限制Lipton模型能.的每个操作本身与电子实现相比很慢,但DNA反应的巨大并处理任何计算问题[叫,Yinetal给出了中国邮递员问题的DNA行性足以满足当前巨型机或更强的计算挑战,其次DNA计算计算模型这些证明显示了存在DNA计算机的许多可能结构。有很高的能量效率和存贮容量,电子计算机操作过程效率非常同时科学家正在利用遗传DNA研制-种全新概念的计算机。低,巨型机执行10° 个操作需要1焦耳能量,而用于实现DNA他们认为这种计算机的运算速度和信息存储量大大超过目前计算操作的酶是在进化中产生的具有很高的能量效率,1焦的计算机。科学家们指出DNA含有大量的遗传密码他通过生耳的能量足以执行2x109个操作,DNA分子允许非常高的信息化反应传递遗传信息。DNA分子中的密码相当于存储的数据存贮密度:1 位/nm3 ,而当前录像带的信息存贮密度仅为1位/DNA分子之间可以在某种酶的作用下瞬间完成生物化学反.12nm2。计算目前还存在许多问题尽管DNA计算的研究已取应,从一种基因代码变为另-种基因代码。反应前的基因代码得一些进展,但DNA计算还有许多实际和理论问题有待解决。可以看作输入的数据,反应后的基因代码可看作运算的结果,首先在DNA计算实验中如何选择实际操作参数的数目、个体如果控制得当那么就可以利用这种过程制作-种新型的计算的操作速度、个体操作和序列操作的可靠性、信息载体的稳定机。科学家们认为这种新型的计算机将在5年内取得实质性的进展。从实际角度来看,自然科学的两个前沿领域分子生物学电子计算机中国煤化工技术及纳米技术的进和计算机科学的有机结合,一定会创造出惊人的遗传奇迹。-步发展等。|YCNMHGDNA计算机- :旦产生诸多NP问题和待解决问题都将可以直接进行计算R(55和R(66就有可能在几分钟内解决。参考文献1.AdlemanLM.MolecularComputationoSolutionstoCombinatorialProblems[J]4计算与其它模型.Science ,1994 266( 5187 ):1021-102326 2002.19 计算机工程与 应用2.Lipton R J.DNA Solution of Hard Computation Problem[J.Sience ,1995 ( 268 ) 583~5859.Baum E B.Building an Associative Memory Vastly Larger than the3.T head et al.Computing with DNA by operating on plasmids[].Bio-Brain[J.Science ,1995 ( 268 ) 583~585Systems 2000 (57 )87-9310.Roo β D ,Wagner K W.On the Power of DNA-Computing[J.Infor-4.Qinhua liu et al.DNA computing on surfaces[J].Nature ,2000 ;403 :mation and Computation 1996 ;131( 2) 95~109175-17911.Zhixiang Yin ,Fengyue Zhang Jin Xu.A Chinese Postman Problem5.Beave D.Computing with DNA[J].Journal of Computational Biology ,Based on DNA Computing[J]Journal of Chemical Infomation and Con-1995 2(1 ):1~8puter Sciences 2002 ;42( 2)222~2246.Smith w Schweitzer A.DNA Computers in Vivo[C].In :DIMACS Work-12.DoiH ,FurusawaM Evolutionis Promotedby Asymmetrial Mutationsinshop on DNA Bead Computing Princeton ,1995DNA Replication-Genetic Algorithmwith Double- -Stranded DNAJ.Fu-7.Winfree EOn the Computational Power of DNA Annealing and Li-jitsu Scientificand Technical Journal ,1996 3x 2 ) 248~255gation[C.In E B Baumand R J Lipton editors DNA based Computers ,13.NakanoKetal.ASelf-OrganizingSystemwithell-Specialization[C].In Pro-American Mathematical Society ,1996ceedings of 1997 IEEE Intermational Conference on Evolutionary Com-8.Rothemund P A.DNA and Restriction Enyme Implementation of Tur-putation ,Indianapolis IN USA ,1997-04 279~284ing Machine[C].In E B Baumand R J Lipton editors DNA based Com-(上接18页)制导致网络拥塞增加和数据传输效率的降低,从而引起端到端到端平均时延指源节点有数据发送至接收节点收到数端平均时延的增加。flooding协议在低带宽MPRN上会产生严据之间的时间,包括建立路由时间和数据转发时间。重的网络拥塞，因而大大增加了端到端平均时延。嘎2 分组递交成功率(%度化情况移动速度多 播组成员节点数5结束语(km/h) 5 10 20 30flooding该文提出了应用于移动分组无线网的多播路由算法及其87.5 73.0 63.0 65.0 72.8实现方法。考虑到节点的移动性和无线通信带宽的限制采用2091.2 74.5 69.0 66.2 72.7了按需路由发现策略减小控制开销提高算法的执行效率,使4091.275.0 66.0 67.0 72.0之能够适应具有较低带宽的大规模动态网络环境。从模拟实验500.0 75.0 66.0 67.2 72.58090.0 75.0 68.0 67.5_ 71.3结果来看,在网络带宽有限和网络拓扑结构变化的条件下具表2列出了在不同多播组成员个数的情况下,分组递交成有稳定的分组转发成功率和良好的伸缩性获得了较好的多播功率随着节点移动速度变化而变化的情况。在表中可以看出。数据传输质量。同时还需要进-步分析网络和算法的各个参数当多播组成员较少时,分组转发成功率在87.5%以上。随着多对路由性能的影响，实现各个参数的合理配置,以进一步提高播组成员数量的增加,虽然建立的转发组网格会产生更多的数路由效率和可靠性。(收稿日期:2002年6月)据传输冗余链路,有助于提高分组传输的可靠性。但由于网络带宽的限制及拥塞的增加，使得分组转发成功率有所下降最参考文献后稳定在60%至70%间。flooding协议的分组递交成功率在1.Deering s E ,Cheriton D R.Multicast routing in datagram internet-72%左右。另外,节点移动速度的变化对分组递交成功率的影works and extended lans [J].ACM Transactions on Computer Systems ,1990 &(2 )85~110响较小。2.Moy JMulticast Routing Extensions for OSPF [J].Communications of表3端到端平均时 延( ms变化情况the ACM ,1994 37(8)61-66移动速度多播组成员节点数3.Deering S ,Estrin D L ,Farinacci D et al.The PIM architecture for(km/h)_5_1020二30- foodingwide-area multicast routingJ]IEEE/ACM Transactions on Networking ,78 81 140.0 1351996 ;( 2):153-1626566.7 126.5 160.0 154.04.Lee Sung- Ju Su W lliamn ,Gerla Mario.On- Demand mulicast routing70 77.2 935 168.0 200.0protocol( ODMRP )Yor ad hoc networks.IETF Intemet Draft [EB/OL].60 71.2 125.4 113.7 207.265 66.9 104.7 181.2 225.5http /ww..t.org/internet drafs/ratft-itf- manet -dmrp- -02.txt 2000-端到端平均时延包括路由请求时间和数据传输时延。路由7-12/2001-12-14请求时间主要用于路由信息的产生和刷新上,由于需要泛洪请5.Johnson David B ,Maltz Davis A.The dynamic source routing protocolfor mobile ad hoe networks IETF Internet Draft EB/OL.htp ://www.求分组来建立路由路由请求时间受组成员数量、网络拓扑结ietf.org/ internet- -drafts/ draft- ietf- -manet- -dsr- _03.txt ,1999-10- -8/2001-构的变化和节点移动速度的影响较小路由请求时间-般保持12-14在34至35ms之间。数据传输时延由于受到拓扑结构变化和6.Ucla compu中国煤化工mputing laboratory and传输带宽的限制,变化较大。从表3中可以看出随着多播组成wireless ac:A scalable simulationC NMHG员节点数量的增加端到端平均时延从67.6ms(5个组节点)增environment:YHIstems [EB/0L.http ://加到151.4ms(30个组节点)，这是由于受到无线信道带宽的限pel.cs.ucla.edu/ projects/domains/glomosim.html 2000 -9- 12/2001-12-14计算机工程与应用2002.19 27