（基础数学专业论文）任意地图四着色问题的dna算法.pdf

摘要 本文对地图的着色问题进行了研究，地图的着色问题是一个n p 难题，它 源自著名的四色问题。着色问题主要研究如何将图的点或者边用给定数目的 颜色涂染，使得相邻两点或者两边着色不同本文通过考察三剖分边着色的性 质，提出了脉组的思想，并证明了覆盖平滑三剖分所有区的脉组的存在性。 根据以上的分析，我们给出了两个算法：一个是平滑三剖分边的三着色 的d n a 算法，并且在此基础上，我们还给出了一个平滑三剖分顶点四着色的 算法。任何一个地图的着色问题都可以转化成三剖分从而平滑三剖分的顶点 着色问题，因此对于任何一个地图，我们都可以对它进行着色。最后我们给 出了一个计算机程序对算法进行了模拟。 本文的两个算法都具有很好的复杂度，分别是多项式时间复杂度和线性 增长的空间复杂度。理想的，分别用十几步生化操作就可以找出一个平滑三 剖分图的三着色和四着色，而所需的d n a 分子链并不是很多，因此可以解决 很大级别的图着色问题，从而验证了d n a 计算在并行计算上的优越性。本文 的编码方式十分简单、直观，编码具有规律性，易于实现。在读取操作中， 我们将一条脉组上的着色信息转化为芯片上的荧光颜色，从而可以读取着色 的信息。对以上算法经过稍作改动，还可以找出平滑三剖分图的全部三着色 和四着色。 本文的算法和四色问题联系十分密切，因为构型的自由补全图是一类平 滑三剖分，因此可以用我们的算法来进行着色。 关键词：d n a 计算：四色问题；地图着色问题；d n a 芯片 a b s t r a c t t h e m a pc o l o r i n gp r o b l e m i so r i g i n a t e df r o mt h ef a m o u sf o u r - c o l o r p r o b l e m ，a n d i ti san p - h a r dp r o b l e m t h eg e n e r a ls t u d yo fi tf o c u so nh o wt oc o l o rt h ev e r t e xo r e d g eo f a m a p s u c ht h a tt w ov e r t e xo re d g ew h i c ha r ec o r r e l a t e dh a v ed i f f e r e n tc o l o r u s i n gc e r t a i nc o l o rn u m b e r i nt h i sp a p e r , w ep u tf o r w a r dt h ei d e ao f r i bg r o u p a n d p r o v e t h a tt h e r ei sar i bg r o u pc o v e r i n ga l lt h er e g i o no f as m o o t h t r i a n g u l a t i o n b yt h ea n a l y s i so fr i bg r o u p ，w ep r e s e n tt w oa l g o r i t h m ：at r i c o l o r i n gd n a a l g o r i t h ma n d o nt h i sb a s eaf o u r - c o l o r i n gd n a a l g o r i t h mo f s m o o t ht r i a n g u l a t i o n a c o l o r a t i o no f e v e r ym a p c a l lb ec o n v e r t e di n t ot h ev e r t e xc o l o r a t i o no fa t r i a n g u l a t i o n s ow e c a nc o l o re v e r y m a p a t l a s tw e g i v eac o m p u t e rp r o g r a m w h i c h s i m u l a t et h i sa l g o r i t h m t h et w o a l g o r i t h m i nt h i s p a p e rb o t h h a v e g o o dc o m p l e x i t y ：p o l y n o m i a l c o m p l e x i t y i nt i m ea n dl i n e a rs p a c e c o m p l e x i t y i d e a l l y ，w ec a n f i n da t r i c o l o r i n go f a t r i a n g u l a t i o nu s i n gs e v e r a lb i o c h e m i co p e r a t i o na n df e w e rd n as t r i n g s t h e r e f o r ew e c a l ls o l v eh a r dm a pc o l o r i n gp r o b l e mw i t hg r e a t s i z e ，i tr e f l e c tt h es u p e r i o r i t yo f p a r e l l e ld n ac o m p u t i n g t h ec o d i n gi nt h i sp a p e ri ss i m p l ea n dd i r e c t ，a n di tc a n e a s i l y b er e a l i z e d i nt h e r e a d i n go p e r a t i o n , d n ac h i p c o n v e r tt h e c o l o r i n g i n f o r m a t i o no far i bg r o u pi n t of l u o r e s c e n c ea c t i v a t e db yh y b r i d i z a t i o n b yal i t t l e m o d i f yo fo u ra 1 9 0 r i t h m , w ec a nf i n da l lt h et f i - c o l o r i n ga n df o u r - c o l o r i n go fa s m o o t h t r i a n g u l a t i o n t h ef i r s ta l g o r i t h r ai nt h i sp a p e rh a sg r e a tr e l a t i o nt of o u r c o l o rp r o b l e m ，f o rt h e f r e ec o m p l e m e n to f c o n f i g u r a t i o ni ss m o o t ht r i a n g u l a t i o n , i tc a nb ec o l o r e db yo u r a l g o f i t h m k e y w o r d s ：d n a c o m p u t i n g ；f o u r - c o l o rp r o b l e m ；m a pc o l o r i n gp r o b l e m ；d n ac h i p l i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 北京工业大学或其它教育机构的学位或证书而使用过的材料与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意 签名趣日期鱼至巡日期 2 ，扣争- o 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文 ( 保密的论文在解密后应遵守此规定) 豁益塑堕导师躲韭 日期：垄! 生：z ! 第1 章绪论 第1 章绪论 1 1 d n a 计算的方法 人们一直在追求一种速度更快、体积更小的计算机。1 9 5 6 年，理查德冯纽 曼就曾经充满幻想的描述了构建一台“亚显微”计算机的可能性。目前，尽管计 算机在不断提高速度、容量和性能上已经取得了巨大的进步，尽管摩尔定律正在 走向极限，但“亚显微”计算机的目标还没有实现。 1 9 9 4 年，美国南加州大学的l e o n a r dm a d l e m a n 在美国著名杂志s c i e n c e 上 发表了一篇划时代的论文“1 ，用人眼看不到的d n a 分子来做计算解决了一个n p 难题一有向哈密顿路径问题，借助生化实验向冯纽曼的理想迈出了开创性的一 步，从而开创了一个非标准计算研究的新领域。它使人们对计算的本质产生了新 的理解和认识。 d n a 计算解决问题的基本思想是：利用9 n a 特殊的双螺旋结构和碱基互补配 对原则对问题进行编码，把要运算的对象映射成d n a 分子链，在d n a 溶液的试 管里，在生物酶的作用下，生成各种数据库，然后按照一定的规则将原始问题 的数据运算高度并行地映射成d n a 分子链的可控的生化过程。最后，利用分子 生物技术破获运算结果“。3 。 d n a 计算的核心问题是将经过编码后的d n a 链作为输入，在试管内经过一定 时间的生物化学反应来完成运算，使得从反应后的产物及溶液中能得到全部的 解空间。 d n a 计算在本质上属于生化反应，为了利用d n a 分子完成给定的任务，我们 必须借助对d n a 分子的各种操作技术。对d n a 分子的操作，既有物理的，也有 化学的。物理操作实质上是调控生化反应的外部条件，例如温度，酸碱度等等。 此外是来自各种生化实验手段，尤其是通过各种酶的操作。经常用到的操作有 以下几种”1 ： ( 1 ) 合成：使游离的碱基形成寡核苷酸的过程。 ( 2 ) 混合：把两个试管中的溶液混合。 ( 3 ) 链接：两条带有粘头( 也就是没有完全配对的双链) 的d n a 双链在连接酶 的作用下，按w a s t o n c r i c k 互补配对原则且将缝隙修补好，从而连接在一起的过 程。 一，。，：。，些耋些垄鐾耋些掣丝垒，。，苎一 ( 4 ) 剪切：利用特定的限制性内切酶，在d n a 双链的某个位置切断形成带有 粘头的两条链的过程。 ( 5 ) 退火和溶解：这是两个完全相反的过程，退火是指两条互补的d n a 单链 在温度逐渐降低的条件下，合成一条双链的过程；溶解是一条d n a 双链在温度升 高时，分解为两条互补的单链的过程。 ( 6 ) 放大：利用p c r 技术，游离的碱基与作为模板的链配对连接形成双链， 然后解成单链，继续这样的过程，于是目标链会以2 的指数级增长。 ( 7 ) 提取；将含有特定d n a 短链的分子提出来，这要通过将特定短链的互补 链吸附在小磁珠上，然后用磁铁将小磁珠吸出来的过程。 ( 8 ) 延长：这一过程需要一条已知单链模板和一条已存在的、并已与模板的 一小段匹配的引物d n a 序列，要延长的d n a 序列根据模板给出的序列结构，在聚 合酶的作用下由5 端到3 端的方向不断延伸。 ( 9 ) 缩短：通过外切核酸酶从d n a 分子的末端去掉一个核苷酸而缩短d n a 分 子。 ( 1 0 ) 分离：将d n a 分予置于一有凝胶的电场中，由于d n a 分子带负电，在电 场中会向正极移动，长度大的分子链受到凝胶的阻力大，移动速度慢，因此可用 此技术去获取一定长度的d n a 分子链，也可区分不同长度的d n a 分子。 d n a 计算之所以具有吸引力，是因为它具有如下三方面的显著特点“。“： ( 1 ) d n a 计算具有高度的并行性，运算速度快。在a d l e m a n 的实验中，通过 适当估计，d n a 串的并行操作数目可达1 0 ”，许多研究者认为，用当前技术1 0 ” 到1 0 “个串的并行操作是可以达到的，a d l e m a n 认为这个数字可以达到1 0 2 z “”； ( 2 ) d n a 作为信息的载体其贮存的容量非常之大，1 立方米的d n a 溶液可存 储1 万亿亿的二进制数据，远远超过目前所有电子计算机的总储存量； ( 3 ) d n a 计算所消耗的能量只有一台电子计算机完成同样计算所消耗的能量 的十亿分之一。 d n a 计算的上述特性，即运算的高度并行性、大容量、低能耗是目前的计算 机和并行计算机所无法比拟和替代的，从这个意义上说，1 9 9 4 年由a d l e m a n 所 开创的分子生物计算技术具有划时代的意义，正因为如此，d n a 计算机成为人们 所追求的目标。 2 1 2d n a 计算研究现状 1 9 9 4 年以来，d n a 计算的高度并行性和高密度存储等优点使得越来越多的科 学家致力于这门学科的研究，她吸引了大量计算机、数学、生物分子学以及化学 研究者的目光。l o 年的时间里，s c i e n c e 、n a t u r e 等顶级杂志连续的报道了这门学 科的最新创造成果。其中有理论方面的研究，比较有代表性的研究如d n a 计算的 普遍性和通用性、算法复杂性、编码理论、误差分析等，也有应用方面的研究， 比如可满足性问题以及各种n p 问题、代数运算、逻辑运算、加密机制等“”1 。 w i n f r e e 对d n a 自装配计算的发展作出了贡献，他的关于二维d n a 格的设计和 自装配的论文。”影响了后来d n a 计算的发展方向。在他的工作基础上，d n a 计算的 问题解决更具有简单性和仿真性。后来自装配计算成为d n a 计算一个重要的研究 方面，c h e n g d e m a o 等人的论文用d n a 三螺旋分子的自装配来实现加法和逻辑异或 运算”，a s h i s hg e h a n i 和z t f l a b e a n 等人把这种方法用于加密系统，提出了一 种基于一次性密码本的d n a 加密算法。1 。日本的k e n s a k us a k a m o t o 等人提出的发 卡状计算模型解决了可满足性问题“，也是建立在d n a 自装配的基础上的。 另一个很重要性的问题是代数运算的d n a 计算方法。9 6 年g u a r n i e r i “”等人实 现了用d n a 计算来作加法。1 9 9 9 年，j o h n s o l i v e r 提出了矩阵乘法的d n a 计算模 型”“。后来又有人用动态规划方法解决了图的连通性和背包问题；符号决定 性问题“；道路染色问题“”；以及超标量计算机代数问题等等。在神经网络方 面，贝尔实验室的a p m i l l s ，j r 1 1 , y u r k e ，pm p l a t z m a n 提出了模拟神经网络模 型的d n a 计算方法o ”。 基于表面的d n a 计算是早在9 6 年就提出的一种模型，它的优越性在于具有实 现自动操作的潜力。2 0 0 0 年n a t u r e 刊载了q i n g h u al i u 的文章。“，标志着表面上 的d n a 计算正在逐步完善。 实现d n a 计算的自动化直是研究者的一个目标，在这方面，比较突出的工 作是以色列著名的可编程生物分子自动机的提出。“，模拟t u r i n g 机的装置可以自 动并行的根据输入的程序执行不同的数据处理。2 0 0 3 年，赵健等在科学通报上发 表论文”3 ，在表面上实现了可编程的分子自动机。 在应用方面，日本奥林巴斯光学工业公司于2 0 0 2 年1 月2 8 日宣布开发成功 借助d n a 之间的化学反应来分析遗传基因的生物计算机。这种计算机可用于分析 s n p ( 单核苷酸多态性) 及疾病遗传基因等。科学杂志对此作了报道，称这是 世界上第一台专用d n a 计算机。 很多d n a 计算的研究致力于n p 问题的解决，这是因为在解决n pf j 题的效率 上，计算机与分子计算差别巨大。n p 问题，就是非多项式级的问题，在传统的计 算机中，解决此类问题的时间复杂度随着题目型号的增加迅速( 成指数级) 增长。 当问题型号变大，比如说变量个数逐渐增多时，所用的时间很快的增加，使得问 题不能有效的解决。而d n a 计算只需在多项式时间就可以解决这类问题。a d l e m a n 研究组的工作已经可以解决2 0 个变量的3 - s a t 问题“。 d n a 计算解决n p 难题具有很大的优越性，科学家们建立了许多的计算模型， 已经解决了很多n p 难题。因此当我们把目光投向一个著名问题一四色问题( 不 是n p 难题) 时，我们找到了个地图四着色问题( 也是一个n p 难题”) 的具有 多项式时间复杂度的d n a 算法，再一次证明了d n a 计算解决n p 难题的高度有效 性。 1 3 地图着色问题和四色定理 地图三着色、四着色问题是和四色定理紧密相关的问题。本文中所指三着色 是指对边的着色，四着色是对点的着色。地图四色定理是一个几乎每个人都可以 理解的数学难题。它的提法也是具有迷惑性的简单：任何一个无环的平面图的顶 点可以四着色。地图四色定理最先是由一位叫古德里( f r a n c i sg u t h r i e ) 的英国 大学生提出来的。德摩尔根( 彳，d e m o r g a n ，1 8 0 6 1 8 7 1 ) 1 8 5 2 年1 0 月2 3 日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。他在信中简述了 自己证明四色定理的设想与感受。一个多世纪以来，数学家们为证明这条定理绞 尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。1 9 7 6 年美国 数学家k a p p e l 与w h a k e n 宣告借助电子计算机获得了四色定理的证明“1 ，又 为用计算机证明数学定理开拓了前景。他们用了三台i b m 计算机经过1 0 0 0 多个 小时( 约5 2 天) 的运算，证明了g u t h r i e 提出的结论是正确的。由于证明的完成借 助了计算机以及其证明的过程庞大，使得很多人对此解决方法存在怀疑。事实上， a p p e l 和h a k e n 的论文有1 0 0 多页，而其计算机程序达到4 0 0 多页，对这个证明 的验证几乎是很难的。1 9 9 6 年，n e i l r o b e r t s o n 等人在此基础上提出了一个更为 简洁的计算机解决方案“3 “，使得四色问题的解决过程变得更为清晰。 v e i l 4 第1 币绪论 r 口b e r t s o n 等人的证明过程是从研究三着色出发，这是因为研究任何一个无环可 平面地图的点的四着色是否存在的问题，可以转化成研究地图三剖分中构形自由 补全图边的三着色的问题，从而使得研究更加方便。 因此，寻找自由补全图全部三着色问题是四色问题解决中的一个重要问题。 如果能有有效的三着色算法，这可以成为四色问题的d n a 算法的突破口。 而三着色和四着色问题是相互等价的。“，对于任一张地图，若能得到一个三 着色的方案，那么可以把三着色转化成四着色。 1 4 研究内容和意义 许进等对无向图点着色问题提出了基于分子生物技术的图顶点着色问题的 d n a 算法”，算法的关键是对图中的顶点和顶点的颜色进行恰当的编码，以便于 使用常规的生物操作及生物酶完成解的产生及最终解的分离。 b a c h ( 1 9 9 6 ) “，f u ( 1 9 9 7 ) 。”对于点的三着色问题分别提出了多项式时间分 子算法；z h i q u a nf r a n kq i u “等人( 2 0 0 3 ) 提出了一种新的d n a 计算模型，并用 于顶点的三着色。这些算法有更好的时间复杂度。但是，这些算法只能找出少数 酌解，而且它们都不具很好的空间复杂度，当图的级别逐渐增大时，着色所需要 的d n a 分子链是指数级的增长。因此，如果能够降低算法的空间复杂度，将能更 加有效的对级别比较大的图进行着色。 自由补全图也是一种三剖分，构形自由补全图的三着色问题对于解决四色定 理是重要的，而且是耗机时比较大的一部分。 我们的目的就是找一种能够有效地寻找地图全部三着色的d n a 计算方法，从 而使得四色问题的解决更加迅速。在这篇论文中我们给出了脉组的思想，借助脉 组给出了寻找全部三着色的d n a 算法，同时，我们给出了对任意地图进行四着色 的d n a 算法。我们的算法具有线性增长的空间和时间复杂度。 1 5 本文的组织结构 第一章对课题的知识背景做了介绍，首先阐述了d n a 计算的原理和发展现状， 其次对地图着色问题的来源及它和四色定理的关系作了介绍。 第二章对三剖分图的着色进行了分析，从脉的思想出发，引入了脉组的概念， 证明了覆盖平滑三剖分的脉组的存在性，给出了着色算法的理论基础。 第三章各节分别详细描述了三着色算法中的编码、着色和读取结果等一系列 j 客三：些盔兰罂兰璺圭兰g 鲨苎 的操作，最后可以得出平滑三剖分的所有三着色。 第四章给出了一个平滑三剖分图顶点四着色的多项式算法。 第五章我们对算法的复杂性进行了分析，在空间复杂度上和已有的算法进行 了比较，并对算法的可行性迸行了分析。 第六章我们用计算机模拟d n a 生化反应，实现了一个可以找出任何一个地图 全部三着色的程序，并结合一个例子进行了分析。 6 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 耋三耋皇垦篓薹婆圣竺! ! ! ! ! 苎! 苎篡鼍巴! ! ! ! ! ! ! ! ! 第2 章地图的着色 2 1预备知识 令g 是一个图，矿( g ) 、e ( g ) 分别代表g 的所有点和所有边的集合，其中 y ( g ) 、e ( g ) 是有限集，任何一条边和两个顶点相连接。如( v ) 代表g 中一个点v 的度数。 如果矿( g ) 是平面上的点集，g 中每一条具有端点“、v 的边是平面上一段以 “、v 为末端的弧线，它与矿( g ) 中其它点不相交，且任何两条不同的边不可能交 于一个不是它们顶点的点，则称图g 是可平面的。平面上的图g 有一个无限区， 它的意义在于欧拉公式的应用，因为欧拉公式是用在平面或球面上的。对于一个 可平面图，其欧拉公式为p g + r 2 2 ，其中b 吼7 分别是点、边和区的个数。 在图论中，任何区是三角区的图称为一个三剖分。e 是三角区r 的三条边， 则称e 与三角区r 相关联。 设g 是一个三剖分，令中：( g ) 一1 ，0 ，1 ) 是一个映射，e ，f ，g 分别与三 角区相关联，若徊( p ) ，西( ) ，( g ) = 一1 ，0 ，1 l ，则称，被三着色。若g 的任何一个 三角区都被三着色，则称这个三剖分被三着色。m 称为g 的一个三着色。 令k ：矿( g ) 斗 1 ，2 ，3 ，4 ) 是另一个映射。对于g 的任何一条边，如果它与点 “，。相关联，有七( “) 七( v ) ，则我们称g 被四着色。幻尔为g 的一个四着色。 对于每个地图，我们可以把每一个区( 区域或国家) 看作一个点，而区与 区之间的邻接关系看作点与点之间的连线，因此得到一个点线图。这不是一个三 剖分。但是通过适当加一些边它可以成为一个三剖分。很明显，如果加边以后的 - - - * 0 分有一个三着色，那么它可以很容易的转化成原图的三着色。因此，我们可 以通过找出加边后的三剖分三着色的方法来找出原图的三着色。 2 2 自由补全图的三着色 自由补全图的三着色是四色问题证明中的重要问题，我们这里证明了自由补 全图是平滑三剖分，因此以上的三着色算法可以直接用于自由补全图。 定义1 m 1 近三剖分三剖分加上它外面的无限区部分叫做近三剖分。 定义2 0 6 1 构形 一个构形k 由一个近三剖分g ( k ) 和一个映射，i ：矿( g ( k ) ) z + 构成，而 且t t 具有以下性质： ( 1 ) v 点v ，g 暇) ”至多有两部分，若有两部分，y t ( ”) 2 如( ”) + 2 1 2 ) v 点v ，若v 与无限区不相关联，则y r ( v ) 2 如( v j 。否则y x ( 。) 如v ) 。 两种情况下都有y x ( v ) 5 。 ( 3 ) k 有环型2 ，环型定义如下：塑x v ) 一d c 一n ，其中 f = v i v 与舒5 勺无限区相关联，且g ( 足) v 是连通的 一 定义3 m 1 自由补全图 令x 是构形，s 是近三剖分。如果满足： ( 1 ) r 是s 的边界回路，且与s 的无限区相关联。 ( 2 ) g ( k ) 是s 的一个导出子图，g ( k ) = s y ) ，任何g ( k ) 的有限区是 s 的有限区，g ( k ) 的无限区包含尺和s 的无限区。 1 3 ) 任何在s 中不在y ( r ) 中的点v 在s 中的度数为y x ( 。 则称s 是构形k 的关于环r 的自由补全图。 k 、s 、r 如上所述。问题是要找出s 的所有三着色。若用穷举法，则对n 个点的s ，要从3 ”种列举中找出正确的着色。若n = 2 5 ，则有1 4 3 4 7 9 0 7 种列举。 构型的自由补全图边数般在2 0 以上，因此这个计算量是庞大的。 定义4 平滑三剖分：若h 中每一个三角区至少与另外两个三角区相关联，则称 这样的三剖分为平滑三剖分。 一般的，一个三剂分可以拆成若干个平滑三剖分和一些非平滑三剖分，这些 非平滑三剖分为单个或者几个三角区组成的三剖分图，它们的着色是容易的。因 此只要给出了平滑三剖分的一个三着色算法，就可以容易的给出任何一个三剖分 的三着色。因此以下的算法只讨论平滑三剖分的三着色。 定理l 自由补全图s 是一个平滑三剖分。 证明：当五变成s 时，五的边界上的每一个点最多新增3 条边，这三条边至少围 城两个区。否则有一个k 中的顶点和无限区相关联，与自由补全图定义第( 2 ) 条矛盾。 矗 第2 章地图的着色 因此，如果这三条边中有一条与无限区相关联，则相邻两个顶点新增的边中 要有两条边不相交，则至少有两个点连不上，因此也会有一个k 中的顶点和无限 区相关联，也与自由补全图定义第( 2 ) 条矛盾。也就是说，如果s 中有这样的 脉：它的第一个区有两条边与s 的无限区相关联，则与上面的结论矛盾。因此 s 是一个平滑三剖分。 由于自由补全图是平滑三剖分的一种，因此以下我们只考虑平滑三剖分的三 着色问题就可以了。 2 3 三着色的脉及其性质 脉的思想来源很久，最初是由肯普在1 8 7 9 年在试图解决四色问题时提出的 “肯普链”的思想，n e l lr o b e r t s o n 等人将其发展并用于四色问题中构形可约性 的证明。我从脉出发，进一步提出脉组的概念，并证明了覆盖平滑三剖分月所 有区的脉组必然存在的定理。这一证明是后一部分着色算法的基础。 定义5 脉”：设月是一个平滑三剖分，k 是它的一个三着色，脉定义为日中 的一个序列g o ，g l ，r 2 ，g t ，它满足下列条件： 1 ) g o ，g ”r ，gr 是最的不同的边 2 ) _ ，_ ，r ，是月的不同的区 3 ) g o ，g t 是月的边界上的边： 4 ) 0 r j s s q a ( e 口) 3 】 ( 2 ) 对第7 个区，若它除了与第f 个和第k 个区共用一条边，还与另一个区相 关联，比如说r t ，则此区的编码有以下1 2 种( 同样的，考虑颜色的交替，每一 个区也是用2 4 条链来编码) 。 研茹趸万功k p 3 中( e 止) 5 】可窝瓦；劢k b 【5 中( ) 3 】 s 【5 0 ( 3 ) 】讲o b f 五砑s 【3 ( 5 ) 】d h b 胃i 硼s l 5 0 ( e f 3 ) j d h p p o ( e 一) 5 js p ( 5 ) j d h p l 5 m ( e 且) 3 j 可菇碲k p 【3 ( ) 5 】可丽疆i 珈k p 5 中。业) 3 】 s 5 中( 勺3 ) 】d hj 5 1 圉瓦；习s 3 西( 白5 ) m p 每五菇羽 可葡冠i 珈k p 【3 ( ) 5 可习瓦i 珈k p 5 m ( 勺) 3 s 【5 。( 勺3 ) p b b 臣蔽苫稠s 【3 。( 勖5 ) 】d b b 胃砑 两个粘头如果能够发生w a t s o n c r i c k 互补反应，它们需要符合以下条件： 1 编码了相同的边。 2 编码了同一种着色。 3 一个粘头是3 端到1 5 端的边，另一个是5 端到3 端的此边的补； 或者一个粘头是5 端到3 端的边，另一个是3 端到5 端的此边的补。 我们可以设计好足够多的分子链，存放在分子库中，这样在任给一个新的地 图时，根据输入边可以自动生成所有的编码链，我们只需记录编码的信息即可。 3 2 生成脉的算法 1 退火。 将编好的每个区的d n a 链全部倒入1 个试管中，我们使溶液逐渐冷却，互补 的两条链通过氢键结合在一起( 冷却过程必须慢慢进行，使得相应的互补基有足 够的时间发现对方) 。这过程称为复性( r e n a t u r a t i o n ) ，也称退火。退火使得所 有的链进行自装配，从而生成所有可能的脉。 2 加入链接酶，使脉产生链接( 1 i g a t i o n ) 反应。 虽然上步氢键使两个互补的粘性末端结合在一起，但每个串上都有一个称 is 为缺口的缝隙。缺口是由于相邻的核昔酸之问没有磷酸二酯键，但是它可以通过 加入链接酶来创建，从而生成完整的双链，如图3 3 所示。 n 骘下下7 一 _ l ct t6| 图3 - 2 链接反应原理图 f i g u r e 3 2t h em e c h a n i s mo fl i g a t i o n 此时，试管中是那些终止于平滑三剖分边界中的边的脉，即两端是都是边界 中的边的脉的全体。这时的脉已经打好了着色的基础。适当升温使不是双链的分 子解成单链。然后，加入外切酶，把不是完整双链的分子剪切成游离的碱基。 图3 - 3 一个简单的= 刮分 f i g u r e 3 - 3as i m p l et r i a n g u l a t i o n 下面以图3 - 2 为例来看一下此步生成的分子的形状： ( 1 ) d 睁( e 。) = 1 1 d k 】d 陋( e 啦) = 一l j d k 】d 卜( 巳。) = l j d k 】d 陋( 岛) = 一1 ( 2 ) d 睁眩) = 一l 】d ，1 】d p ( q ，) = 1 d k 】d p ( 色，) = 一1 d h 】d 陋( e 3 ) = 1 】 ( 3 ) d 脚( 白) = 1 】d k 】d 睁( e ) = 一1 】d k 】d p ( 岛。) = l 】d k 】d 睁( 。) = 一1 ( 4 ) d 陋( q ) = 一l i d r 4 d m ( e 4 。，) = 1 】d k 】d p ( e 耶) = 一1 】d k 】d 陋( 气) = 1 】 ( 5 ) d 睁( q ) = 一1 】d k 】d 陋( e ) = 咖 r 4 d 印( e 。) = 一1 】 ( 6 ) d 陋( e 。) = 1 】d k 】d b ( e l 4 ) = 一1 d k d c p ( e ) = 1 】 。d 洳( 岛) = 一l i d h p p ( e ：，) = 1 j d k 】d p ( e ：，；) = 一1 j d k 】d 舾( 巳。) = 1 1 一 ”7 一d h 】d 陋( ) ；一1 d 舾( 岛) = 1 d k 】d 睁( 巳，) = 一l j d k p p ( e ：，) = l j d k p p ( 巳。) = 一1 卜 ”7 一d k 】d p ( ) = 1 。d 睁( e 。) = 1 d k d p ( e 啦) = 一1 j d k d 扣( 岛j ) = l j d h d 西( e 3 。) l j q d k d p ( e 。，) = l 】d 【r 5 】d 睁( 气，。) = 一1 】d 【，6 】d 脚( 气) = 1 】 1 6 第3 章地图三着乜的d n a 算法 ，。、d 陋( q ) = 一1 p k d 陋( e l , 2 ) = 1 p k 】d p ( e 2 , 3 ) = 一1 d k 】d p ( e 3 , 4 ) = 1 卜 uw d r 4 d q ) ( e s ) = 一1 】d k l d b ( e ，。) = 1 】d k 】d p ( e 。) = 一l 】 在编码了上图的分子生成的脉r _ | 至少有以上1 0 条，我们看到结果中生成的 脉有两种情形：一种是两端着色相同的脉，一种是两端着色不同的脉。事实上当 一条脉中有奇数个区时，两端边的着色不同，而一条脉中有偶数个区时，两端边 的着色是相同的。 3 升温变性，把上步结果的双链解为单链。 因为两个互补基之问的氢键比同一串内的磷酸二酯键要弱得多，这就使得在 不破坏单条链的前提下分离两条链成为可能。我们加热上一步结果中的d n a 双链 溶液直至1 ) n a 溶解，即d n a 双链分离为单链。溶解温度为8 5 一9 5 。 此步结束后溶液中双链解链为互补的单链如下面两个分子： 珂面再司难同而习i 面啊环繇j j 环雨陌弼5 ； 5 s 【o ( e ，) = 1 p h p 睁( 巳：) = 一1 p k p p ( e 2 , 3 ) = 1 p 沁p 【( 白) = 一1 】3 。 3 3 脉组的提取算法 对上一步生成脉的单链形式的试管进行如下操作，可以生成代表了着色信息 的脉组。 1 亲和纯化对单链分子的提取 提取出末端具有编码可菇砑可燹砑爱氍砑，可菇砑的所有 单链，而不是含有它们的补的单链。其中m 为平滑三剖分边界回路上边的个数。 将编码了羔竖! 鱼2 墨兰堕! 【垒2 蓼璺堕竺! 刍2 丑，兰堡竺生! ! 翌( 印8 ：，e 3 ，的 互补分子，称为引物) 的单链分子附着在细小的磁珠上，将其放入上一步反应后 的溶液中，摇动混合液，目标分子就附着在磁珠上，这个过程称为亲和纯化。引 物的种类数应该为m 个。 2 退火反应连接单链 在步骤l 中的结果试管中加入所有这样的单链：s 【3 中( e ) 5 p 【3 m ( s ，) 5 】； s 5 。( e ，) 3 p 【5 巾( 勺) 3 】l _ i c j 开 环双链d n a “”。当凝胶浓度很高时，凝胶孔径变小时，环状d n a ( 球形) 不能进 入凝胶中，相对迁移率为o ，而同等大小的直线d n a ( 刚性棒状) 可以按长轴方 向前移，相对迁移率大于0 。因此我们用较高浓度的低熔点琼脂糖凝胶来做实验， 从而使得未成环状的d n a 分子可以进入凝胶，而环状分子不能进入。这样就把同 有相同区的脉组去除掉了。 9 对脉组的回收 低熔点琼脂糖熔点为6 2 6 5 c ，溶解后在3 7 c 下维持液体状态约数小时， 可完成样品的回收。 如果还有链留下，则说明了有着好色的脉组留下，否则便没有。结果便是通 过，屹，0 且仅通过r l , r 2 ，这”个区的所有的脉组的集合。事实上，因为每 一个三剖分必然有三着色和四着色惜1 ，所以最后我们肯定可以得到盛满了“解” 的试管。 3 4 三着色的读取 1 _ 着色信息在d n a 芯片上的存储 ( 1 ) 探针的制备 将所有的边的着色的补链作成探针，每一条边有1 ，一l 两种探针相对应。若 有可条边则有2 9 种探针，即芯片大小为2 q 。对应于探针，我们把脉组称为靶分子。 若此边在三剖分内部，则每一个边的编码为 1 9 _ ! ! ! ! ! 蔓! ! ! ! ! ! ! ! ! ! 些垄圣呈竖垒差呈茎茎呈堇垒望垒圣! ! ! 竺! 鼍曼! ! ! ! ! ! ! ! ! 一 s p ( e “) = 1 】或者s 睁( q ，) = 一1 ； 若此边在三剖分的边界上，则每一个边的编码为 s p ( 口，) = 1 或者s p ( q ) = 一1 。 ( 2 ) 荧光素标记编码链 前面提到，靶分子中每一条边的着色需要进行标记。用两种不同的荧光素标 记靶分子和探针，这两种荧光素其中一种所发荧光恰好是另一种的激发光“。其 中一种标记于靶分子上每一条边的3 端，一种标记于探针的5 端。当靶分子没有 分子段与探针互补时，一种产生的荧光不能够激发另一种的荧光，但是当靶分子 某一分子段与探针结合成双链后，则可以激发出另一种荧光。 ( 3 ) 芯片的设计 我们对探针序列在芯片上的分布进行约定，我们把编码了着色为1 和一1 的同 一条边的探针平行排列，排列的顺序由计算机做记录。其他的依次在芯片上排开。 将所有的探针进行有序的点样，从而制成d n a 芯片，如图3 4 左图所示 图3 - 4 杂交反应前后的d n a 芯片 f i g u r e 3 4t h ed n ac h i pb e f o r ea n da f t e rh y b r i d i z a t i o “ 2 d n a 芯片上的杂交反应 ( 1 ) 从盛满了脉组的溶液中捞出任意一条靶分子，然后对它进行p c r 扩增， 从而放大i 0 0 万倍以上，使得靶分子个数足够多。 ( 2 ) 将d n a 芯片放入靶分子所在的溶液中，进行杂交反应。如果靶分子上某 一个边的着色和探针的着色相同，则靶分子就被粘到了这个探针上，则荧光被激 活。如果脉组中没有这个边，则探针粘不上靶分子，荧光不会被激活，如图3 4 右图所示。如果靶分子太长，可以考虑短后进行反应。 ( 3 ) 一旦荧光标记的靶分子和d n a 芯片上的探针反应后，未结合的成分就可 洗去，结合到芯片的样品可通过荧光检测装置一聚焦扫描仪来进行检测。经过芯 片扫描仪扫描后，再经模式识别软件，就可以把每一个边( 边对应芯片上的位置) 对应的着色记录到计算机上。 如例( 图3 2 ) 的脉中2 、3 两个脉连成的脉组为： d p ( e 。) = 一1 1 d h d 睁( 巳：) = l l d r d d 西( 。：，) = 一1 】d k l d p ( 岛) = 1 卜 一d p ( e 。) = l m _ 】d 卜( e 。，) = 一1 】d k d 扣( e ，。) ；1 】d 【，6 】d 【中( e 。) = - 1 】 这个脉组所蕴含的着色如图3 - 5 所示，图3 5 左表中前八条边着色为l ，一1 中的，最后三条边在脉组中没有出现，所以为0 。 边着色边着色 e 1 1 e l2 1 e 3 1 e 2 3 1 e d 1 e 4 5 1 e 6 1 e f f i 1 e 3 t l 0 e 2 5 0 e 1 4 0 图3 - 5 三着色的读取 3 5 本章小结 本章给出了一个对平滑三剖分三着色的d n a 算法，详细介绍了如何将图的结 构用d n a 分子编码出来，及算法的具体步骤和结果的读取方案，并以一个实例演 示了编码如何转化成图的着色。 第4 章地图四着色的d n a 算法 第4 章地图四着色的d n a 算法 4 。1 编码方法 在证明四色定理的过程中，用到的是边的三着色代替点的四着色来完成证 明，这种代替的理论依据是： 定理1 一个三剖分是四着色的等价于它是三着色的。 定理的含义有两层：给定一个三剖分的边的三着色，可以找到它的四着色； 同样的，给定一个三剖分的点的四着色，我们可以找到它的三着色。例如，对三 剖分任意一条边e ，如果它有两个顶点“，v ，可以建立如下对应方式。”： 辑( “) ，露( v ) 】= l ，2 ) 或者 3 ，4 ) 伽q l 膏( v ) ) = 1 ，3 ) 或者 2 ，4 许( “) ，七( ) = 1 ，4 ) 或者 2 ，3 ) 这启发我们得到一种平滑三剖分四着色方案。我们在三着色方案里区的编码 中编入点的着色，则按照找出三着色的实验步骤我们就可以给出点的四着色。 编码方式与三着色的编码基本上相同，采用双粘头( 除了边界上的区用到单 粘头) 的链。但是这里的短个代表边的编码链两端各增加一个功能段用来编码顶 点及其着色。编码时的规则如下： 1 每条边两端的点的编码不同的着色。 2 同一个区不同的点着色不同。 3 点的着色和边的着色的对应方式如上所示 编码例：可甄丽j 五匿了i 神k p 5 i ( v ：) 中( e ：，) 七( v ，) 3 】 习j 叹瓦了甄互了i i j 习d 以p p “v 2 ) m 0 ：，) j i ( v 9 ) 5 】 s 3 k ( v ：) ( 白) _ j ( 匕) 5 】d 【_ 研丽西丽i 汪丽习 s s k ( v ：p ( e ，) 七( v ，) 3 】嗽研顽可瓦西i 两习。 事实上，对一个区，从 l ，2 ，3 ，4 中选出三种颜色对三个顶点进行着色， 共有日种可能的选择方式，因此一个区的编码代表了2