DNA计算及其应用(共2页).docx

精选优质文档-----倾情为你奉上 DNA计算及其应用 自动化1411 7 王张鑫 1994年，Adleman发表得论文《用分子计算解决组合问题》中，叙述了他如何用DNA分子的生物学反应来模拟一个著名的 N．P问题—有向哈密顿路径(栅P)的求解过程，并获得了结果因此 Adlem开创了一门新的计算方法：DNA计算DNA计算机的基本运算是通过生物化学反应来实现的，其存储介质是生物分子 脱氧核糖核酸(DNA)是一切细胞生物的遗传信息的载体，其基本结构单元是脱氧核苷酸而脱氧核苷酸又由碱基、戊糖和磷酸三部分组成组成脱氧核苷的酸碱基有四种，分别是腺嘌呤 A、胸腺嘧啶T、胞嘧啶C和鸟嘌呤G，每个脱氧核苷酸都只含有这四种碱基中的一种，人们通常用碱基名来指代整个脱氧核苷酸，碱基的特定化学结构使得A只能和T配对，G只能和C配对 因此，从计算机科学的角度看，DNA分子链可以看作是字母表{A，C，G，T)上的有限多重集合 研究表明DNA分子与现行计算机相比具有以下优势： (1)生物化学反应是并行反应，这使得DNA计算机本身就具有极高的并行计算能力。

(2)由于生物化学反应一般会释放出能量，因此Ⅸ蛆计算机与常规电子计算机相比，是极其节能的 (3)DNA分子的信息存储密度很高一个晶体管仅有一字节，而一克DNA包含1021个DNA碱基，相当于108万亿字节因此，世界上现在存储的所有数据用DNA来存储，可能只需几克DNA 由于DNA计算显示了高速并行计算、极少耗能、极大存储量的优势及其解决超大规模计算的可能性和潜在力，从而引起了计算机科学，数学科学和工程及生物分子学等诸多领域的学者们的极大兴趣 从计算机科学的角度看，DNA链可以看作是字母表A，C，G，T上的有限多重集合DNA计算实质上是对此集合作以下几种运算： (1)提取：设T是字母表∑上的多重集，S∈∑，产生+(T，S)与-（T，S) +(T，S)里分子都包含连续的S，而 -(T，S)里的分子则不包含连续的S (2)分离：设T是字母表∑上的多重集，S∈T，按S的长度将T分离成T1…… (3)合并：给定T-与T2，产生u(TT2，)，这里u(TT2)=Tu T2 (4)检测：给定T，如果T里有至少一个分子，返回“是”， 否则返回“不”；(5)扩增：给定T，产生丁’(丁)与丁”(r)，这里丁=丁’(丁)=丁"(丁)；(6)附加：设T是字母表∑上的多重集，S∈∑，使T中所有的串后都加上S。

DNA计算在密码学方面的应用：由于DNA计算天生具备极大的并行计算能力与海量储存密度这两个常规电子计算机所不具备的强大优势，所以DNA计算一经创立，就被尝试用来攻击密码系统 1995年，Boneh提出了一种基于lipton DNA计算模型攻击DES密码系统的方法Boneh采用的编码方法如下：每一比特均用两条独一无二的30个碱基长的寡聚核苷酸链编码，一条寡聚核苷酸链编码该比特所在的位置，另一条寡聚核苷酸链编码该比特的值将每一次异或运算的结果添加在编码密钥的Ⅸ蛆分子的后面S运算则通过提取、添加等操作将编码该次运算结果的DNA分子加在DNA分子的后面Boneh的算法采用并行提取的方法，一次能同时并行进行32个提取操作，只需916步，该算法就有可能破译DES由于现在的大多数生物仪器，例如PCR仪，具有同时操作多种溶液的功能，因此这种方法在实际上是可行的Adlem锄的编码方法如下，将一条长为1 1580聚体的单链DNA分子分成576个的 单元，每个单元含20个碱基，前56个单元编码密钥，第57—120个单元编码密文，剩余的单元 用来存储计算过程中的中间结果其异或运算用并行分离、并行设置来实现，S运算则用并行分 离、并行设置、并行组合来实现。

DNA计算在自动机领域的应用：从可行性的角度出发，研究DNA计算能有效且可靠地求解问题更具有现实意义正是基于这一点，利用DNA计算模拟有穷自动机成为DNA计算研究领域的一个重要内容，因为有穷自 动机是一种最简单的理想计算机，用DNA计算来模拟有限自动机比较容易实现1997年，Rose报导了用DNA计算快速、准确地模拟有穷自动机的方法；1997年，Gao设计了用DNA计算模拟非确定性有穷自动机的方法2001年，以色列科学家成功地进行了用DNA计算自动模拟有穷自动机的实验2003年，该国科学家又成功地设计出不需外界提供能量就能自动运行的DNA自动机2004年，他们还研究出能对基因的表达起调控作用的DNA自动机国内对DNA计算的研究刚刚起步不久，基本上都是针对大规模计算问题的研究2003年，赵健设计出运行于磁珠表面的可自动运算的DNA自动机从 2004年开始，北京航空航天大学DNA研究小组致力于用DNA计算攻击密码的研究我们已完成了攻击对称与非对称密钥系统的设计，并完成了其可行性论证 以上说明了DNA计算相关的理论研究、实验研究及DNA计算的应用重点描述了DNA 计算在密码学领域和自动机领域的研究现状与取得的进展。

从1994年Adleman提出DNA计算至今已十三年，在这十三年里，学术界对DNA计算机 的前景由怀疑到有所保留，到最后肯定即使仅从目前的研究成果来看，也能肯定得出DNA计算机来将在一些领域的完全替代电子计算机这一结论在很大程度上，DNA计算机能否有更大的作为取决于生物技术的发展专心---专注---专业。