 《三思科学》电子杂志
第六期，2001年12月1日
目 录
封面
封面故事
[异调]斐波那契螺旋
编者的话
[柯南]过去与未来的好时光
新闻
[碧声]与日逐走
[柯南]你在那里
[柯南]再见，流星雨！
求知
[逍遥]DNA与哈密顿路径问题
[九歌]再谈鸟鸣
[小江]细胞周期，癌症与诺贝尔奖
[荒原]细胞学的发展
译述
科学美国人：谎言鉴别（第二部分）
自然：探索虚拟宇宙
观点
[小江]同性恋，艾滋病与社会
——献给世界艾滋病日
[刘华杰]关于钱学森的“人体科学”
历史
[异调]ENIGMA的兴亡（三中）
[韩雪涛]一元三次方程的故事
[碧声]寻找经度（上） （下）
书评
[一笑]《惊人的假说——灵魂的科学
探索》读书笔记（一）
辨伪
[异调]亚曼拉“公主”的“木乃伊”
[柯南]天使和魔鬼的影子
[方舟子]破解“惊世大预言”
版权声明·订阅与投稿须知
三思科学杂志社
本期责编 异调
下期责编 柯南
三思言论集
©2001,All Rights Reserved.
|
 |
DNA与哈密顿路径问题
 逍遥
