沧海横流，谁开辟了DNA计算？----我所认识的L. Adleman(6)   （唐常杰）

　　是谁带来DNA分子的千军万马，是谁打开了生物计算机时代之门？

　　其理念或前有渊源，但作出第一个能演示的DNA计算机原型的学者，是伦纳德·阿德曼（Leonard Adleman）。
　　还是先讲故事，后作科普，把DNA计算科普放到本系列最后，是因它有点神秘，又有点长，要写得容易懂，还真费思量。

    博学深思出灵感  下列取自对伦纳德·阿德曼的一次科学访谈录（意译）：
　　“我是个一生都异想天开的人。
　　“我躺在床上读Watson的基因分子生物学，DNA像一个四色项链， DNA双螺旋中两支上，碱基互补、聚合酶工作时，像图灵机的读写头游走于存储带 …
　　"Wow! 它像计算机,它可以计算，我立刻起身下床，开始了思考……
　　
　　该出手时就出手  敢想敢干、连远缘领域的艾滋病免疫都敢去客串一把的L.Adleman说干就干，于是就有了DNA计算实验室，于是就有了那张著名的狂热科学家的工作照：The mad scientist at work（参见系列博文之一）。
      天道酬勤，1994年，Leonard Adleman在论文[1]中公布了它设计的第一个DNA计算机原型，成功解决了7城市8线路的旅行商问题。虽其速度不敢恭维，但它的生物属性令人眼睛一亮，DNA也可玩计算！展示了生物计算机的潜力，开辟了一个崭新的领域。
　　
　　L.Adleman最初想象的工作场景：
  　(a)一米见方的DNA计算机，成束的试管装着DNA汤，一个传统的硅片电脑控制着几十个机械手，不断地移动和和倾倒试管（最初实验中，阿德曼自己临时顶替了设想的机械手）；
　   (b) 一系列生化过程（聚合链反应PCR等，详见科普部分）施加到这一锅DNA汤中N亿个DNA上，
　   (c)用生命的力量计算。N亿个巧妙编码的DNA“麦片”在生化酶作用下，并行地、采用“人”海战术、用生命的力量，去碰撞、粘连，实现基因组合；几秒钟内，代表结果的DNA “麻花”（双螺旋）出现在这一锅DNA汤中。
      (d)去粗存精，去伪存真，从DNA汤中的N亿个对象中，用一系列生化技术（包括超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等），取出那个代表结果的DNA，解释并输出结果，（详见后面科普部分）。
 
　　DNA计算的魅力。1立方米的DNA溶液可存1万亿亿比特数据；1立方厘米DNA溶液将超过1万亿片CD光盘的存储容量。速度可达到每秒10²⁰次,耗能甚微。据称，以色列学者2001年研制出首台可编程DNA“微微”电脑，体积只一滴水的一万亿分之一，为进入人体奠定了基础。
　　坚冰已经打破，航线已经开通。目前的DNA计算离实用尚远，还有太多的路要走，Leonard Adleman的工作展示了生物计算的可能性。DNA计算已成为全世界计算机科学家关注的新方向，有数百个团队在这里攻关竞争。
　　当记者问Leonard Adleman，你是否意识到你已经开辟新的科学领域，他谦虚地说，这是两个学科，即计算机科学与分子生物学，自然结合的产物。
　　他和分子生物学家Myron Goodman合作，建立了一个DNA计算和分子生物学的实验室。2001年获得发明专利。
　　
　　以子之矛攻子之盾 L. Adleman参与发明了RSA公钥技术（盾） ，又发明了DNA计算（矛）；以子之矛，攻子之盾，结果会如何？
　　RSA公司 1978年悬赏100万美元征解,公开了公钥  (n, e )， 1995年4月26日，路透社报道， 600位专家，用1600台机器，用 8个月时间，把公布的129位整数 n分解为 p*q，求得d，构造出私钥。这说明129位 不够长，不够安全。
　　如果沿用上述的平台来破解256位的RSA，其计算量要大10¹²⁸倍，如果没有方法上的革命，等它等到“天亦老”了。现在已有研究者提出用DNA 计算破译加密标准DES的方案，也有人雄心勃勃想用DNA计算的“人海战术”破解较小规模的RSA；在技术日新月异的今天，科学预言家一般不轻言某项基础研究“不实用”、某项技术“不可能”，但可说，近两年不太容易。
　　
用一锅DNA汤”来计算旅行商问题（以下为科普内容）
　　拟用一个5城8线的旅行商问题来说明DNA计算的轮廓，此文利用了一些笔者过去的PPT页面，虽读过一点DNA计算文章，但未做过这方面的项目，理解自然就不深刻；初稿写好后，请了一位非计算机专业、亦非生物专业，但知识面较宽的大三学生来试读，他觉得难懂的地方或者删去，或者改写成了非标准的比喻（如DNA麦片，DNA麻花），失误之处，请专家指正。
　　
　　虚拟的“22世纪梦之旅”公司. 此公司开辟了 北京、天津、太原、郑州、济南 五城的飞艇娱乐旅游，开张伊始，仅图1中箭头所示的8条航线。
　　拟解决的问题：某人想从北京出发，游遍五个城市，到郑州结束，每城都要到且仅到一次，不考虑返程（例如，返程可在郑州坐火车）；请用DNA计算机找出一条合乎要求的旅游路线。

　　
　　　　　　　图1 DNA双螺旋碱基配对  和   5城8线旅行问题

