[發(fā)明專利]一種基于DNA計算模型的拉蒙賽圖的獲取方法和系統(tǒng)

無效

• 申請?zhí)枺?/td>: 200910080655.3
• 申請日: 2009-03-23
• 公開（公告）號: CN101847145A
• 公開（公告）日: 2010-09-29
• 發(fā)明（設計）人: 許進;李菲
• 申請（專利權）人: 北京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/10;G06N3/12
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 胡小永

技術領域

本發(fā)明涉及計算機和生物技術領域，特別是涉及一種基于DNA(Deoxyribonucleic?acid，脫氧核糖核酸)計算模型的Ramsey(拉蒙賽)圖的獲取方法和系統(tǒng)。

背景技術

Ramsey數(shù)是指給定任意兩個正整數(shù)k、l，總存在一個最小的正整數(shù)r(k，l)，使得任意r(k，l)個頂點的圖，或者含有k個頂點的團，或者含有l(wèi)個頂點的獨立集。該最小的正整數(shù)r(k，l)稱為關于(k，l)的Ramsey數(shù)。容易算出r(1，l)＝r(k，1)＝1，r(2，l)＝l，r(k，2)＝k，r(k，l)＝r(l，k)，其中r(k，l)稱為經典Ramsey數(shù)。

上述的圖指有限、無向、簡單圖。設正整數(shù)m，n，p≥1，Ramsey(m，n)-圖是指既不含m個頂點的團也不含n個頂點獨立集的圖；Ramsey(m，n，p)-圖是指階數(shù)為p的Ramsey(m，n)-圖。分別用G(m，n)，G(m，n，p)表示所有Ramsey(m，n)-圖，Ramsey(m，n，p)-圖的集合。Ramsey數(shù)r(m，n)定義為不存在Ramsey(m，n，p)-圖的最小數(shù)p。目前已確定的經典Ramsey數(shù)有：r(3，3)＝6，只有1個Ramsey圖；r(3，4)＝9，共有3個Ramsey圖；r(3，5)＝14，只有1個Ramsey圖；r(3，6)＝18，共有191個Ramsey圖；r(3，7)＝23，共有191個Ramsey圖；r(3，8)＝28，業(yè)已知道它有430215個Ramsey圖；r(3，9)＝36，只有1個Ramsey圖；r(4，4)＝18，只有1個Ramsey圖，r(4，5)＝25，業(yè)已發(fā)現(xiàn)350904個Ramsey圖(可能更多)。

目前已找到105個34階Ramsey(4，6)-圖，據(jù)推測35～40階Ramsey(4，6)-圖可能存在。目前已找到656個42階Ramsey(5，5)-圖，可以推測43～49階Ramsey(5，5)-圖可能存在。注意，每個Ramsey(5，5)-圖的補圖也是Ramsey(5，5)-圖。

近來，電子計算機在求解Ramsey數(shù)問題的研究上起到了巨大的促進作用，如Ramsey數(shù)r(3，8)和r(4，5)均是借助于電子計算機來完成的。但隨著問題規(guī)模的增大，如r(3，10)至少需要從40個頂點的圖集中搜索是否存在Ramsey圖，而這個搜索次數(shù)理論上需要約2⁷⁶⁰個圖，顯然電子計算機對此是無法實現(xiàn)的。這就迫使科學家在Ramsey數(shù)問題的研究上另辟蹊徑。

目前，DNA計算機的研究得到了長足的發(fā)展，業(yè)已建立了不少求解組合優(yōu)化中NP-完全問題的DNA計算模型，但至今尚未見到關于求解Ramsey數(shù)這個組合數(shù)學領域困難問題的DNA計算模型。在DNA計算機研究方面有一個消除解空間指數(shù)爆炸問題的新方法(參見Xu?Jin，Qiang?Xiaoli?et?al.A?parallel?type?of?DNA?computing?model?for?graph?vertex?coloring.Submitted?to?Journal?of?the?ACM(Mar.20，2008))，并在此基礎上建立了一個求解61個頂點圖的3-著色問題DNA計算模型并成功地進行了實驗，這標志著DNA計算機不僅已經具備了求解某些大規(guī)模信息處理的能力，而且也可以用于解決電子計算機無法解決的問題了。

借助于電子計算機在求解經典Ramsey數(shù)模型的研究上，Mckay等人作出了杰出的貢獻(參見Mckay?B?D，Radziszowski?S?P.R(4，5)＝25.Journal?of?Graph?Theory，1995，19：309～322.和Mckay?B.D.，Zhang?K.M.The?Value?of?the?Ramsey?Number?R(3，8).Journal?of?Graph?Theory，1992，16：99～105.)。他們所建立模型的基本思想是利用圖的自同構群來刪除同構子圖，其具體做法是：首先建立10個頂點所有非標定子圖的集合，然后以這10個頂點非標定子圖的集合為基礎，進一步構造所需要的圖集合。

Mckay等人在進一步構造所需的圖集合時，一般通過每次增加一個頂點來完成的。但是，即就如此，一下子增加的非解也是很多，從而導致電子計算機在一定的范圍內就無能為力。這也就是目前利用電子計算機求解Ramsey數(shù)停滯不前的根本原因所在。

發(fā)明內容