考虑这样一个问题，比如：哈密顿
路径问题。十九世纪中期爱尔兰的皇家
天文学家哈密顿(William Rowan Hamilton)
提出，在一个有多个城市的地图网络中，
寻找一条从给定的起点到给定的终点沿
途恰好经过所有其他城市一次的路径。 |  |
这个问题和著名的过桥问题的不同之处在于，某些城市之间的旅行不
一定是双向的。比如A→B,但B→A是不允许的。
换一种说法，对于一个给定的网络，确定起点和终点后，如果存
在一条路径，穿过这个网络，我们就说这个网络存在哈密顿路径。哈
密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据
说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些
顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐
的时间（比如几百年）才能确定其是否存在一条这样的路径。
在这里我们讨论一种简单的算法，目的不是为了论证这种算法的
优越，而是利用这个算法，我们可以用DNA分子来帮我们找到这样一
条哈密顿路径是否存在。
算法步骤：给定一个有N个顶点的网络
1. 生成一组穿过网络的随机路径（当然这个随机路径要足够的多）
2. 对于这一组路径中的每一条作如下检验
a): 检查该路径的起点和终点是否正确。如果不正确则去掉此路径。
b): 检查该路径是否恰好经过n个顶点。同上
c): 对于每一个顶点，检查该路径是否经过。同上
3. 如果该路径为非空集，则报告说找到哈密顿路径。
让我们来看一个简单的例子：
图1
现在我们的问题就是找到这个网络中，从北京到上海的哈密顿路
径。当然这个问题的答案很简单，实际路线显然是北京→成都→南京
→上海。不过我们的真正问题在于怎样用DNA分子来得到这个结果。
在您继续往下看之前，让我提醒您一件事。无论如何，对于DNA
分子来说，其所有的信息都用碱基顺序来表示的。而两条DNA链如果
其上的碱基顺序可以互补配对的话，那它们就会形成局部的或者整条
链的双链结构，这就是著名的DNA双螺旋。配对规则为：A—T;T—A;
G—C;C—G。(注意DNA链是具有方向性的，互补配对的双链方向相反)
好现在让我们把这个问题进行转换。
首先我们给每一个城市以及城市之间的连接都给出一段DNA的碱
基顺序来代表它。当然为了可以用DNA分子来找到相关的路径，这些
碱基顺序是有特点的，不能完全随机。
碱基顺序：
1. 代表各个城市的碱基顺序以及它们的互补链上的碱基顺序。
北京：5'-AGGCTTGA-3' 3'-TCCGAACT-5'
成都：5'-GACCTACA-3' 3'-CTGGATGT-5'
南京：5'-CCGAAATT-3' 3'-GGCTTTAA-5'
上海：5'-TTAGCGAT-3' 3'-AATCGCTA-5'
2. 上面的碱基顺序实际上是随机的，如果你愿意完全可以自己设置，
不过你得注意必须有足够的长度，一是为了让它们彼此不同，二是为
了下面这个步骤也必须设置得比较长才行。为了表示各个城市之间的
联系，我们也同样用一个碱基顺序来表示这个信息。不过这个碱基顺
序是被上面的顺序所决定的。（默认DNA链方向为5'-3'）
北京→成都： TTGAGACC
（注意：我们所使用的是北京这个城市的后半段碱基顺序加上成都这
个城市的前半段碱基顺序，来表示这个信息。按照这样的规则，我们
依次构造图1中所有的联系方式。）
成都→北京： TACAAGGC
北京→上海： TTGATTAG
成都→上海： TACATTAG
成都→南京： TACACCGA
南京→上海： AATTTTAG
由于我们已经知道答案是：北京→成都→南京→上海，将这个答案转
换为碱基顺序的话，显然我们有“TTGAGACC TACACCGA AATTTTAG”。
所以我们的问题进一步的转变为，我们是否有某种办法，得到这样一
个特定的碱基顺序？观察一下这个碱基顺序很显然它就是简单的把北
京至成都、成都至南京、南京至上海的这三段碱基顺序给连在一起了。
在体内负责催化DNA链连接的酶被称为DNA连接酶。
考虑某一个双链DNA,由于种种原因，使得其某条链上的连接脱氧
核糖核苷酸的共价键断裂了。对于这种情况机体使用DNA连接酶来加以
修复，将断开的这两条链重新连接在一起。见下面的例子
----------------------
G G G C G T T A
......A T C C C G C A A T G T......
---------------------- ----------------------
下面这两条分开的DNA链可以在上面连接酶的作用下，连接成一条单
链。
计算开始：
1. 用DNA连接酶连接代表各个城市之间联系的DNA链。将上
述代表各个城市的互补链以及代表各个城市之间联系的DNA链若干以及
DNA连接酶等加入试管。
由于DNA连接酶所固有的限制，它决不会随便把任意两条DNA链在
一起，所以实际上反应如下发生。首先我们有
成都：GACCTACA CTGGATGT（互补链）
北京→成都： TTGAGACC
成都→上海： TACATTAG
成都→南京： TACACCGA
注意后两条链的前半段和第一条链的后半段拼在一起，恰好就是成都
这个城市的碱基顺序，这是我们在构造城市之间的联系的碱基顺序的
时候所规定的。而这两段DNA可以和代表成都的互补链配对形成DNA
双链，这就意味着DNA连接酶可以将北京至成都以及成都至南京连接
在一起。当然也可以把成都至上海连在一起。这取决于随机因素，我
们可以得到TTGAGACC TACACCGA或者TTGAGACC TACATTAG。
以此类推在DNA连接酶的作用下，所有可以连接在一起的DNA链最终
都连接在了一起。由于DNA连接酶的效率，几乎在一秒之内，所有可
能的穿越网络的路径就通过该方式连接在一起了。现在我们的任务是
要去掉那些不是答案的DNA链。
对照本文最初给出的算法步骤，上面的算法至此我们完成了算法
步骤的第一步。
1. 生成一组穿过网络的随机路径（当然这个随机路径要足够的多）
现在让我们来完成算法的第二步：
a): 检查该路径的起点和终点是否正确。如果不正确则去掉此路径。
2. PCR扩增我们所需要的DNA链。PCR扩增法是在体外进行快
速DNA链复制的一种常见方法。
DNA链复制的特点是半保留的复制机制。双链DNA在复制时，解开
成两条单链，分别作为模板，在DNA聚合酶的作用下合成新的与之配对
的子代DNA双链。在体外解链的过程，可以用升高溶液温度的方法解开。
DNA聚合酶的特点是，它不能从头开始进行聚合反应，它只能延长已有
的子代DNA链，在体内DNA合成的起始首先由RNA聚合酶提供一小段与
模板DNA配对的RNA链，这一小段RNA链被称为引物。然后在由DNA聚
合酶将之延长。在体外，我们人工提供引物，当然我们完全可以使用一
小段与模板配对的DNA链。因为DNA聚合酶并不在意引物是RNA还是
DNA。注意为了合成双链DNA，我们给每一种模板提供一小段引物。为
了合成足够多的DNA提供的引物数量显然是可以及其巨大的。不要忘记，
引物一旦被使用，就参与形成了子代DNA链。
正是DNA聚合酶的这个性质，使我们得以筛选我们所需要的DNA链
来进行扩增。在我们的进一步实验中，我们分别提供起点城市和终点城
市的一半碱基顺序，作为引物，从而使我们想得到的DNA链大量扩增。
北京：5'-AGGCTTGA-3' 3'-TCCGAACT-5'
上海：5'-TTAGCGAT-3' 3'-AATCGCTA-5'
（根据上面的正确的哈密顿路径的答案，事实上5'-TTGAGACC TACA
CCGA AATTTTAG-3'则是我们希望扩增的DNA链）
我们给定的一对引物是：5'-TTGA-3'；5'-CTAA-3'，其中：
5'-TTGA-3'：这个引物将启动从正确的起始点北京开始的DNA链的互补
链的互补链的复制。负负得正实际上我们就得到了原链。而原链的互补
链由另一个引物启动合成出来。
5'-CTAA-3'：启动以正确的终止点上海为终止的DNA链的互补链的合成。
实际过程如下：
5'-TTGAGACCTACACCGAAATTTTAG-3' 由DNA连接酶得到的原链
3'-AACTCTGGATGCGGCTTTAAAATC-5' 由引物5'-CTAA-3'启动合成
的互补链
通过加热的方法，分开这个新形成的DNA双链，分别作为模板。
5'-TTGAGACCTACACCGAAATTTTAG-3' 由DNA连接酶得到的原链
3'-AACTCTGGATGCGGCTTTAAAATC-5' 由引物5'-CTAA-3'启动合成
的互补链
5'-TTGAGACCTACACCGAAATTTTAG-3' 由引物5'-TTGA-3'合成的
“原链”
3'-AACTCTGGATGCGGCTTTAAAATC-5' 由引物5'-CTAA-3'启动合成
的互补链
上述过程循环往复，具有正确起始点和终止点的DNA链的数目以
指数形式迅速增长，它们的增长方式显然是1、2、4……。而只具有正
确终止点的DNA链只能以线性数目增长，而且只能增长它们的互补链。
因为它们不能形成有效的双链，而只能是互补链的1、1、1、1……的
增长。只具有正确终止点的实际上无法增长。（当然考虑到在我们的
溶液中存在先前加入的各个城市的互补链，它们也可以作为引物启动
可以与之配对的DNA链的互补链合成，但是考虑到我们所加入的引物
的巨大数量，这些增加几乎可以不计。）
到此我们就得到了大量的具有正确碱基顺序的DNA链（如果它真
的存在）。现在让我们更进一步的纯化筛选。
b): 检查该路径是否恰好经过n个顶点。同上
这一条规则意味着，我们的DNA链的长度必须为24个碱基，因为每8个
碱基代表一个联系。而要恰好经过所有的城市，北京、成都、南京、
上海，它刚好具有三（即四减一）个联系。怎样把那些多于或者少于
24个碱基的DNA顺序筛选掉？我们可以使用电泳的技术。
3. 电泳。简单说来电泳技术利用带电粒子在电场中的移动速度，正
比于它所带电量而反比于它的质量Q/M(荷质比)。理论上只要荷质比
不同就可以将它们分离。目前在核酸电泳技术中，我们已经有办法可
以将哪怕仅仅相差一个碱基数量的DNA分离开。
所以利用电泳方法，筛选掉所有那些不是恰好等于24个碱基长度
的DNA链。
c): 对于每一个顶点，检查该路径是否经过。同上
4. DNA探针技术。将上面步骤中恰好等于24个碱基长度的DNA链从
电泳介质中收集起来，利用DNA探针技术，加以检查。
由于我们在扩增过程中实际上已经检验过起点和终点，现在我们
只需检查那些位于途径中间的那些城市。
成都：5'-GACCTACA-3' 3'-CTGGATGT-5'（互补链）
南京：5'-CCGAAATT-3' 3'-GGCTTTAA-5'（互补链）
5'-TTGAGACCTACACCGAAATTTTAG-3'，怎样把这个正确顺序
筛选出来？要确定我们的DNA链经过了成都这个城市，我们只需将代
表成都市的互补链DNA作为探针，去找找溶液中是否有可以和我们这
个探针配对的DNA链即可知晓。大家不要忘了，我们城市之间的联系
是用出发点的后一半加到达点的前一半的碱基顺序拼出来的。作为中
间城市，必然有到达它也必然要从它离开。所以实际上在符合我们要
求的DNA链中必然包含了所有中间城市的碱基顺序。
比如：5'-TTGAGACCTACACCGAAATTTTAG-3'，在以蓝色加
粗字体表示的碱基顺序中，前一半四个代表来到成都，而后一半的四
个代表从成都离开。加入成都的互补链，如果它们可以配对，则代表
这条链经过了成都，而不能配对的话，则自然是没有经过成都。为了
淘汰那些不合要求的DNA链，我们可以有多种方法。比如将探针固定
在某些膜上或者显微大小的铁球上等等，一句话，固定住探针，凡是
可以和探针配对的DNA链也就被固定了，而留在溶液中的DNA链，则
被放弃。将含有探针的显微铁球或者膜，放入另一溶液中，加热使双
链解开。在将此溶液用第二种探针检查，直到检查完所有的探针为止。
在最后一次加热使双链解开以后，如果溶液中还含有DNA分子的话，
那就表明找到了哈密顿路径。
为了使结果显著，这是由于在每一步操作中，必然有所损失。我
们可以在进行一次PCR扩增，使用前面使用过的DNA引物。最后我们
可以用电泳检查，是否存在DNA链。如果有那就是答案了。这就完成
了算法步骤中的最后一步：
3. 如果该路径为非空集，则报告说找到哈密顿路径。
由于本题答案已知，所以我们就不需要进行DNA碱基顺序测定以
读出具体的答案了。《用DNA进行计算》一文的作者，仅仅是想通过
这个方法来看看是否可行，所以只要最后一步电泳结果显示有DNA
（当然长度肯定是24个碱基），也就可以了。
我写本文的目的不是谈论DNA计算，因为我对计算一无所知。而
只是想借此介绍一些基本的分子生物学中的概念。至于大家看了以后
见仁见智则是读者诸君自己的事了。
参考文献
《科学美国人》1998.11 《用DNA进行计算》 作者:Leonard M.Adleman
|
