计算机时代2011年第2期
·1·
DNA计算中的数据与计算模型*
朱雅莉,徐雨明,蒋瀚洋
(衡阳师范学院计算机科学系,湖南衡阳421008)
摘
要:对DNA计算的通用性及单链、双链、粘性末端、发夹、质粒、k-臂DNA分子等各种数据作了简单介绍,并对基于
DNA分子结构特性和基于DNA计算机研制过程两个方面的DNA计算模型进行了分析对比。针对各种不同的DNA数据及特性,提出了混合DNA计算模型的研究思路,并从不同角度论述了混合DNA计算模型的可行性。关键词:DNA计算;DNA数据;混合DNA计算模型;DNA芯片
DataandComputingModelinDNAComputing
ZHUYa-li,XUYu-ming,JIANGHan-yang
(Dept.ofComputerScience,HengyangNormalUniversity,Hengyang,Hunan421008,China)
Abstract:Theversatilityandvariousdata,suchassingle-stranded,double-stranded,sticky-end,hairpin,plasmidandk-armDNAmolecules,ofDNAcomputingarebrieflyintroduced.Furthermore,theDNAcomputingmodelsbasedonthecharacteristicsofDNAmolecularstructureanddevelopmentprocessofDNAcomputerareanalyzedandcomparedrespectively.FordifferentdataandcharacteristicsofDNA,weputforwardtheresearchideaofmixedDNAcomputingmodelanddiscussthefeasibilityofitfromdifferentangles.
Keywords:DNAcomputing;DNAdata;mixedDNAcomputingmodel;DNAchip
0引言
电子计算机科学被认为是二十世纪三大科学革命之一,它对人类社会发展起到了巨大的促进作用。但随着科技进步和社会发展,目前电子计算机的运算速度和存储容量都不能满足日益增长的高性能计算需求,同时,电子计算机在制造工艺上受到0.08μm的客观限制,这些迫使研究者们展开新型信息处理模式的研究。其中,DNA计算因其具有高度的并行性、海量存储容量、低能量消耗以及丰富的DNA分子资源等优点,迅速成为发展非传统高性能计算的重要途径之一,备受研究者们的关注,自Adleman提出DNA计算以来,DNA计算迅速成为研究的热点。
Schweitzer提出利用DNA分子和标准实验室技术可用于建立一个非确定性图灵机;Winfree给出了一种基于自装配单股核酸链网络的空间图灵机;Rooβ和Wagner则表明若没有时间限制,Lipton模型能处理任何计算问题。这些证明显示了DNA计算机存在许多可能结构。
2DNA计算中的数据
2.1单链DNA分子
单链DNA分子实际上就是DNA分子的一级结构,即不同的核苷酸之间通过磷酸二酯键连接成一个核苷酸序列。它是有方向的,一般用5'→3'或3'→5'来表示不同方向。在DNA计算中,已有不少学者利用单链DNA分子作为信息处理的数据。如:Adleman在求解7结点哈密顿问题(HPP)时,就是利用单链DNA分子来表示图的顶点,而图的边则以边相邻的两个顶点的各一半序列构成,并通过边的补链为模板进行杂交反应来获得所需要的有向路径。2.2双链DNA分子
双链DNA分子是DNA分子的二级结构。其实,对于DNA计算而言,双链与单链编码没有本质性区别,其原因主要有两点。第一,DNA单链分子可以通过杂交反应变成双链分子,而DNA双链分子又可以通过热变性为单链分子。第二,根据碱基互补配对原则,知道单链分子,实际上就等于知道该单链DNA分子所对应的双链DNA分子;反之亦然。所谓的碱基互补配
1DNA计算的通用性
自1994年Adleman提出是否存在一个通用的DNA计算框架问题以来,研究者们通过多种不同方法证明了DNA计算至少在理论上是通用的。DNA计算可以解决图灵机所能解决的所有问题,这也为DNA计算机的可行性提供了理论基础。例如:Lipton将Adleman的结果推广到解决任意的NP问题,并提高了计算速度。他在一些理想的假设下得到一个确定性的并行计算模型——无限制模型,并证明了可使用该模型用计算多项式的时间完成任意NP问题的求解;Adleman又在Lipton提出的无限制模型上提出了一种有限制的改进模型;Beaver则提出如何建立和操作含单个DNA分子的图灵机;Smith和
*基金项目:湖南省教育厅科学研究项目(10C0487);衡阳市科技计划项目(2008KG36,2009KJ27)
基于DNA计算模型的数据加密与解密_专业资料。讨论DNA计算模型,用DNA计算模型破解AES算法的可能性,介绍基于DNA二进制链加密和解密方法,并对它的安全性进行分析。...
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入阅读会员!获取下载券 DNA计算模型的研究 隐藏>> !"#$%&'( ...
关键词 经典 Ramsey 数 ;DNA 计算 ; 位序列 DNA 计算模型 中图法分类号 TP..., p 些数据代表了图的所有可能边的位置信这息 . 这就是说 , 一个长度为 ...
第3 1卷第1期 2200 8年1 2月 计 算 机 学 报 Vo13 No.1 .12De.208c0 CHINES oURNALOFC0MPUTERSEJ )经典Rmsy数DaeNA计算模型(:Ⅱ 基 于位序 列的 ...
DNA计算模型任晓玲 2012年4月17日 一、引言 DNA计算的原理 DNA分子作为信息载体(A、C、G、T四种碱基) 原始问题映射为DNA分子链 数据运算映射为对DNA分子链的...
第3 1卷第l期 2200 8年1月2 计 算 机 学 报 Vo13 No1 .1.2De.208c0 CHINES OURNALOFCOMPUTERSEJ 经典 Raemsy数D A计 算模 型() 位序 列计算模型 ...
DNA计算模型及应用综述_专业资料。自从Adleman博士最早利用DNA计算成功求解了7个顶点有向图的Hamilton问题以来,DNA计算被引入多个研究领域,成为当今科技发展的热点之...
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入会员!获取文档下载券 数值乘法的DNA计算模型 自从Adleman教授开创...
维普资讯 http://www.cqvip.com Cmue niergadApitnoptEgnei n plai s计算机工程与应用rnco 20,38 074() 6 7 数 制转换 的D A计算模型 N 孟大 志, 璞,高...
热门文档