　　问题中仅5城8线，不用计算机也可看出“北京--> 天津--> 太原--> 济南--> 郑州” 是一个正确答案。
　　难度随城市数k呈指数增长，当城市数k很大时（例如10⁴数量级）,目前的高级硅片计算机+巧算法 也会 “芯有余而速不足”。这是图论中的旅行商问题，是典型的NP完全问题。时下已有人宣称证明了“P不等于NP”，可能其证明或有瑕疵，但人们都倾向于相信这一结论，所以，NP问题是难计算的。
　　而Leonard Adleman竟异想天开，要用“一锅DNA汤”来计算它。
　　　　
(1) 准备工作，符号和编码长度
　　DNA中有4种个碱基，其名称首字母是A、C、G、T；推荐一种助记法：gCat，Cat是猫，“g-猫”既时髦又响亮，词内的字母顺序能帮助记忆下列规则：构成DNA双螺旋时，G、C配对（或互补）， A、T配对（或互补）。
　　DNA双螺旋的两个分支，就像阴模和阳模；DNA分裂--复制时，阴阳并行，像太极理论一样，1-->2-->4--> …-->2^n,成指数的增长。
　　如果一个汉字用三个字母表示，四个字母表达4^3=64个汉字，对我们这个小问题够用了。（大问题时，把编码加长）。本问题中，城市名含两汉字，用6个碱基表示。长度为6的编码可以区分 4^6=2^12=4096个对象，够用了。

(2)  DNA麦片
      用DNA的4个碱基G、C、A、T给城市及已通航线编码。
      图2中，城市序列 中的带框文字 是5城市的编码，长度5X6=30;航线序列是已通航线中的4条，（其余4条航线未画出），其中 头控 和 尾控 是为了保证 从北京开始，到郑州结束, 长度3+4X6+3=30。

  　　　　　　　　　　　　　　　　图2   5城4线的编码
　　
　　易见，按G与C互补、A与T互补的规则，航线编码串刚好是城市编码串的补码，两序列可绞成长为30的双螺旋结构（参见图1左边的双螺旋）。
　　
　　带框的字符串只含3个或6个碱基，较短小，好像是麦片（而不是长面条）；此问题5城8线，共需 5+8+2=15种DNA麦片，表达了5城8线 和头尾控制，这些麦片可用专用设备制备，也可到专门的生化公司或研究机构订货，几毫升就有若干亿个。
　
（3） 生命的力量使得DNA麦片汤变成麻花汤
　　是金子就要放光芒，是生命，就要生长。
　　把15种DNA麦片及其它必要的材料放在试管中，在正确的时间加入正确的酶（如限制内切酶、结合酶、转移酶、外切核酸酶 、修饰酶），给以合适的温度压力，生命的奇迹发生了，亿万个麦片 在DNA汤中 翻滚、碰撞、粘连，最后变成一锅麻花汤。
　　例如，代表 北京 和 天津 两个城市的麦片，通过互补的 京天线  ，可连接成图3中的麻花中的一小段：
　　
　　
　　　　　　　　　　　　                    图3
　　
       想象一下，图2的城市序列 和 航线序列 分写两纸条，然后对准互补的碱基，搓绳一样绞起来。
      得到了什么？DNA双螺旋结构！参见图1左边的双螺旋。
      由于我们有控制头尾的麦片，CGA使头为北京； GGC 使得尾为济南；所以，这一锅DNA麻花 表达了各种各样路径，且以北京开头，济南结尾。（这里简化了复杂的生化过程）。
      这是生命的礼赞，这是信息的演绎，这是DNA在计算！
   
       一条好消息： 这一锅麻花汤中，肯定已了有若干这样的DNA双螺旋：代表了从北京到济南的、不重复城市的、且游遍了5城市、的正确的航线；当然，并不唯一。
       一条坏消息： DNA汤中也夹杂了其他不合格的线路，有的有重复城市，有的长度不合格，鱼龙混杂。
      1994年，Adleman煮了一锅7城8线的DNA麦片汤，只用了几秒钟，就成了DNA麻花汤；但接下来，取其精华，去其糟粕的过程用了一个星期！
 
