[發明專利]基于改進PCR計算模型求解最大團問題的方法

在審

• 申請號: 201510860554.3
• 申請日: 2015-12-01
• 公開（公告）號: CN105488569A
• 公開（公告）日: 2016-04-13
• 發明（設計）人: 張強;翟偉華;鄭學東
• 申請（專利權）人: 大連大學
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 大連創達專利代理事務所(普通合伙) 21237
• 代理人: 劉濤

1.基于改進PCR計算模型求解最大團問題的方法，其特征在于，如下步驟：

步驟1：建立無向圖的補圖；

步驟2：用DNA鏈表示補圖的頂點子集，并對DNA鏈進行編碼,利用PCR技術對DNA鏈上的 特定片段進行復制并利用XPCR技術生成解空間；

步驟3：給定一條補圖邊,每條補圖邊對應兩個頂點，篩選出含有這兩個頂點的一個或 兩個的DNA鏈，放入試管；

步驟4：對試管中的DNA鏈重復步驟3，直到所有的補圖邊均被篩選過；

步驟5：從步驟4所得結果中，利用PCR技術篩選出試管中最短的DNA鏈作為含有最少頂 點數的子集；

步驟6：對步驟5中所得子集求補，得到最終結果。

2.根據權利要求1所述的基于改進了的PCR計算模型求解最大團問題的方法,其特征在 于:對于給定的無向圖G＝(V,E),其中V＝{v₁,...,v_n},E＝{e₁,...,e_m},求解具體步驟如 下：

1)建立無向圖G的補圖

2)用DNA序列對補圖中的每個頂點進行DNA序列編碼，采用二進制編碼頂點子集,編 碼格式為其中U_iX代表第i個頂點在頂點子集中的狀態；并 生成無向圖G的所有可能頂點子集，即為解空間；

3)對補圖中的所有的邊進行編號，每條邊均由兩個頂點唯一確定

4)給定一條補圖中的邊利用PCR技術篩選含有v_i或v_l的DNA鏈，并放入特 定試管T中；

5)對試管T中DNA鏈重復步驟4，直到所有的補圖邊均被篩選過；

6)利用PCR技術篩選出試管T中，含有最少的頂點的子集，并對這些子集求補，即為最終 結果。

3.根據權利要求1或2所述的基于改進了的PCR計算模型求解最大團問題的方法,其特 征在于:所述DNA鏈為DNA雙鏈。

4.根據權利要求1所述的基于改進PCR計算模型求解最大團問題的方法，其特征在于， 所述步驟2中生成解空間的具體方法如下：利用PCR技術，對初始DNA雙鏈分子按照頂點編 號，逐位循環進行XPCR交叉連接，XPCR進行的過程中會伴隨DNA雙鏈分子的指數擴增，對于n 個頂點的簡單無向圖，循環n次得到圖所有的頂點子集，則試管中生成的DNA雙鏈分子表示 所有的頂點子集，得到解空間。

5.根據權利要求1所述的基于改進PCR計算模型求解最大團問題的方法，其特征在于： 所述步驟3中篩選的方法為通過XPCR操作對含有特定DNA分子序列的DNA分子后面添加指定 序列β,以DNA分子片段ω和β的后綴分別作為PCR操作的前端與后端引物，對添加了特定序 列β的DNA分子進行指數擴增，擴增后以DNA分子的長度作為DNA序列分離的特征條件，通過 凝膠電泳對DNA序列進行分離，篩選出含有特定頂點的頂點子集。