[發明專利]基于DNA計算實現的圖頂點著色方法和DNA計算系統

無效

• 申請號: 200810085571.4
• 申請日: 2008-03-19
• 公開（公告）號: CN101256640A
• 公開（公告）日: 2008-09-03
• 發明（設計）人: 許進;強小利;張成;楊靜;王淑棟;劉向榮
• 申請（專利權）人: 北京大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06T15/00;C12Q1/68
• 代理公司: 北京同達信恒知識產權代理有限公司
• 代理人: 李娟

1、一種基于DNA計算實現的圖頂點著色方法，其特征在于，包括：

將待著色圖劃分為至少兩個子圖；

根據給定顏色種類，基于DNA計算獲得每一個子圖對應的頂點著色方案集合；

基于DNA計算逐步合并各子圖對應的頂點著色方案，獲得所述待著色圖的頂點著色方案集合。

2、如權利要求1所述的方法，其特征在于，將所述待著色圖劃分為至少兩個子圖時，優先選擇度數較大的頂點作為劃分子圖的頂點。

3、如權利要求1或2所述的方法，其特征在于，根據在頂點排列順序中標號連續的頂點在所述待著色圖中有邊相連為優先的原則，確定每一個子圖中所包含的頂點排列順序。

4、如權利要求3所述的方法，其特征在于，還根據各頂點在所述待著色圖中組成Hamilton圈、最大圈或最長路為優先的原則依次確定每一個子圖包含頂點的排列順序。

5、如權利要求3或4所述的方法，其特征在于，根據所述待著色圖的頂點數，確定每個子圖中包含的頂點數在10-20之間。

6、如權利要求1所述的方法，其特征在于，所述根據給定顏色種類，基于DNA計算獲得每一個子圖對應的頂點著色方案集合的方法包括：

分別確定各頂點可用的顏色集合，以及每個顏色集合中包含的顏色元素個數；

對應每一個顏色元素生成互不相同的DNA序列，并為每兩個標號連續且代表不同顏色的頂點生成DNA序列探針；

采用PCR方法，分別根據每一個子圖的DNA序列和DNA序列探針合成頂點著色方案的初始解空間；

分別在每一個子圖的初始解空間中刪除非解并提取真解，每一個子圖的所有真解構成的集合就是該子圖的頂點著色方案集合。

7、如權利要求1所述的方法，其特征在于，所述基于DNA計算逐步合并各子圖對應的頂點著色方案集合，獲得所述待著色圖的頂點著色方案集合的方法包括：

根據PCR方法，逐步兩兩合并具有橋點的子圖的解，刪除非解并提取真解，直到合并為一個完整的待著色圖時獲得所述待著色圖的頂點著色方案集合。

8、如權利要求6或7所述的方法，其特征在于，所述的PCR方法為半巢式PCR方法。

9、一種DNA計算系統，其特征在于，包括：

輸入模塊：用于根據待著色圖分解出的至少兩個子圖，編碼并自動合成每一個子圖對應的DNA序列；

至少一個運算模塊：用于根據給定顏色種類，基于DNA計算獲得每一個子圖對應的頂點著色方案集合，每一種頂點著色方案中任意兩個相鄰頂點著不同顏色；基于DNA計算逐步合并各子圖對應的頂點著色方案集合，獲得所述待著色圖的頂點著色方案集合；

輸出模塊：用于讀取所述運算模塊輸出的所述待著色圖的頂點著色方案集合。

10、如權利要求9所述的DNA計算系統，其特征在于，

所述輸入模塊包括：

DNA合成儀，用于合成分別為待著色圖的每一個子圖所設計的DNA序列和DNA序列探針；

所述運算模塊包括：

試管，用于容納DNA樣品；

加樣機/微量移液器，用于將DNA合成儀合成的DNA序列以及其他試劑加到試管中；

PCR儀，用于對試管中的DNA樣品進行DNA運算，從而篩選所需的DNA鏈，并進行PCR擴增；

電泳槽，用于將PCR擴增后的DNA樣品放入電泳儀器中進行電泳，以分離所需序列；

所述輸出模塊包括：

凝膠成像系統，用于分析在電泳槽中跑完的電泳條帶的結果；

核酸蛋白分析儀，用于分析試管中單位體積中所含DNA的數量。