用电泳技术，筛出长度合格的线路
　　注意，DNA常带负电，用gel电泳技术，在上正下负的电场之下，不同长度的DNA受到不同的力，使得他们（在受力图上）像鸡尾酒一样分层，短的靠近上层，长的靠近下层，同长的在一层。
　　有差别就有办法，通过适当的生物化学参数或技术，可取出长度为30（碱基数）的DNA，其双螺旋结构中，一支包含五个城市，另一只包含了4个航班。（可再参见图2）。
　　筛选尚未成功，因长度为30（碱基数）的DNA中，五城可能有重复，（同时也就有遗漏），所以，L Adleman同志仍需努力。
 
　　磁铁钓硬币的启示。有某农家乐，招揽游客向池中假山上“福”字投币祈福。每天傍晚，老板娘用钓鱼竿悬挂磁铁，把一元硬币钓出来，（因为 一元硬币与磁铁有亲和力），而一分五分的铝币，则暂留水中招揽游客。映射到这里，老板娘不自觉地用了一种称为 “亲和力萃取”的高技术。
　　
　　 DNA麻花汤之钓鱼术 用亲和力萃取技术（affinity purify），模仿上述老板娘，但把磁铁 换为能吸引北京DNA的材料，利用亲和力，可把 包含北京碱基的、长度为30的DNA钓出来，放到缓冲池1中，再从缓冲池1中，把含天津碱基的DNA钓出来，…….,如此,流水线方式（串联地）地钓5次，则得到了含5个城市的DNA，都以北京开始，济南结束，且不重复不遗漏。
      五次钓鱼可比喻为过五关，过完五关，同时也“斩了四将” 得到四条航线。
      Adleman做完去粗存精、去伪存真的过程用了一周。对大规模题目，可以用渐进 PCR方法，改进效率，（类似动态规划，保存并引用中间结果），减少时间代价。

　　观察上述流程：DNA麦片-->DNA麻花汤-->电泳筛选--> DNA麻花汤中钓鱼，这就是DNA计算机解决5城市8线小规模旅行商问题的大致思路。
　　一时间，学术界一片匪夷所思的感叹，一阵跟风追浪的潮流。
　　什么是创新， 这样的“无中生有”，就是创新； 什么是掀起潮流？这样的“兴风作浪”就是掀起潮流！

　  关于L. Adleman的六篇系列博文到此结束，如果读者意犹未尽，请复习博文之二，　图灵奖得主是怎样炼成的--侧应钱学森之问，那里还留下了若干思考。该文最初被策划为系列之六，为了内容的由浅入深，才改为之二，请读者发表评论或博文来探讨和抒怀。科普文章中通俗和严谨不容易平衡，通常是宁可漏写，不可错写；失误之处，请专家指正。

关于 Leonard . Adleman的系列博文
　　1一位狂热科学家的工作照 

      2 图灵奖得主是怎样炼成的-----侧应钱学森之问  
      3 他凭什么得到图灵奖？ （在RSA中的贡献，+RSA科普）

      4  一不小心，成了计算机病毒的教父 (科普）  

      5  奇思妙想，客串艾滋病免疫研究      (科普）  

     6  沧海横流，谁开辟了DNA计算?  （DNA计算简介，科普）

             其它系列博文的入口           唐常杰博客主页          科学博客主页

参考文献
  [1] Adleman, L.M., Molecular computation of solutions to combinatorial problems, Science, 226, 1021-1024，(Nov. 11)  1994