[發(fā)明專利]一種基于對稱破壞的子圖同構(gòu)約束求解方法

有效

• 申請?zhí)枺?/td>: 201810607429.5
• 申請日: 2018-06-13
• 公開（公告）號: CN108932306B
• 公開（公告）日: 2021-05-25
• 發(fā)明（設計）人: 徐周波;梁軒瑜;戴瑀君;寧黎華;楊健;黃文文;劉桂珍;張鵾
• 申請（專利權(quán)）人: 桂林電子科技大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 桂林市持衡專利商標事務所有限公司 45107
• 代理人: 陳躍琳

1.一種基于對稱破壞的子圖同構(gòu)約束求解方法，應用于抗AIDS化合物比對中，通過分析提取化合物中的信息構(gòu)建抗AIDS化合物比對圖，圖中節(jié)點對應元素，邊對應化學鍵；其特征是，具體包括步驟如下：

步驟1、模式圖的自同構(gòu)節(jié)點檢測，即：

步驟1.1、按節(jié)點的度，將模式圖的上層分區(qū)節(jié)點和下層分區(qū)節(jié)點各劃分到不同的單元中，其中度相同的節(jié)點劃分為同一單元；此時上層分區(qū)的單元數(shù)和下層分區(qū)的單元數(shù)均為n，具有相同度節(jié)點的上層分區(qū)單元與對應的下層分區(qū)單元具有相同的標記；

步驟1.2、當上層分區(qū)單元A_i內(nèi)的節(jié)點數(shù)量大于1時，將上層分區(qū)單元A_i內(nèi)的每個節(jié)點依次與對應下層分區(qū)單元B_i內(nèi)的所有節(jié)點進行組合配對，并逐一判斷每組配對的節(jié)點是否屬于同一映射集合：

若當前配對的節(jié)點屬于同一映射集合時，則對下一組配對的節(jié)點進行判斷；

否則，分別將當前配對的節(jié)點中，原屬于上層分區(qū)單元A_i的節(jié)點放入新建的上層分區(qū)單元A_n+i中，原屬于下層分區(qū)單元B_i的節(jié)點放入新建的下層分區(qū)單元B_n+i中；

步驟1.3、對于新建的上層分區(qū)單元A_n+i和新建的下層分區(qū)單元B_n+i內(nèi)的節(jié)點，觀察其鄰接點，為這些鄰接點添加連接邊標記neibor，并記錄新建上層分區(qū)單元A_n+i內(nèi)節(jié)點的鄰接點所屬單元標記；

步驟1.4、對每個鄰接點的所屬單元標記所對應的上層分區(qū)單元A_i和下層分區(qū)單元B_i內(nèi)的節(jié)點進行分類：

對于上層分區(qū)單元A_i內(nèi)的節(jié)點：將有連接邊標neibor標記的節(jié)點保留在該上層分區(qū)單元A_i內(nèi)，將沒有連接邊標neibor標記的節(jié)點從原所屬單元移入到新建的上層分區(qū)單元A_2n+i中，同時記錄此新建的上層分區(qū)單元A_2n+i的單元標記并存入臨時標記集合Nlabel中；

對于下層分區(qū)單元B_i內(nèi)的節(jié)點：將有連接邊標neibor標記的節(jié)點保留在該下層分區(qū)單元B_i內(nèi)，將沒有連接邊標neibor標記的節(jié)點從原所屬單元移入到新建的下層分區(qū)單元B_2n+i中；

步驟1.5、依次選取上層分區(qū)單元A_i和對應的下層分區(qū)單元B_i：若上層分區(qū)單元A_i與下層分區(qū)單元B_i內(nèi)的節(jié)點數(shù)量不一致，則轉(zhuǎn)至步驟1.2；否則，轉(zhuǎn)至步驟1.6；

步驟1.6、取臨時標記集合Nlabel內(nèi)的單元標記，找到與此單元標記對應的上層分區(qū)單元A_i，并觀察上層分區(qū)單元A_i內(nèi)節(jié)點的鄰接點，為這些鄰接點添加連接邊標記neibor，并記錄此上層分區(qū)單元A_i內(nèi)節(jié)點的鄰接點所屬單元標記，并轉(zhuǎn)至步驟1.4；

步驟1.7、當上層分區(qū)與下層分區(qū)的每個單元均僅包含一個節(jié)點時，若上層分區(qū)中的節(jié)點a與下層分區(qū)中的節(jié)點b的所屬單元標記相同，且上層分區(qū)中的節(jié)點b與下層分區(qū)中的節(jié)點a的所屬單元標記相同，則節(jié)點a和節(jié)點b為一組自同構(gòu)節(jié)點，每組自同構(gòu)節(jié)點形成一個映射集合；

步驟2、當模式圖的所有自同構(gòu)節(jié)點檢測完成后，得到一系列置換，這些置換構(gòu)成置換群，通過施賴埃爾一西姆斯算法對置換群進行操作，即首先通過置換群得到穩(wěn)定鏈，其次利用穩(wěn)定鏈求得陪集，最后，利用陪集生成節(jié)點間的約束關系；

步驟3、利用步驟2所得到的模式圖中節(jié)點的約束關系，結(jié)合子圖同構(gòu)的通用約束，構(gòu)建子圖同構(gòu)問題的對稱破壞CSP模型，對此對稱破壞CSP模型進行求解，即可得到目標圖中的與模式圖同構(gòu)的子圖，且這些解互不為對稱解；

上述i∈1，2，...，n。