DNA计算及其应用.docx

《DNA计算及其应用.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DNA计算及其应用自动化14117王张鑫1994年，Adleman发表得论文《用分子计算解决组合问题》中，叙述了他如何用DNA分子的生物学反应来模拟一个著名的N．P问题—有向哈密顿路径(栅P)的求解过程，并获得了结果。因此Adlem开创了一门新的计算方法：DNA计算。DNA计算机的基本运算是通过生物化学反应来实现的，其存储介质是生物分子。脱氧核糖核酸(DNA)是一切细胞生物的遗传信息的载体，其基本结构单元是脱氧核苷酸。而脱氧核苷酸又由碱基、戊糖和磷酸三部分组成。组成脱氧核苷的酸碱基有四种，分别是腺嘌呤

2、A、胸腺嘧啶T、胞嘧啶C和鸟嘌呤G，每个脱氧核苷酸都只含有这四种碱基中的一种，人们通常用碱基名来指代整个脱氧核苷酸，碱基的特定化学结构使得A只能和T配对，G只能和C配对。因此，从计算机科学的角度看，DNA分子链可以看作是字母表{A，C，G，T)上的有限多重集合。研究表明DNA分子与现行计算机相比具有以下优势：(1)生物化学反应是并行反应，这使得DNA计算机本身就具有极高的并行计算能力。(2)由于生物化学反应一般会释放出能量，因此Ⅸ蛆计算机与常规电子计算机相比，是极其节能的。(3)DNA分子的信息存储密

3、度很高。一个晶体管仅有一字节，而一克DNA包含1021个DNA碱基，相当于108万亿字节。因此，世界上现在存储的所有数据用DNA来存储，可能只需几克DNA。由于DNA计算显示了高速并行计算、极少耗能、极大存储量的优势及其解决超大规模计算的可能性和潜在力，从而引起了计算机科学，数学科学和工程及生物分子学等诸多领域的学者们的极大兴趣。从计算机科学的角度看，DNA链可以看作是字母表A，C，G，T上的有限多重集合。DNA计算实质上是对此集合作以下几种运算：(1)提取：设T是字母表∑上的多重集，S∈∑，产生+(

4、T，S)与-（T，S)。+(T，S)里分子都包含连续的S，而-(T，S)里的分子则不包含连续的S。(2)分离：设T是字母表∑上的多重集，S∈T，按S的长度将T分离成T1……(3)合并：给定T-与T2，产生u(T。，T2，)，这里u(T。，T2)=T。uT2。(4)检测：给定T，如果T里有至少一个分子，返回“是”，否则返回“不”；(5)扩增：给定T，产生丁’(丁)与丁”(r)，这里丁=丁’(丁)=丁"(丁)；(6)附加：设T是字母表∑上的多重集，S∈∑，使T中所有的串后都加上S。DNA计算在密码学方面的

5、应用：由于DNA计算天生具备极大的并行计算能力与海量储存密度这两个常规电子计算机所不具备的强大优势，所以DNA计算一经创立，就被尝试用来攻击密码系统。1995年，Boneh提出了一种基于liptonDNA计算模型攻击DES密码系统的方法。Boneh采用的编码方法如下：每一比特均用两条独一无二的30个碱基长的寡聚核苷酸链编码，一条寡聚核苷酸链编码该比特所在的位置，另一条寡聚核苷酸链编码该比特的值。将每一次异或运算的结果添加在编码密钥的Ⅸ蛆分子的后面。S运算则通过提取、添加等操作将编码该次运算结果的DNA

6、分子加在DNA分子的后面。Boneh的算法采用并行提取的方法，一次能同时并行进行32个提取操作，只需916步，该算法就有可能破译DES。由于现在的大多数生物仪器，例如PCR仪，具有同时操作多种溶液的功能，因此这种方法在实际上是可行的。Adlem锄的编码方法如下，将一条长为11580聚体的单链DNA分子分成576个的单元，每个单元含20个碱基，前56个单元编码密钥，第57—120个单元编码密文，剩余的单元用来存储计算过程中的中间结果。其异或运算用并行分离、并行设置来实现，S运算则用并行分离、并行设置、并

7、行组合来实现。DNA计算在自动机领域的应用：从可行性的角度出发，研究DNA计算能有效且可靠地求解问题更具有现实意义。正是基于这一点，利用DNA计算模拟有穷自动机成为DNA计算研究领域的一个重要内容，因为有穷自动机是一种最简单的理想计算机，用DNA计算来模拟有限自动机比较容易实现。1997年，Rose报导了用DNA计算快速、准确地模拟有穷自动机的方法；1997年，Gao设计了用DNA计算模拟非确定性有穷自动机的方法。2001年，以色列科学家成功地进行了用DNA计算自动模拟有穷自动机的实验。2003年，该

8、国科学家又成功地设计出不需外界提供能量就能自动运行的DNA自动机。2004年，他们还研究出能对基因的表达起调控作用的DNA自动机。国内对DNA计算的研究刚刚起步不久，基本上都是针对大规模计算问题的研究。2003年，赵健设计出运行于磁珠表面的可自动运算的DNA自动机。从2004年开始，北京航空航天大学DNA研究小组致力于用DNA计算攻击密码的研究。我们已完成了攻击对称与非对称密钥系统的设计，并完成了其可行性论证。以上说明了DNA计算相关的理论研究、实验研究