（運籌學與控制論專業(yè)論文）構(gòu)形可約性證明的dna算法.pdf

捅要 摘要 d n a 計算是一門新興的研究領(lǐng)域。1 9 9 4 年，a d l e m a n 在著名雜志s c i e n c e 上 發(fā)表第一篇關(guān)于d n a 計算的文章，他用d n a 在試管中解決了著名的哈密爾頓 路徑問題。d n a 計算具有大規(guī)模并行計算的能力，而且與傳統(tǒng)的電子計算機相 比能存儲更多的數(shù)據(jù)。目前d n a 計算的研究已涉及許多領(lǐng)域，包括生物學、數(shù) 學、物理、化學、計算機科學和自動化工程等多領(lǐng)域，包括生物學、數(shù)學、物理、 化學、計算機科學和自動化工程等具體應用，是計算概念上的一次革命。 四色問題在1 8 5 2 年首次提出。是一個可與費馬猜想相媲美的難題，直到1 9 7 6 年才由哈肯和阿佩爾給出了第一個證明，隨后r o b e r t s o n 等人對他們的方法進行 了改進。首先，他們給出了一個不可避免集，證明每個三剖分都至少包含不可避 免集中的一個構(gòu)形。第二步，他們證明每個構(gòu)形都是可約的，這一部分的證明需 要借助于計算機實現(xiàn)，完成第二步的證明大概需要1 2 0 0 個小時! 本文探討用d n a 計算的方法來解決構(gòu)形的可約性證明，因為d n a 計算具有大規(guī)模并行計算的能 力，能夠大大地減少證明所需的時間。目前還沒有這方面的研究。 本文首先簡述了四色定理證明的證明，然后介紹了平滑三剖分三著色的一些 性質(zhì)和三著色的d n a 算法，在本文的最后分析了著色和符號匹配體的關(guān)系，給 出了構(gòu)形可約性的d n a 算法。本文的編碼方式十分直觀、有規(guī)律，算法簡單易 于實現(xiàn)。算法具有一定的并行性，能夠大大地減少構(gòu)形可約性證明的時間。 關(guān)鍵詞：d n a 計算；四色問題；可約性；構(gòu)形 北京工業(yè)大學理學碩士學位論文 a b s t r a c t d n a c o m p u t i n gi sa ne m e r g i n gn e ws t u d ya r e a i n1 9 9 4 ，a d l e m a nd e s c r i b e d h i s p i o n e e r i n gr e s e a r c ho nd n ac o m p u t i n gi ns c i e n c e ，w h e r eh ec o m p u t e da ni n s t a n c eo f t h eh a m i l t o n i a np a t hp r o b l e mw i t hd n ai nt e s tt u b e s t h i si st h ef i r s te x p e r i m e n t a l r e p o r to nd n ac o m p u t i n gs t u d y t h em a i nf e a t u r e so f d n a c o m p u t i n ga r em a s s i v e l y p a r a l l e lc o m p u t i n ga b i l i t ya n dp o t e n t i a le n o r m o u sd a t as t o r a g ec a p a c i t yc o m p a r i n g w i t h c o n v e n t i o n a le l e c t r o n i cc o m p u t e r s ，d n am o l e c u l e sp r o v i d ec o n c e p t u a l l ya r e v o l u t i o ni nc o m p u t i n g ，a n dm o r ea n dm o r ei m p l i c a t i o n sh a v eb e e nf o u n di nv a r i o u s d i s c i p l i n e s t h ef o u r - c o l o rp r o b l e mw a sf i r s tf o r m u l a t e di n18 5 2a n dw a sn o tp r o v e nu n t i l 1 9 7 6 a l o n gw i 也o t h e rp r o b l e m ss u c ha sf e r m a t sl a s tt h e o r e m t h i sc o n j e c t u r ew a s c o n s i d e r e do n eo ft h eg r e a to p e np r o b l e m si nm a t h e m a t i c s i n19 7 6 ，h a k e na n da p p e l g a v et h ef i r s tp r o o f , w h i c hl a t e rw a si m p r o v e db yr o b e r t s o n f i r s t ，t h e ys h o we v e r y p l a n a rt r i a n g u l a t i o nc o n t a i n s o n eo ft h ec o n f i g u r a t i o n si nt h e i ru n a v o i d a b l es e t s e c o n d ，t h e ys h o wt h a te a c hc o n f i g u r a t i o ni sr e d u c i b l e t h es e c o n ds t e pi st h ep a r to f t h ep r o o ft h a tr e q u i r e st h ea i do fac o m p u t e na p p r o x i m a t e l y1 2 0 0h o u r so fc p ut i m e w e r er e q u i r e dt oc o m p l e t et h es e c o n ds t e po ft h ep r o o f i nt h i sp a p e r , w et r yt os o l v e t h ep r o o fo fc o n f i g u r a t i o nr e d u c i b i l i t yu s i n gd n ac o m p u t i n g b e c a u s eo ft h e m a s s i v e l yp a r a l l e lc o m p u t i n ga b i l i t yo fd n ac o m p u t i n g ，w ec a ns h o r t e nt h et i m eo f t h ep r o o f g r e a t l y t h e r ei sn os u c hr e s e a r c hu pt on o w f i r s t ，w ei n t r o d u c et h ep r o o f o f f o u r - c o l o rt h e o r e mi nb r i e f s e c o n d ，w ei n t r o d u c e t h ep r o p e r t yo ft r i c o l o r i n gt os m o o t ht r i a n g u l a t i o na n dt h ed n aa l g o r i t h mo f t r i c o l o r i n g f i n a l l y , w ea n a l y z et h er e l a t i o n s h i pb e t w e e nt h ec o l o r i n ga n dt h es i g n e d m a t c h i n g ，a n dt h e np r o v i d et h ed n aa l g o r i t h mt ot h ep r o o fo fc o n f i g u r a t i o n r e d u c i b i l i t y 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 ；t h ea l g o r i t h mi se a s yt o c a r r yo u t t h ea l g o r i t h mi sp a r a l l e lt os o m ee x t e n t ，a n di tc a ns h o r t e nt h et i m et o p r o v et h ec o n f i g u r a t i o nr e d u c i b i l i t yg r e a t l y k e yw o r d s ：d n ac o m p u t i n g ；f o u r - c o l o rp r o b l e m ；r e d u c i b i l i t y ；c o n f i g u r a t i o n i i 獨創(chuàng)性聲明 本人聲明所呈交的論文是我個人在導師指導下進行的研究工作及取得的研 究成果。盡我所知，除了文中特別加以標注和致謝的地方外，論文中不包含其他 人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得北京工業(yè)大學或其它教育機構(gòu) 的學位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均 已在論文中作了明確的說明并表示了謝意。 簽名：章魚l 日期： 關(guān)于論文使用授權(quán)的說明 塑豎9 本人完全了解北京工業(yè)大學有關(guān)保留、使用學位論文的規(guī)定，即：學校有權(quán) 保留送交論文的復印件，允許論文被查閱和借閱；學?？梢怨颊撐牡娜炕虿?分內(nèi)容，可以采用影印、縮印或其他復制手段保存論文。 ( 保密的論文在解密后應遵守此規(guī)定) 簽名：軸牝翩簽絲隰鯊鉚 第l 章緒論 1 1d n a 計算概述 第1 章緒論 計算機科學家把計算問題分為三類：容易求解的，困難的和不可求解的。電 子計算機在人類社會起到了巨大的促進作用，但由于電子計算機的存貯量小，運 算速度慢，智能化低，而且在圖靈機上求解計算困難問題所需的時間往往隨問題 規(guī)模呈指數(shù)增長，這導致人們迫切希望尋找一種能克服上述缺點的新型計算機。 1 9 9 4 年，l m a d l e m a n 在著名雜志s c i e n c e 上首先發(fā)表開創(chuàng)性論文“m o l e c u l a r c o m p u t a t i o no f s o l u t i o n st oc o m b i n a t o r i a lp r o b l e m s ”。，提出了d n a 計算的概念， 并成功地解決了著名的h a m i l t o n 路徑問題，指出了d n a 計算潛在的巨大并行性 及待研究的問題。1 9 9 5 年，l i p t o n 也在s c i e n c e 雜志上發(fā)表論文。3 ，進一步論證 了d n a 計算可解決完全性問題。自此，d n a 計算引起了國際上許多學者的關(guān)注 與興趣，并掀起了d n a 計算的研究熱潮，成為一個引人注目的研究方向。 d n a 計算的并行性使得我們可以用d n a 分子在線性增長的時間內(nèi)解決n p 一 完全等計算困難問題，d n a 計算開創(chuàng)了一個非標準計算研究的新領(lǐng)域，它使人 們對計算的本質(zhì)產(chǎn)生了新的理解和認識。 d n a 是在d n a 計算中起中心作用的分子，是重要的基因物質(zhì)，它攜帶著生 物的遺傳信息“1 ，d n a 的基本元素是核苷酸。由于化學結(jié)構(gòu)的不同，核苷酸劃 分為4 類堿基：腺嘌呤( a ) 、鳥嘌呤( g ) 、胞嘧啶( c ) 和胸腺嘧啶( t ) 。d n a 由兩條核苷酸鍵組成，這兩條極長的核苷酸利用堿基之間的氫鍵而結(jié)合在一起 形成一條雙股的螺旋結(jié)構(gòu)，且一股中的堿基序列與另一股中的堿基序列互補a 和t 配對，c 和g 配對堿基的上述配對關(guān)系稱為w a t s o n - c r i c k ( w c ) 配對。遺傳 信息以a 、t 、c 、g 在核苷酸中的排列順序而體現(xiàn)，其排列序列的多樣性構(gòu)成 了豐富的遺傳信息。 d n a 計算解決問題的基本思想是：利用d n a 特殊的雙螺旋結(jié)構(gòu)和堿基互 補配對原則對問題進行編碼，把要運算的對象映射成d n a 分子鏈，在d n a 溶 液的試管里，在生物酶的作用下，生成各種數(shù)據(jù)庫，然后按照一定的規(guī)則將原 始問題的數(shù)據(jù)運算高度并行地映射成d n a 分子鏈的可控的生化過程。最后，利 北京工業(yè)大學理學碩士學位論文 用分子生物技術(shù)如聚合酶鏈反應p c r 、聚合重疊放大技術(shù)、克隆、誘變、電泳、 磁珠分離等，破獲運算結(jié)果。 從d n a 的原理來看，它與數(shù)學操作非常類似。單股d n a 可看作由4 個不同 符號a 、g 、c 、t 組成的串，就像電子計算機中編碼0 和“1 ”一樣，可 表示成四個字母的集合= a ，g ，c ，t ) 來譯碼信息。d n a 串可作為譯碼信息， 在d n a 序列上可執(zhí)行一些簡單操作。這些操作是通過大量能處理一些基本任務(wù) 的酶來完成的。也就是說，酶可看作模擬在d n a 序列上簡單的計算。不同的酶 用于不同的算子“1 。如限制內(nèi)核酸酶可作為分離算子，能夠識別特定的d n a 短 序列即限制位，任何一個在其序列中包含限制位的雙鏈d n a 在限制位被酶切 斷。d n a 結(jié)合酶可作為綁結(jié)算子，將一條d n a 鏈的末端連接到另外一條d n a 鏈。d n a 聚合酶具有可作為復制算子復制d n a 等功能。復制反應需要一個單 鏈的向?qū) n a 即模板d n a ，和一個稍短的被稱為引物的寡聚核苷酸且與模板 相連。在這些條件下，d n a 聚合酶對d n a 的合成有催化作用，通過在引物的 末端連續(xù)不斷的添加核菅酸來實現(xiàn)。外核酸酶可作為刪除算子等“3 。 如果說過去所指的計算機是指物理芯片計算機，那么d n a 計算機則是化學 反應計算機。& 口d n a 計算在本質(zhì)上屬于生化反應，為了利用d n a 分子完成給 定的任務(wù)，我們必須借助對d n a 分子的各種操作技術(shù)。1 9 5 3 年w a s t o n 和c r i c k 發(fā)現(xiàn)d n a 之后，人們發(fā)現(xiàn)許多操作d n a 的方法。如剪切、粘貼、電泳、聚合鏈 反應、加熱、退火等。這些操作d n a 的方法有助于人們解決內(nèi)存及信息的輸入和 接收。 經(jīng)常用到的操作有以下幾種“”： ( 1 ) 合成：使游離的堿基形成寡核苷酸的過程。 ( 2 ) 混合：把兩個試管中的溶液混合。 ( 3 ) 鏈接：兩條帶有粘頭( 也就是沒有完全配對的雙鏈) 的d n a 雙鏈在連接 酶的作用下，按w a s t o n c r i c k 互補配對原則且將縫隙修補好，從而連接在一起的 過程。 ( 4 ) 剪切：利用特定的限制性內(nèi)切酶，在d n a 雙鏈的某個位置切斷形成帶 有粘頭的兩條鏈的過程。 ( 5 ) 退火和溶解：這是兩個完全相反的過程，退火是指兩條互補的d n a 單 第1 章緒論 鏈在溫度逐漸降低的條件下，合成一條雙鏈的過程；溶解是一條d n a 雙鏈在溫 度升高時，分解為兩條互補的單鏈的過程。 ( 6 ) 放大：利用p c r 技術(shù)，游離的堿基與作為模板的鏈配對連接形成雙鏈， 然后解成單鏈，繼續(xù)這樣的過程，于是目標鏈會以2 的指數(shù)級增長。 ( 7 ) 提?。簩⒑刑囟╠ n a 短鏈的分子提出來，這要通過將特定短鏈的互 補鏈吸附在小磁珠上，然后用磁鐵將小磁珠吸出來的過程。 ( 8 ) 延長：這一過程需要一條已知單鏈模板和一條已存在的、并已與模板的 - - 4 段匹配的引物d n a 序列，要延長的d n a 序列根據(jù)模板給出的序列結(jié)構(gòu)， 在聚合酶的作用下由5 端到3 端的方向不斷延伸。 ( 9 ) 縮短：通過外切核酸酶從d n a 分子的末端去掉一個核苷酸而縮短d n a 分子。 ( 1 0 ) 分離：將d n a 分子置于一有凝膠的電場中，由于d n a 分子帶負電， 在電場中會向正極移動，長度大的分子鏈受到凝膠的阻力大，移動速度慢，因此 可用此技術(shù)去獲取一定長度的d n a 分子鏈，也可區(qū)分不同長度的d n a 分子。 d n a 計算就是利用這些基本的生物操作的組合來實現(xiàn)的。這些操作的組合 形成多種d n a 計算的數(shù)學模型，主要是：粘接系統(tǒng)，剪接系統(tǒng)，插入一刪除系 統(tǒng)這三種。 d n a 計算之所以具有吸引力，是因為它具有以下優(yōu)點： ( 1 ) d n a 分子生物算法具有高度的并行性，因而其運算速度很快。在 a d l e m a n 的實驗中，通過適當估計，d n a 串的并行操作數(shù)目可達木1 0 ”，許多 研究者認為，用當前技術(shù)使d n a 計算達到1 0 ”1 0 2 0 個串的并行操作是可行的 相比之下，目前最快的巨型計算機每秒僅能執(zhí)行l(wèi) o ”個操作雖然d n a 計算每個 操作本身與電子實現(xiàn)相比非常緩慢，但d n a 反應的巨大并行性足以補償d n a 鏈的大規(guī)模并行性可以同時攻擊一個計算問題的不同部分，從而可以攻破諸如 數(shù)據(jù)加密標準d e s 這種最艱難的組合問題。 ( 2 ) d n a 作為信息的載體其貯存的容量非常之大，d n a 溶液可存儲1 萬億 億的二進制數(shù)據(jù)，遠遠超過目前所有電子計算機的總儲存量。 ( 3 ) d n a 分子生物計算所消耗的能量只有一臺電子計算機完成同樣計算所 北京工業(yè)大學理學碩士學位論文 消耗的能量的十億分之一，甚至能自己提供燃料從而實現(xiàn)自供能。 d n a 計算的上述特性，即運算的高度并行性、大容量、低能耗是目前的計 算機和并行計算機所無法比擬和替代的，而a d l e m a n 的實驗表明，生物分子計 算從理論變成了現(xiàn)實，這在d n a 計算的歷史上具有里程碑的意義。正因為如此， d n a 計算機成為人們所追求的目標。 目前的d n a 計算有幾種主要的形式： ( 1 ) 試管d n a 計算機：這是目前大部分d n a 計算機的工作形式。其技術(shù)核 心是進行并行反應的分子游離在液體中。反應物、中間產(chǎn)物和輸出分子都混雜 在一起。需要有專門的步驟把輸出產(chǎn)物分離出來，分離方法有瓊脂糖電泳、毛 細管電泳、高壓液相、液質(zhì)聯(lián)用質(zhì)譜等。 ( 2 ) 表面計算“”：w i s c o n s i n 大學的研究人員把d n a 計算所有可能的結(jié)果附 著在固體表面上，然后通過系列的雜交和酶切來得到最后的答案。與試管相比， 表面計算、芯片技術(shù)、微型化技術(shù)以及納米技術(shù)等技術(shù)的綜合可能是d n a 計算 實用化的必經(jīng)之路。 ( 3 ) 雜合計算機：這種雜合計算機實際上是電子計算機與具有高度并行能力 的d n a 計算單元結(jié)合而成。我們認為這是比較可行的第一代實用型d n a 計算 機。s u y a m aa t l 6 提出了雜合計算機的概念，電子計算機的功能是控制單元，在 電子計算機與d n a 計算單元中間有自動化的d n a 分子加工部。 ( 4 ) 生物膜系統(tǒng)：即所謂的p 系統(tǒng)“，尚處于理論探討階段。 ( 5 ) 細胞式計算機：尚處于理論探討階段。即使單細胞生物也在執(zhí)行著復雜 而有序的分子計算過程。高等細胞在基因表達過程中的剪接以及并行處理過程， 與電子計算機中的數(shù)據(jù)化過程是相同的“”。 1 。2d n a 計算研究現(xiàn)狀 i 9 9 4 年以來，d n a 計算的高度并行性和高密度存儲等優(yōu)點使得越來越多的 科學家致力于這門學科的研究，她吸引了大量計算機、數(shù)學、生物分子學以及化 學研究者的目光。1 0 年的時間里，s c i e n c e 、n a t u r e 等頂級雜志連續(xù)的報道了這門 學科的最新創(chuàng)造成果。其中有理論方面的研究，比較有代表性的研究如d n a 計 算的通用性“、計算模型和算法、時空復雜性、有效性及容錯性模型，也有應用 第1 蘋緒論 方面的研究，比如可滿足性問題以及各種n p 問題、代數(shù)運算、邏輯運算、加密 機制等。 w i n f r e e 對d n a 自裝配計算的發(fā)展作出了貢獻，他的關(guān)于二維d n a 格的設(shè) 計和自裝配的論文影響了后來d n a 計算的發(fā)展方向。在他的工作基礎(chǔ)上，d n a 計算的問題解決更具有簡單性和仿真性。后來自裝配計算成為d n a 計算一個重 要的研究方面，c h e n g d em a o 等人的論文用d n a 三螺旋分子的自裝配來實現(xiàn)加 法和邏輯異或運算，a s h i s hg e h a n i 和t h l a b e a n 等人把這種方法用于加密系統(tǒng)， 提出了種基于一次性密碼本的d n a 加密算法。日本的k e n s a k us a k a m o t o 等人 提出的發(fā)卡狀計算模型解決了可滿足性問題，也是建立在d n a 自裝配的基礎(chǔ)上 的。 另一個很重要性的問題是代數(shù)運算的d n a 計算方法。9 6 年g u a m i e r 等人實 現(xiàn)了用d n a 計算來作加法。1 9 9 9 年，j o h n s o l i v e r 提出了矩陣乘法的d n a 計算 模型。后來又有人用動態(tài)規(guī)劃方法解決了圖的連通性和背包問題：符號決定性問 題；道路染色問題：以及超標量計算機代數(shù)問題等等。在神經(jīng)網(wǎng)絡(luò)方面，貝爾實 驗室的a p m i l l s ，j r b y u r k e ，p m p l a t z m a n 提出了模擬神經(jīng)網(wǎng)絡(luò)模型的d n a 計算方法。 基于表面的d n a 計算是早在9 6 年就提出的一種模型，它的優(yōu)越性在于具有 實現(xiàn)自動操作的潛力。2 0 0 0 年n a t u r e 刊載了q i n g h u al i u 的文章，標志著表面上 的d n a 計算正在逐步完善。 實現(xiàn)d n a 計算的自動化一直是研究者的個目標，在這方面，比較突出的工 作是以色列著名的可編程生物分子自動機的提出，模擬t u r i n g 機的裝置可以自動 并行的根據(jù)輸入的程序執(zhí)行不同的數(shù)據(jù)處理。2 0 0 3 年趙健等在科學通報上發(fā)表 論文，在表面上實現(xiàn)了可編程的分子自動機。 2 0 0 4 年上海交通大學b i o x 生命科學研究中心和中科院上海生科院營養(yǎng)科學 研究所已在試管中完成了d n a 計算機的雛形研制工作，在實驗上把自動機與表 面d n a 計算結(jié)合到一起，標志著中國第一臺“d n a 計算機”在上海問世。這一 d n a 計算機是在以色列魏茨曼研究所的d n a 計算機的基礎(chǔ)上進行改進后完成 的，其中包括用雙色熒光標記對輸入與輸出分子進行同時檢測，用測序儀對自動 運行過程進行實時監(jiān)測，用磁珠表面反應法固化反應提高可控性操作技術(shù)等，以 至最終在一定程度上完成模擬電子計算機處理0 ，1 信號的功能，并可能將來通過 北京工業(yè)大學理學碩士學位論文 計算芯片技術(shù)把電子計算機的計算功能進行本質(zhì)上的提升。 1 3d n a 計算的應用 ( 1 ) n p 問題：目前d n a 計算機最出色的應用就是n p 問題的解決，而且自從 a d l e m a n 的工作以后，用d n a 計算能解決的數(shù)學問題的種類迅速增長。近年來 人們意識到生物系統(tǒng)內(nèi)可能的越來越多的n p 問題，如在一定條件下的蛋白質(zhì)的 折疊過程，復制一長段d n a 序列所需要的擴增引物數(shù)量的選擇等等。很顯然， 如果有的話，生物系統(tǒng)可能已經(jīng)解決了自己的n p 問題。 ( 2 ) 基因分析：利用d n a 計算的方法來分析d n a 本身其實是一個很有意思 的問題。d n a 計算過程本來就是d n a 分子的一系列反應過程，這些過程的某些 步驟可能可以很好地反映出d n a 分子的一些特性，比如說s n p 。用d n a 計算過 程來分析d n a 分子有什么好處呢? 一個很大的好處是高通量，因為超大規(guī)模的 并行性是d n a 計算的天然特性。如果相關(guān)的檢測方法能解決的話，前景將非常 看好。 ( 3 ) 密碼設(shè)計和密碼破譯：日本學者嘗試用d n a 分子設(shè)計并存儲密碼。他們 意識到d n a 分予是天然的數(shù)據(jù)儲存載體，把二進制的密碼以特定的方式轉(zhuǎn)換成 d n a 密碼分子并隱藏在海量的其它d n a 分子當中，這些d n a 中還包括鎖定密 碼分子的d n a 鏈，必須用特定的程序才能把密碼分子擴增出來。在密碼破譯方 面，d n a 計算已經(jīng)展示了其巨大的潛力。a d l e m a n 等描述了l i p t o n 發(fā)展的d n a 計算方法來破譯d e s 密碼。這種密碼采用2 5 6 種密鑰加密，現(xiàn)有的計算機還幾乎 不可能破解；但是l i p t o n 利用d n a 鏈強大的編碼和并行運算能力構(gòu)建出全部可 能的密鑰，經(jīng)過幾個月的生物學操作，最終拿到了密鑰對應的惟一的一條d n a 鏈。 ( 4 ) 科學家們預測，在不久的將來，d n a 計算機可被用來開發(fā)新一代的基因 分型技術(shù)，處理基因組的信息，或用注入到人體內(nèi)的d n a 計算機進行基因治療。 1 4 研究內(nèi)容和意義 研究學者們證明了d n a 計算至少在理論上是通用的和完備的?；赿 n a 計 算的機器能像我們所用的電子計算機一樣進行編程，這主要是指d n a 計算框架 如何能模擬一個著名的通用計算模型，例如，它能模擬一個通用的圖靈機或元胞 第1 蘋緒論 自動機。由于d n a 計算出色的并行能力，研究學者們已經(jīng)開始考慮用它來解決 一些電子計算機很難解決的特殊問題。近年來，國外發(fā)表了多篇論文，研究運用 分子生物學的技術(shù)來解決一些實際問題。 四色問題又稱四色猜想，是世界近代三大數(shù)學難題之一。1 9 7 6 年由哈肯和阿 佩爾給出了首個證明，他們在美國伊利諾斯大學的兩臺不同的電子計算機上，用 了1 2 0 0 個小時，作了1 0 0 億判斷，完成了四色定理的證明，轟動了世界。此后 羅伯特森等人又給出了改進的算法，但是整體來說，這些方法證明起來所花費的 時間都相當長。基于d n a 計算的優(yōu)點，我們在本文探討用d n a 計算的方法來 證明四色定理，這里所指的證明是指用d n a 計算的方法來實現(xiàn)四色定理證明中 計算機證明的部分，而不包括邏輯證明部分，以其在較短的時間內(nèi)實現(xiàn)計算機證 明的部分。 雖然人們已經(jīng)證明了d n a 計算的通用性和完備性，也就是說用電子計算機 可以解決的問題用d n a 計算也一定能解決，但這都是理論性的，我們在這篇文 章中就是要設(shè)計一個具體的算法，來解決四色定理的證明。如果可以解決，顯然 是具有非常大的現(xiàn)實意義的。 1 5 本章小結(jié) 本章介紹了d n a 計算的計算機制、d n a 計算常用的生物操作、d n a 計算 的研究現(xiàn)狀以及d n a 計算的應用，給出了本文的研究內(nèi)容和意義。 2 1 四色定理簡介 第2 章四色定理證明 四色問題又稱四色猜想，是世界近代三大數(shù)學難題之一。 四色問題的內(nèi)容是：“任何一張地圖只用四種顏色就能使具有共同邊界的國 家著上不同的顏色?！庇脭?shù)學語言表示，即“將平面任意地細分為不相重迭的區(qū) 域，每一個區(qū)域總可以用1 ，2 ，3 ，4 這四個數(shù)字之一來標記，而不會使相鄰的 兩個區(qū)域得到相同的數(shù)字?！边@里所指的相鄰區(qū)域，是指有一整段邊界是公共的。 如果兩個區(qū)域只相遇于點或有限多點，就不叫相鄰的。因為用相同的顏色給它 們著色不會引起混淆。 四色猜想的提出來自英國。1 8 5 2 年，畢業(yè)于倫敦大學的弗南西斯格思里來 到一家科研單位搞地圖著色工作時，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖 都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色?！边@個現(xiàn) 象能不能從數(shù)學上加以嚴格證明呢? 他和在大學讀書的弟弟格里斯決心試一試。 兄弟二人為證明這一問題而使用的稿紙已經(jīng)堆了一大疊，可是研究工作沒有進 展。 1 8 5 2 年1 0 月2 3 日，他的弟弟就這個問題的證明請教了他的老師、著名數(shù)學 家德摩爾根，摩爾根也沒有能找到解決這個問題的途徑，于是寫信向自己的好 友、著名數(shù)學家漢密爾頓爵士請教。漢密爾頓接到摩爾根的信后，對四色問題進 行論證。但直到1 8 6 5 年漢密爾頓逝世為止，問題也沒有能夠解決。 1 8 7 2 年，英國當時最著名的數(shù)學家凱利正式向倫敦數(shù)學學會提出了這個問 題，于是四色猜想成了世界數(shù)學界關(guān)注的問題。世界上許多一流的數(shù)學家都紛紛 參加了四色猜想的大會戰(zhàn)。1 8 7 8 1 8 8 0 年兩年間，著名的律師兼數(shù)學家肯普和 泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認為四 色猜想從此也就解決了。 肯普的證明是這樣的：首先指出如果沒有一個國家包圍其他國家，或沒有三 個以上的國家相遇于一點，這種地圖就說是“正規(guī)的”，否則為非正規(guī)地圖。一 張地圖往往是由正規(guī)地圖和非正規(guī)地圖聯(lián)系在一起，但非正規(guī)地圖所需顏色種數(shù) 第2 章四色定理證明 一般不超過正規(guī)地圖所需的顏色，如果有一張需要五種顏色的地圖，那就是指它 的正規(guī)地圖是五色的，要證明四色猜想成立，只要證明不存在一張正規(guī)五色地圖 就足夠了。 肯普的證明包含兩個重要的步驟。他先用歸納法證明了一個圖g 至少存在一 個頂點v ，使得v 至多與五個其他的頂點相鄰。我們把這些頂點標記為 ”1 ，v 。，m 5 。然后將頂點v 刪除，這樣得到一個圖g 。= g v 。第二步主要證 明可以四著色的g 可以被重新著色，使得h ，v 。只需要三種不同的顏色進行著 色。把這些頂點進行著色的方法，現(xiàn)在稱之為肯普鏈?？掀真湸笾率沁@樣定義的： 由一些顏色交替的相鄰的國家所連成的一條鏈。在圖論當中，肯普鏈實際上是相 鄰頂點所組成的序列?？掀兆詈笾匦乱腠旤cv ，將它用第四種顏色進行著色 完成了整個證明。后來有人指出肯普的證明是錯誤的，不過肯普的證明闡明了兩 個重要的概念，對以后問題的解決提供了途徑。第一個概念是“構(gòu)形”。他證明 了在每一張正規(guī)地圖中至少有國具有兩個、三個、四個或五個鄰國，不存在每 個國家都有六個或更多個鄰國的正規(guī)地圖，也就是說，由兩個鄰國，三個鄰國、 四個或五個鄰國組成的一組“構(gòu)形”是不可避免的，每張地圖至少含有這四種構(gòu) 形中的一個( 如圖2 1 ) 。 武 到2 1 構(gòu)形 f i g u r e2 - 1c o n i i g u r a t i o n s 肯普提出的另一個概念是“可約”性?！翱杉s”這個詞的使用是來自肯普的論 證。他證明了只要五色地圖中有一國具有四個鄰國，就會有國數(shù)減少的五色地圖。 自從引入“構(gòu)形”，“可約”概念后，逐步發(fā)展了檢查構(gòu)形以決定是否可約的一 些標準方法，能夠?qū)で罂杉s構(gòu)形的不可避免組，是證明“四色問題”的重要依據(jù)。 但要證明大的構(gòu)形可約，需要檢查大量的細節(jié)，這是相當復雜的。 1 1 年后，即1 8 9 0 年，在牛滓大學就讀的年僅2 9 歲的赫伍德以自己的精確計 算指出了肯普在證明上的漏洞。他指出肯普說沒有極小五色地圖能有一國具有五 個鄰國的理由有破綻。不久，泰勒的證明也被人們否定了。人們發(fā)現(xiàn)他們實際上 北京工業(yè)大學理學碩士學位論文 證明了一個較弱的命題五色定理。就是說對地圖著色，用五種顏色就夠了。 后來，越來越多的數(shù)學家雖然對此絞盡腦汁，但一無所獲。于是，人們開始認識 到，這個貌似容易的題目，其實是一個可與費馬猜想相媲美的難題。 進入2 0 世紀以來，科學家們對四色猜想的證明基本上是按照肯普的想法在 進行。1 9 13 年，美國著名數(shù)學家、哈佛大學的伯克霍夫利用肯普的想法，結(jié)合 自己新的設(shè)想；證明了某些大的構(gòu)形可約。后來美國數(shù)學家富蘭克林于1 9 3 9 年 證明了2 2 國以下的地圖都可以用四色著色。1 9 5 0 年，有人從2 2 國推進到3 5 國。 1 9 6 0 年，有人又證明了3 9 國以下的地圖可以只用四種顏色著色；隨后又推進到 了5 0 國?？磥磉@種推進仍然十分緩隉。 高速數(shù)字計算機的發(fā)明，促使更多數(shù)學家對“四色問題”的研究。從1 9 3 6 年就開始研究四色猜想的?？耍_宣稱四色猜想可用尋找可約圖形的不可避免 組來證明。他的學生丟雷寫了一個計算程序，?？瞬粌H能用這程序產(chǎn)生的數(shù)據(jù)來 證明構(gòu)形可約，而且描繪可約構(gòu)形的方法是從改造地圖成為數(shù)學上稱為“對偶” 形著手。他把每個國家的首都標出來，然后把相鄰國家的首都用一條越過邊界的 鐵路連接起來，除首都( 稱為頂點) 及鐵路( 稱為弧或邊) 外，擦掉其他所有的線， 剩下的稱為原圖的對偶圖( 如圖2 2 ) 。到了六十年代后期，?？艘M個類似于 在電網(wǎng)絡(luò)中移動電荷的方法來求構(gòu)形的不可避免組。在?？说难芯恐械谝淮我灶H 不成熟的形式出現(xiàn)的“放電法”，這對以后關(guān)于不可避免組的研究是個關(guān)鍵，也 是證明四色定理的中心要素。 圖2 - 2 一個幽的對偶圖 f i g u r e2 - 2t h ed u a lg r a p ho f ag r a p h 電子計算機問世以后，由于演算速度迅速提高，加之人機對話的出現(xiàn)，大大 加快了對四色猜想證明的進程。美國伊利諾大學哈肯在1 9 7 0 年著手改進“放電 過程”，后與阿佩爾合作編制一個很好的程序。就在1 9 7 6 年6 月，他們在美國 伊剎諾斯大學的兩臺不同的電子計算杌上，用了1 2 0 0 個小時，作了1 0 0 億判斷， 第2 章四色定理證明 終于完成了四色定理的證明，轟動了世界。 1 9 9 6 年，美國數(shù)學學會的電子研究雜志上又發(fā)表了篇關(guān)于四色猜想的證 明。這個證明是對阿佩爾和哈肯證明的改進。而且，它再一次證實了阿佩爾和哈 肯計算機證明的正確性。這個新的證明是由羅伯特等人提出的。羅伯特使俄亥俄 州立大學數(shù)學系的教授，于1 9 6 9 年獲得沃特盧大學博士。雖然整個證明簡化了， 但是證明的框架與阿佩爾一哈肯的證明是相同的。整個證明的組織結(jié)構(gòu)如下： ( 1 ) 列出一個構(gòu)形集。 ( 2 ) 可約性證明：構(gòu)形集當中的構(gòu)形不會出現(xiàn)在四色猜想的極小反例當中。因為 一旦有個構(gòu)形出現(xiàn)在極小反例當中，那么可以給出一個更小的極小反例。這一 部分的證明與阿佩爾一哈肯的證明一樣，都是用計算機來證明的。 ( 3 ) 證明每個極小反例都是“內(nèi)部六連通”的三剖分。 ( 4 ) 不可避免性證明：每個內(nèi)部六連通的三剖分至少包含一個構(gòu)形。 因此，不存在極小反例。如果不存在極小反例，那么四色猜想是成立的。 新證明主要的優(yōu)點在于： ( 1 ) 不可避免集的數(shù)量從1 4 7 6 個減到6 3 3 個： ( 2 ) “放電”規(guī)則從3 0 0 個減少到3 2 個： ( 3 ) 尋找一個平面圖四著色算法的時間復雜度由s 3 減到s ： ( 4 ) 不可避免性的證明也得到了改進。 這是一百多年來吸引許多數(shù)學家與數(shù)學愛好者的大事，當兩位數(shù)學家將他們 的研究成果發(fā)表的時候，當?shù)氐泥]局在當天發(fā)出的所有郵件上都加蓋了“四色足 夠”的特制郵戳，以慶祝這一難題獲得解決。 “四色問題”的被證明僅解決了一個歷時i 0 0 多年的難題，而且成為數(shù)學史 上一系列新思維的起點。在“四色問題”的研究過程中，不少新的數(shù)學理論隨之 產(chǎn)生，也發(fā)展了很多數(shù)學計算技巧。如將地圖的著色問題化為圖論問題，豐富了 圖論的內(nèi)容。不僅如此，“四色問題”在有效地設(shè)計航空班機日程表，設(shè)計計算 機的編碼程序上都起到了推動作用。 不過不少數(shù)學家并不滿足于計算機取得的成就，他們認為應該有一種簡捷明 快的書面證明方法。直到現(xiàn)在，仍由不少數(shù)學家和數(shù)學愛好者在尋找更簡潔的證 明方法。 2 2 四色定理證明 2 2 1 預備知識 令r 是一個圖，礦( 丁) ，e ( t ) 分別代表圖r 所有點和所有邊的集合，其中 y ( ，) ，e ( r ) 都是有限集，任何一條邊和兩個頂點相連接。( v ) 代表圖t 中一個 頂點v 的度數(shù)。 如果圖丁能畫在一個平面上，且使得丁中除端點外任意兩條邊均不相交，則 稱圖r 是可平面的。平面上的圖r 有一個無限區(qū)，它的意義在于歐拉公式的應用， 因為歐拉公式是用在平面或球面上的。對于一個可平面圖，其歐拉公式為 p q + ，= 2 ，其中p ，g ，分別是點、邊和區(qū)的個數(shù)。 在圖論中，任何區(qū)是三角區(qū)的圖稱為一個- - 音t j 分( 如圖2 3 ) 。e 是三角區(qū)r 的 三條邊，則稱e 與三角區(qū)，相關(guān)聯(lián)。 、k 芬 圖2 - 3 三剖分示例 f i g u r e2 - 3a ne x a m p l eo f t r i a n g u l a t i o n 一個圖分為有限區(qū)和無限區(qū)兩部分，一個三剖分加上無限區(qū)稱為一個近三剖 分。 令g 是一個三剖分或者近三剖分，令k ：五( g ) - 卜1 ，0 ，1 ) 是一個映射，若 k ( e ) ，k ( ，) ，k ( g ) ) = 1 , 0 ，1 ) ，其中e ，f ，g 是三角區(qū)r 的三條邊，則稱，被三著色。 第2 章四色定理證明 如果g 的每個區(qū)被三著色( 是一個三剖分) 或者g 的每個有限區(qū)被三著色( g 是 一個近三剖分) ，我們說k 是g 的一個邊的三著色。 令七：v ( g ) _ 1 ，2 ，3 ，4 是另一個映射，對于g 的任何一條邊，如果它與點“，v 相關(guān)聯(lián)，且有k ( u ) k ( v ) ，則我們稱g 被頂點四著色。k 稱為g 的一個頂點四著 色。 后文中凡是提到四著色均指頂點的四著色，而三著色均指邊的三著色。 ( 2 1 ) “”一個三剖分丁是可以頂點四著色的當且僅當可以對它進行邊的三著 色。 例如，對三剖分任意一條邊e ，如果它有兩個頂點“，v ，可以建立如下對應 f 一1 七( “) ，t ( v ) ) = 1 , 2 或者 3 ，4 ) 方式：巾( 8 ) = 0 _ j ( “) ，七( v ) ) = 1 ，3 ) 或者 2 ，4 ) i l 尼( “) ，七( v ) ) = 1 , 4 ) 或者 2 ，3 ) 這樣如果一個三剖分可以進行頂點四著色，那么按照上面的對應方式就可以 進行邊的三著色。在做計算機程序時，三著色比四著色來的更為容易一些，同時 它們兩者之間的轉(zhuǎn)化卻是非常簡單的，所以在后面的證明中我們使用三著色。 l 圖2 4 頂點四著色和邊三著色 f i g u r e2 - 4f o u rc o l o r i n go f v e r t i c e s a n dt h r e ec o l o r i n go f e d g e s 對于每一個地圖，我們可以把每一個區(qū)( 區(qū)域或國家) 看作一個點，而區(qū)與 區(qū)之間的鄰接關(guān)系看作點與點之間的連線，因此得到一個點線圖。這不是個三 剖分。但是通過適當加一些邊它可以成為一個三剖分。很明顯，如果加邊以后的 三剖分有一個三著色，那么它可以很容易的轉(zhuǎn)化成原圖的三著色。因此，我們可 以通過找出加邊后的三剖分三著色的方法來找出原圖的三著色。 北京工業(yè)大學理學碩士學位論文 2 2 2 構(gòu)形 如果圖r 不可以四著色，而對于任一個圖丁。， 若 l v ( t ) 卜i e ( r ) 1 d g ( v ) 。 兩種情況下都有7 。( v ) 5 。 ( 3 ) k 有環(huán)型2 ，環(huán)型定義如下：e ( y f ( v ) 一d a ( v ) 一1 ) ，其中 ”e f f = v v 與世的無限區(qū)相關(guān)聯(lián)，且g ( 世) 睫連通的 。 四鄰鄰pp 鄰舀 哪哪媽翎哪哪哪 圖2 - 5 部分構(gòu)形 f i g u r e2 - 5p a r to f c o n f i g u r a t i o n s 第2 章四色定理證明 構(gòu)形也是四色定理證明當中一個非常重要的概念，在羅伯特森等人的證明 中共給出了6 3 3 個構(gòu)形。 在用圖形描述構(gòu)形k 的時候，一個辦法是畫出圖，把( v ) 的值寫在對應的 頂點v 的旁邊，但是這樣表示起來不方便。羅伯特森等人沿用?？说姆椒ㄓ庙旤c 的形狀來表示k ( v ) 的值，如圖2 - 6 所示： ，y 耳( ”) = 5 7 k ( ”) = 6 o1 k ( ”) = 7 口，y 片( 扣) = 8 v懈( ”) = 9 o ，y ( t j ) = 1 0 圖2 - 6 頂點的形狀 f i g u r e2 - 6t h es h a p e so f v e r t i c e s 兩個構(gòu)形k 和工是同構(gòu)的，如果存在一個所在平面的同胚，將g ( k ) 映到 g ( z ) ，y 。映到y(tǒng) 。在 1 9 1 q u 共列出t 6 3 3 個構(gòu)形，圖2 5 給出了其中的部分構(gòu)形。 與6 3 3 個構(gòu)形中任何一個構(gòu)形同構(gòu)的構(gòu)形稱為一個好構(gòu)形。 ( 2 3 ) i t 9 如果丁是一個極小反例，那么t 中沒有好構(gòu)形出現(xiàn)。 ( 2 4 ) 1 1 9 】對于每個內(nèi)部6 連通的三剖分7 1 ，r 中會出現(xiàn)一些好構(gòu)形。 由( 2 2 ) 、( 2 3 ) 、( 2 4 ) 可知：極小反例不存在，四色定理是正確的。本文將在 2 2 3 節(jié)中討論( 2 3 ) ，( 2 4 ) 可以在比較短的時間內(nèi)用手工驗證，具體的證明可參照 【19 】。( 2 3 ) 要依靠計算機來進行證明，而且需要相當長的時間，本文的主要目的 就是要用d n a 計算來減少證明的時間。 2 2 3 可約性 一個回路指一個非空的圖，且圖中每個頂點的度數(shù)都是2 。 1 9 1 令世是一個構(gòu)形，s 是近三剖分。如果： ( 1 ) r 是s 的導出回路，且是s 的無限區(qū)的邊界。 ( 2 ) g ( k ) 是s 的一個導出子圖，g ( 世) = s 礦( r ) ，f f ：侗j g ( k ) 的有限區(qū)是 s 的有限區(qū)，c ( k ) 的無限區(qū)包含r 和s 的無限區(qū)。 1 5 北京工業(yè)大學理學碩士學位論文 ( 3 ) 任何在s 中不在v ( r ) 中的點v 在s 中的度數(shù)為y 。( v ) 。 則稱s 是構(gòu)形k 的關(guān)于環(huán)r 的自由補全圖。 圖2 7 為6 3 3 個構(gòu)形當中的其中一個 0 ，g 。，g ，與日的無限區(qū)相關(guān)聯(lián)；若t = 0 ，則g ，與的任何有限區(qū)都不 關(guān)聯(lián)； 4 ) 1 i f ，與g h 和g 。相關(guān)聯(lián)； 5 ) 0 f ，k ( g ，) 0 。 說明：本章帶+ 的內(nèi)容源自蔣興鵬的畢業(yè)論文任意地圖四著色問題的d n a 算法 第3 章三著色的d n a 算法 v j 圖3 - i 三剖分的脈 f i g u r e3 - 1t h er i b so f t r i a n g u l a t i o n 脈