Ｓｃｉｅｎｃｅ ａｎｄ ＴｅｃｈｎＯｌＯｇｙ Ｉｎｎｏｖａｔｉｏｎ Ｈｅｒａｌｄ Ｑ Ｑ： § Ｔ技术 Ｄ Ｎ Ａ计算方法与应用 叶子’ 孙飞一 （１．中国矿业大学（北京）机电与信息学院 北京 １ ０００８３；２．江西农业大学生物工程学院 江西南昌 ３３００４５） 摘要：简要介８ｇＤＮＡ计算产生的历史背景，结合囤论例子（邮递员路线图）叙述ＤＮＡ计算的基本概念与计算模型等方面内容。 关键词：ＤＮＡ计算 邮递员问题Ｄ Ｎ Ａ算法设计ＤＮＡ计算机 中图分类号：ＴＮ９１ ８ 文献标识码：Ａ 文章编号：１ ６７４－－０９８Ｘ（２０１ ｏ）ｏ２（ｃ）一００３７－－０１ １ ＤＮＡ计算产生的背景 步骤３：解决的方案，例如找出那些经 （２）选择操作表示计算内容模式，如粘 １９４６年，世界上第一台数字电子计算 过图Ｇ的所有边至少一次的闭途径，也就是 贴与剪切方式不同，对于序列切割与分离 机ＥＮＩＡＣ在美国的宾夕法尼亚大学诞生。 说，保留Ｇ的所有广义Ｅｕｌｅｒ闭迹。 的酶的选择不同［２１。 从此，电子计算机经历了从电子管（１９４６— 步骤４：求解答案，例如找出最短的广 （３）结果识别与分离，分子信标，荧光 １９５６）、晶体管（１９５７—１９６４）、集成电路（１９６５ ｌ９７０）到超大规模集成电路（１９７ｌ 至今） 四个发足 段。但是，量子理论已经揭示出 计算机芯片制造的物理极限尺寸一０．０８微 米。然而，１９９４年在美国加利福尼亚大学的 Ａｄｌｅｍａｎ博士利用ＤＮＡ分子序列计算ＮＰ完 全问题方法带给发展新型计算机的曙光…， 美国、加拿大、英国、波兰、德国、以色列等 国家的著名研究机构和大学都相继开展了 这一领域的研究工作，我国在此方面的研 究工作也已经展开，主要研究基地之一，华 中科技大学许进教授领导的ＤＮＡ计算和分 子计算机研究所。进行ＤＮＡ计算系统的探 索和研究，基于ＤＮＡ芯片的ＤＮＡ计算研究 探索和分子生物计算中的膜计算研究。此 外，国内还有东华大学和其他一些研究人 员从事这方面的研究，但是大部分的结果 都是综述性的。 ２ ＤＮＡ计算的生物学基础 ＤＮＡ计算的本质是对其分子序列的各 种操作完成问题的编码描述与算法设计和 实际生物技术模型来完成。因此每一个问 题解决，都是小小ＤＮＡ计算机模型的一次 运行 一１。具体生物操作包括下列几方面： ＤＮＡ分子序列双链分离与结合复性， 经设定温度加热与冷却完成，通常在聚合 酶链式反应（ＰＣＲ）检测中进行。 ＤＮＡ序列链的切割与连接；分别由于 内、外切酶与连接酶完成。 ＤＮＡ序列长度与序列组成测量；聚合 酶序列延长与Ｓａｎｇｅｒ末端终止方法测序及 凝胶电泳技术确定序列长短。 ＤＮＡ序列复制与重组标志，由ＰｃＲ完 成及荧光探针标志等。 ３基本数学计算 为了便于利用ＤＮＡ计算，首先将求解 问题的数学计算进行算法分解，计算过程 逐步可求，以便Ｄ Ｎ Ａ算法设计［６１。求解Ｇ问 题的算法设计如下的（例如邮递员路线图）： 步骤１：问题条件的描述，搜索出所有 关于Ｇ所有组合途径。 步骤２：找出符合问题条件的那些组合 途径；例如开始是Ｇ，结束也是Ｇ的固定顶点 的闭途径，也就是说，保留那些经过Ｇ的固 定顶点的途径。 义Ｅｕｌｅｒ闭迹（即所有广义Ｅｕｌｅｒ闭迹中权和 探针序列的选择 。 最小者），这就是我们所需要的解。 （４）结果解或者答案的提取技术组件。 步骤５：确定解出例如邮递员路线。 其中ＰＣＲ与凝胶电泳技术是必要的手段。 ４ ＤＮＡ算法设计 ６前景 Ｄ Ｎ Ａ算法设计在于将问题编码为 国际上，ＤＮＡ计算机的研究持续的“热 ＤＮＡ分子序列链，而将问题解以另一条链 点”＿８】。例￣１１２００１年ｌ１月，以色列的Ｗｅｉｚｍａｎｎ 编码；利 研究所的Ｓｈａｐｉｒｏ研制出由ＤＮＡ分子和酶分 用ＤＮＡ分子序列双链互补，通过对 子构成的生物计算机，它实质上是一种半 ＤＮＡ序列双链的生物操作完成数学计算过 自动化的可编程的有穷自动机。２００２年２ 程。 月，Ｓｕｙａｍａ等研制出一台用于基因表达分 下面简单介绍一下上述步骤的Ｄ Ｎ Ａ 析的ＤＮＡ计算机。同样在其他方面有广泛 算法 。 应用。未来主要在三方向发展与突破。一是 步骤１：对给定图Ｇ的顶点和边进行编 ＤＮＡ计算的通用语言设计，能够提供方法 码，将编码好的顶点所对应的Ｄ Ｎ Ａ片段 性＿４， 】；二所谓软计算，结合其他计算模型方 和边所对应的Ｄ Ｎ Ａ片段混合在一起，加 法，例如与神经网络模型的结合。三与分子 入缓冲液经Ｄ Ｎ Ａ连接酶的连接反应，生 生物学发展密切结合，解决自身实际能力 成图Ｇ的所有闭途径。 问题 １，例如Ｄ Ｎ Ａ算法的实际准确性与 步骤２：在第一步连接反应后的产物中 误差的限制，以及对生物学的反馈应用。 加入底物Ｄ Ｎ Ａ分子、适量的引物、ＤＮＡ聚 合酶及缓冲液进行ＰＣＲ扩增，使那些以固 参考文献 定点开始和结束的ＤＮＡ链呈指数增而保 【１】Ａｄｌｅｍａｎ Ｌ．Ｍｏｌｅｃｕｌａｒ Ｃｏｍｐｕｔａｔｉｏｎ ｏｆ 留。 Ｓｏｌｕｔｉｏｎ ｔ６ Ｃｏｍｂｉｎａｔｏｒｉａｌ ｐｒｏｂｌｅｍｓ． 步骤３：将第２步的产物进行纯化与分 Ｓｃｉｅｎｃｅ．１９９４，６６（１ １）：１０２１—１０２４． 离。在分离的过程中我们先以表示边权的 ［２］许进，王淑栋，潘强林（译）．ＤＮＡ计算 Ｄ Ｎ Ａ片段的补链为模板构造探针，再用 ［Ｍ】，北京：清华大学出版社． 构造的探针对纯化后的产物进行分离，凡 ［３】殷志祥．图与组合优化中的ＤＮＡ计算． 与该探针杂交的ＤＮＡ链中一定含有该Ｄ Ｎ 科学出版社，２００４． Ａ片段，再将之加热解链分离后保留了目 ［４】王翼飞．计算分子生物学［Ｍ】．北京：化 标ＤＮＡ链即包含图Ｇ的所有边，也就是说 学工业出版社，２００４． 我们找到了图Ｇ的所有广义Ｅｕｌｅｒ闭迹。 ［５］孟大志，曹海萍．ＤＮＡ计算与生物数学． 步骤４：对第３步的产物进行琼脂糖浆 生物物理学报，２００２，１ ８（２）：ｌ６３—１７４． 凝胶电泳，跑在最前段的就是最短的ＤＮＡ ［６李源，方辰，欧阳颀．最大集团问题的 ６】链。 ＤＮＡ计算机进化算法．科学通报，２００４， 步骤５：将上述步骤的产物进行测序， ４９（５）：４３９－４４３． 找到中国邮递员问题的结果解。 【７】张永有，程金平，朱艳冰．分子信标及其 应用研究进展，生命的化学，２００２，２ ５ ＤＮＡ算法的生物模型 【８］Ｓｕｙａｍａ Ａ．ｅｔ ａ１．ＤＮＡ Ｃｈｉｐｓ— 任何算法设计最终是依靠生物分子操 Ｉｎｔｅｒｇｒａｔｅｄ Ｃｈｅｍｉｃａｌ Ｃｉｒｃｕｉｔｓ ｆｏｒ ＤＮＡ 作的执行并由实际的生物技术与方法完 Ｄｉａｇｎｏｓｉｓ ａｎｄ ＤＮＡ ｃｏｍｐｕｔｅｒｓ．Ｐｒｏｃ． 成。不同的 ３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｍｉｃｒｏｍａｃｈｉｎｅ Ｓｙｍｐ， 操作技术与方法决定其计算的体系模 １９９７：７—１２． 型的不同。因此根据问题选择需要的构造 体系是关键。一般生物模型由下列分子计 算组件构成： （１）描述方式与结构，选择双链或者三 链ＤＮＡ分子序列； 科技创新导报Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｉｎｎｏｖａｔｉｏｎ Ｈｅｒａｌｄ ３７
