一種在無(wú)機(jī)晶體結(jié)構(gòu)中檢索特定子結(jié)構(gòu)的計(jì)算機(jī)方法

霍衛(wèi)峰 李 乙,* 盧君然 于吉紅 徐如人 李 晶

(1吉林大學(xué)無(wú)機(jī)合成與制備化學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室,長(zhǎng)春130012;2北京科技大學(xué)應(yīng)用力學(xué)系,北京100083)

一種在無(wú)機(jī)晶體結(jié)構(gòu)中檢索特定子結(jié)構(gòu)的計(jì)算機(jī)方法

霍衛(wèi)峰1李 乙1,*盧君然1于吉紅1徐如人1李 晶2

(1吉林大學(xué)無(wú)機(jī)合成與制備化學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室,長(zhǎng)春130012;2北京科技大學(xué)應(yīng)用力學(xué)系,北京100083)

提出了一種針對(duì)無(wú)機(jī)晶體化合物的子結(jié)構(gòu)檢索方法.該方法以VF2子圖同構(gòu)算法為基礎(chǔ),針對(duì)無(wú)機(jī)晶體化合物的結(jié)構(gòu)特點(diǎn),采用了兩種策略以提高子結(jié)構(gòu)檢索的效率:(1)引入晶體的對(duì)稱(chēng)性信息避免了在等價(jià)原子間進(jìn)行的大量重復(fù)性計(jì)算;(2)采用結(jié)構(gòu)編碼預(yù)篩選可以有效地減少目標(biāo)結(jié)構(gòu)的數(shù)量.我們以在無(wú)機(jī)微孔分子篩數(shù)據(jù)庫(kù)中進(jìn)行子結(jié)構(gòu)檢索為例測(cè)試該方法的有效性.測(cè)試結(jié)果表明,該方法可以快速且準(zhǔn)確地在分子篩數(shù)據(jù)庫(kù)中檢索包含特定子結(jié)構(gòu)的記錄.兩種檢索策略的引入大大降低了子結(jié)構(gòu)檢索的復(fù)雜度,檢索速度可提高3-5個(gè)數(shù)量級(jí).該方法通過(guò)Perl語(yǔ)言實(shí)現(xiàn),具有較好的可移植性.

無(wú)機(jī)晶體材料;數(shù)據(jù)庫(kù);子結(jié)構(gòu)檢索;VF2算法;分子篩;構(gòu)筑基元

1 引言

分子結(jié)構(gòu)檢索是利用計(jì)算機(jī)程序從數(shù)據(jù)庫(kù)中提取分子結(jié)構(gòu)信息的過(guò)程,是化學(xué)信息學(xué)的核心研究領(lǐng)域之一,1其中的子結(jié)構(gòu)檢索問(wèn)題是研究最多的課題之一.簡(jiǎn)單而言,子結(jié)構(gòu)檢索就是利用計(jì)算機(jī)方法在分子結(jié)構(gòu)數(shù)據(jù)庫(kù)中尋找包含特定子結(jié)構(gòu)的分子.目前,子結(jié)構(gòu)檢索主要應(yīng)用于在有機(jī)分子結(jié)構(gòu)中尋找特定的官能團(tuán),主要有ParMol、2MoFa、3FFSM、4gSpan、5Gaston、6SMSD7等方法.和有機(jī)分子一樣,無(wú)機(jī)晶體材料的子結(jié)構(gòu)(構(gòu)筑基元)對(duì)無(wú)機(jī)晶體材料的結(jié)構(gòu)、性質(zhì)以及合成研究至關(guān)重要,8,9因此針對(duì)無(wú)機(jī)晶體材料的子結(jié)構(gòu)檢索同樣具有非常重要的意義.

然而,和以獨(dú)立分子為單位的有機(jī)晶體材料不同,無(wú)機(jī)晶體結(jié)構(gòu)往往是三維方向無(wú)限延展的,沒(méi)有像有機(jī)分子一樣的特定獨(dú)立單元,數(shù)以萬(wàn)計(jì)不同配位狀態(tài)的原子相互連接形成一個(gè)巨大的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu).在如此巨大的體系中進(jìn)行子結(jié)構(gòu)檢索是一個(gè)非常復(fù)雜的問(wèn)題;而當(dāng)檢索范圍擴(kuò)大到由大量復(fù)雜無(wú)機(jī)結(jié)構(gòu)組成的數(shù)據(jù)庫(kù)時(shí),子結(jié)構(gòu)檢索將變得難以實(shí)現(xiàn).目前在化學(xué)領(lǐng)域中使用最廣泛的晶體結(jié)構(gòu)數(shù)據(jù)庫(kù)是劍橋結(jié)構(gòu)數(shù)據(jù)庫(kù)(CSD),10數(shù)據(jù)庫(kù)中包含劍橋晶體數(shù)據(jù)中心開(kāi)發(fā)的子結(jié)構(gòu)檢索工具Conquest,11其原理和有機(jī)分子的檢索類(lèi)似,即把龐大的晶體結(jié)構(gòu)分割為有限大小的晶體學(xué)不對(duì)稱(chēng)單元,進(jìn)一步把這些不對(duì)稱(chēng)單元當(dāng)作獨(dú)立分子進(jìn)行子結(jié)構(gòu)檢索.這種檢索方法的局限性是顯而易見(jiàn)的:首先,無(wú)機(jī)晶體的不對(duì)稱(chēng)單元在理論上是可以任意選取的,僅憑不對(duì)稱(chēng)單元無(wú)法代表整個(gè)無(wú)機(jī)骨架結(jié)構(gòu);更為重要的是,當(dāng)待檢索的子結(jié)構(gòu)位于一個(gè)以上不對(duì)稱(chēng)單元的交界時(shí),像Conquest這種只檢索不對(duì)稱(chēng)單元內(nèi)部的方法是無(wú)法識(shí)別不對(duì)稱(chēng)單元之間的關(guān)聯(lián)的.因此以晶體學(xué)不對(duì)稱(chēng)單元或獨(dú)立分子為基礎(chǔ)的子結(jié)構(gòu)檢索方法并不適用于不具備獨(dú)立單元的無(wú)機(jī)晶體結(jié)構(gòu).目前,對(duì)無(wú)機(jī)晶體結(jié)構(gòu)進(jìn)行子結(jié)構(gòu)檢索的唯一途徑是將其骨架拓?fù)渚W(wǎng)絡(luò)擴(kuò)展到相當(dāng)大的范圍內(nèi)(例如8個(gè)晶胞),而擴(kuò)大的拓?fù)渚W(wǎng)絡(luò)同時(shí)會(huì)使計(jì)算量以指數(shù)形式遞增,當(dāng)檢索的對(duì)象是包含大量無(wú)機(jī)結(jié)構(gòu)的數(shù)據(jù)庫(kù)時(shí),子結(jié)構(gòu)檢索將變得難以實(shí)現(xiàn).

由此可見(jiàn),無(wú)機(jī)晶體材料子結(jié)構(gòu)檢索的重要性和理論方法的局限性迫切要求新方法的誕生.基于這些問(wèn)題,結(jié)合無(wú)機(jī)晶體材料的結(jié)構(gòu)特點(diǎn),我們提出了一種可以在無(wú)機(jī)晶體結(jié)構(gòu)中有效地進(jìn)行子結(jié)構(gòu)檢索的方法.

2 方法

將無(wú)機(jī)晶體結(jié)構(gòu)中的中心原子看作節(jié)點(diǎn),將節(jié)點(diǎn)之間的連接看作邊,無(wú)機(jī)晶體結(jié)構(gòu)就可以轉(zhuǎn)化成圖論中的圖,子結(jié)構(gòu)檢索問(wèn)題就轉(zhuǎn)化成為圖論中的子圖同構(gòu)問(wèn)題.子圖同構(gòu)是非確定多項(xiàng)式時(shí)間完全問(wèn)題(NPC),即沒(méi)有方法可以在合理的時(shí)間內(nèi)(多項(xiàng)式時(shí)間)解決它.12算法的時(shí)間消耗是隨節(jié)點(diǎn)(中心原子)數(shù)的增加呈指數(shù)級(jí)增長(zhǎng)的,可以想象,對(duì)于包含大量原子的無(wú)機(jī)晶體結(jié)構(gòu)而言,傳統(tǒng)的子圖同構(gòu)算法是難以實(shí)際應(yīng)用的.

很多研究嘗試將子圖同構(gòu)算法的復(fù)雜程度降至可以實(shí)際應(yīng)用的程度,主要的算法包括Ullmann算法、13SD算法、14Nauty算法、15VF算法16和VF2算法17等.其中,VF2算法是在VF算法的基礎(chǔ)上發(fā)展起來(lái)的,和VF算法相比,VF2算法成功地將空間復(fù)雜度從O(N2)降到了O(N),其中N為圖中的節(jié)點(diǎn)數(shù).特別是在規(guī)則圖(每個(gè)節(jié)點(diǎn)都具有相同數(shù)目鄰接節(jié)點(diǎn)的圖)和大圖(節(jié)點(diǎn)數(shù)大于600的圖)的同構(gòu)計(jì)算中,VF2算法具有比其他算法更高的性能.1,18-21因?yàn)闊o(wú)機(jī)晶體的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)絕大多數(shù)屬于規(guī)則圖和大圖,所以我們采用VF2子圖同構(gòu)算法作為子結(jié)構(gòu)檢索方法的基礎(chǔ).

VF2算法是一種深度優(yōu)先的回溯算法,算法的高效性得益于采用了狀態(tài)空間表示(SSR)的方法和減少搜索空間的一些匹配規(guī)則.16

圖1為檢索圖(Q)和目標(biāo)圖(T)示意圖.如圖1所示,假設(shè)要查詢(xún)的圖Q中有N1個(gè)節(jié)點(diǎn),目標(biāo)圖T中有N2個(gè)節(jié)點(diǎn),N1≤N2.M是Q和T之間的映射,包含點(diǎn)對(duì)(q,t),其中,q∈Q,t∈T,M?N1×N2.狀態(tài)空間S是M的一個(gè)子集,用于存儲(chǔ)圖Q和圖T的局部匹配.點(diǎn)對(duì)(qi,ti)是否可以加入S,取決于其是否滿(mǎn)足匹配規(guī)則.在這里,我們規(guī)定點(diǎn)對(duì)(qi,ti)加入S的規(guī)則是:(1)qi與ti的類(lèi)型要一致;(2)對(duì)于S中任一已有的點(diǎn)對(duì)(qi-1,ti-1),如果qi與qi-1相連,則ti和ti-1必須相連;(3)ti的鄰接節(jié)點(diǎn)數(shù)要小于或等于qi的鄰接節(jié)點(diǎn)數(shù).

圖1 檢索圖(Q)和目標(biāo)圖(T)示意圖Fig.1 Diagrams of query graph(Q)and target graph(T)

狀態(tài)空間S的初值S0為空.從查詢(xún)圖Q中選擇任意一個(gè)未訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)q1,在目標(biāo)圖T中尋找當(dāng)前這一輪未被訪(fǎng)問(wèn)過(guò)的且滿(mǎn)足匹配規(guī)則的對(duì)應(yīng)節(jié)點(diǎn).如果Q中的第一個(gè)節(jié)點(diǎn)q1沒(méi)有在T中找到對(duì)應(yīng)的節(jié)點(diǎn),則Q不是T的子圖;如果能找到這樣的節(jié)點(diǎn)t1,就將點(diǎn)對(duì)(q1,t1)放入狀態(tài)空間S中,然后從節(jié)點(diǎn)q1在Q中的后繼節(jié)點(diǎn)集(與節(jié)點(diǎn)q相連的節(jié)點(diǎn)集合)中選擇一個(gè)節(jié)點(diǎn)q2,再?gòu)墓?jié)點(diǎn)t1在T中的后繼節(jié)點(diǎn)集(與節(jié)點(diǎn)t1相連的節(jié)點(diǎn)集合)中尋找滿(mǎn)足匹配規(guī)則的對(duì)應(yīng)節(jié)點(diǎn).如果成功找到對(duì)應(yīng)節(jié)點(diǎn)t2,則將點(diǎn)對(duì)(q2, t2)放入到狀態(tài)空間S中;如果找不到就回溯到上一輪,開(kāi)始新的查找.當(dāng)狀態(tài)空間S中有N1個(gè)點(diǎn)對(duì)時(shí),表明圖Q是圖T的子圖,輸出結(jié)果.

因?yàn)闊o(wú)機(jī)晶體結(jié)構(gòu)中包含的節(jié)點(diǎn)數(shù)是非常龐大的,直接采用VF2算法對(duì)無(wú)機(jī)晶體結(jié)構(gòu)進(jìn)行檢索仍然是不現(xiàn)實(shí)的.在此基礎(chǔ)上,根據(jù)無(wú)機(jī)晶體材料的結(jié)構(gòu)特點(diǎn),我們?cè)赩F2算法的基礎(chǔ)上做了兩個(gè)重要的改進(jìn)以提高檢索效率.

(1)利用晶體結(jié)構(gòu)的對(duì)稱(chēng)性.在進(jìn)行匹配前,分別將待檢子結(jié)構(gòu)片段(查詢(xún)圖Q)和目標(biāo)晶體結(jié)構(gòu)片段(目標(biāo)圖T)中的晶體學(xué)獨(dú)立或不對(duì)稱(chēng)的原子(節(jié)點(diǎn))移至相應(yīng)圖的頂部.在進(jìn)行子圖匹配時(shí),檢驗(yàn)Q中是否有與T中晶體學(xué)獨(dú)立節(jié)點(diǎn)相匹配的獨(dú)立節(jié)點(diǎn),如果沒(méi)有找到滿(mǎn)足匹配規(guī)則的節(jié)點(diǎn),就可以認(rèn)為待檢結(jié)構(gòu)不是目標(biāo)結(jié)構(gòu)的子結(jié)構(gòu),而并不需要遍歷待查詢(xún)的子結(jié)構(gòu)及目標(biāo)結(jié)構(gòu)中的所有節(jié)點(diǎn),從而大大提高計(jì)算的效率.

(2)采用編碼預(yù)篩選方法.由于子圖匹配算法的計(jì)算量非常大,因此如果在進(jìn)行子圖匹配之前能夠預(yù)篩選掉大量確定無(wú)效的數(shù)據(jù)而僅保留少量有可能符合檢索條件的數(shù)據(jù),將極大提高子結(jié)構(gòu)檢索的效率.為此,我們?cè)O(shè)計(jì)了一個(gè)具有特定位數(shù)的二進(jìn)制編碼,編碼中的每一位對(duì)應(yīng)一種特定的構(gòu)筑基元.以無(wú)機(jī)微孔分子篩晶體結(jié)構(gòu)為例來(lái)說(shuō),我們采用了一個(gè)19位的二進(jìn)制編碼,編碼中的每一位代表了19種在分子篩結(jié)構(gòu)中最常見(jiàn)的構(gòu)筑基元22(表1),編碼中每一位的值1或0代表該結(jié)構(gòu)中含有或不含有指定的構(gòu)筑基元.在進(jìn)行子圖匹配計(jì)算之前,我們先通過(guò)計(jì)算機(jī)程序把待查詢(xún)的子結(jié)構(gòu)和目標(biāo)結(jié)構(gòu)分別轉(zhuǎn)換成編碼(如圖2所示),然后對(duì)比編碼中相應(yīng)位上的值,如果待查詢(xún)子結(jié)構(gòu)編碼中的某一位顯示含有某個(gè)特定的構(gòu)筑基元而目標(biāo)結(jié)構(gòu)編碼顯示不含有,說(shuō)明待查詢(xún)子結(jié)構(gòu)中包含目標(biāo)結(jié)構(gòu)中所不包含的構(gòu)筑基元,因此可以直接判定目標(biāo)結(jié)構(gòu)不包含待查詢(xún)的子結(jié)構(gòu);如果待查詢(xún)的子結(jié)構(gòu)中所有的構(gòu)筑基元在目標(biāo)結(jié)構(gòu)編碼中都顯示含有,則說(shuō)明目標(biāo)結(jié)構(gòu)有可能包含待查詢(xún)的子結(jié)構(gòu),需要進(jìn)一步通過(guò)子圖匹配計(jì)算以確定兩者是否具有包含關(guān)系.對(duì)于僅包含少量目標(biāo)結(jié)構(gòu)的數(shù)據(jù)庫(kù)而言,編碼預(yù)篩選的優(yōu)越性并不明顯.隨著數(shù)據(jù)庫(kù)中目標(biāo)結(jié)構(gòu)數(shù)量的增加,編碼預(yù)篩選的優(yōu)越性將迅速顯現(xiàn)出來(lái).需要強(qiáng)調(diào)的是,目標(biāo)結(jié)構(gòu)的編碼轉(zhuǎn)換是在子結(jié)構(gòu)檢索之前完成并保存的,并不占用子圖匹配計(jì)算的時(shí)間.

表1 19個(gè)分子篩結(jié)構(gòu)編碼中各位所代表的構(gòu)筑基元Table 1 Prescreening code for 19 zeolite structure building units

圖2 結(jié)構(gòu)編碼Fig.2 Structure encoding

3 結(jié)果與討論

我們以在分子篩晶體結(jié)構(gòu)中檢索特定的子結(jié)構(gòu)為例測(cè)試這種方法的效率.數(shù)據(jù)源采用了國(guó)際分子篩協(xié)會(huì)(IZA)官方網(wǎng)站提供的197種分子篩結(jié)構(gòu)的cif文件.22從每個(gè)結(jié)構(gòu)的cif文件出發(fā),計(jì)算了8個(gè)晶胞內(nèi)容所對(duì)應(yīng)的鄰接矩陣并合并在一起形成結(jié)構(gòu)數(shù)據(jù)庫(kù).選取了一些已知的分子篩構(gòu)筑基元作為待查詢(xún)的子結(jié)構(gòu)片段,在由197種分子篩晶體結(jié)構(gòu)所組成的數(shù)據(jù)庫(kù)中進(jìn)行檢索,并將檢索結(jié)果與分子篩協(xié)會(huì)官方網(wǎng)站提供的手工檢索結(jié)果相對(duì)比,以此檢驗(yàn)我們這種檢索方法的準(zhǔn)確性.在此基礎(chǔ)上,我們又任意定義了一些新的構(gòu)筑基元,進(jìn)一步考察這種結(jié)構(gòu)檢索方法在不同條件下的效率.測(cè)試的硬件環(huán)境是Intel Core2 Duo T9600 2.8 GHz,4 GB DDR2 800 MHz,操作系統(tǒng)為Windows 7 Ultimate SP1 32位,程序開(kāi)發(fā)環(huán)境為ActivePerl 5.12.4.

表2 采用不同策略進(jìn)行子結(jié)構(gòu)檢索所需時(shí)間的比較Table 2 Time needed for substructure search by different approaches

選取的已知分子篩構(gòu)筑基元包括lov、nat、vsv、bre、bea等,22部分測(cè)試結(jié)果列在表2中.國(guó)際分子篩協(xié)會(huì)經(jīng)過(guò)人工分析,在其官方數(shù)據(jù)庫(kù)中給出了這些常見(jiàn)的構(gòu)筑基元在197個(gè)分子篩結(jié)構(gòu)中出現(xiàn)的情況.經(jīng)過(guò)對(duì)比發(fā)現(xiàn),采用我們的子結(jié)構(gòu)檢索方法得到的結(jié)果與國(guó)際分子篩協(xié)會(huì)人工統(tǒng)計(jì)的結(jié)果完全一致.說(shuō)明我們的子結(jié)構(gòu)檢索方法在準(zhǔn)確性上是可靠的.

此外,表2還列出了各種檢索策略所需的CPU時(shí)間，包括單純的VF2檢索、引入對(duì)稱(chēng)性的VF2檢索、采用編碼預(yù)篩選的VF2檢索以及同時(shí)引入對(duì)稱(chēng)性和編碼預(yù)篩選的VF2檢索.盡管這四種策略所得到的檢索結(jié)果完全一致,但檢索效率卻相差較大.單純的VF2算法耗時(shí)非常長(zhǎng),在由197個(gè)結(jié)構(gòu)組成的數(shù)據(jù)庫(kù)中進(jìn)行子結(jié)構(gòu)檢索一般需要1 h以上的CPU時(shí)間.而在引入了對(duì)稱(chēng)性信息之后,檢索消耗的時(shí)間會(huì)降低2-3個(gè)數(shù)量級(jí).從理論上說(shuō),對(duì)稱(chēng)性的引入可以大大降低VF2算法所需遍歷的節(jié)點(diǎn)個(gè)數(shù),因此VF2算法的效率會(huì)得到指數(shù)級(jí)的提升.此外,編碼預(yù)篩選能夠在子圖同構(gòu)計(jì)算之前大幅度縮小目標(biāo)結(jié)構(gòu)的數(shù)量,同樣也可以大幅度提高結(jié)構(gòu)檢索的效率.需要說(shuō)明的是,待檢的結(jié)構(gòu)片段越特殊、越少見(jiàn),編碼預(yù)篩選提升的效率就越高,這個(gè)特性恰恰可以滿(mǎn)足實(shí)際需求.因?yàn)樵趯?shí)際應(yīng)用中,人們往往對(duì)新穎少見(jiàn)的子結(jié)構(gòu)更關(guān)心,更需要在數(shù)據(jù)庫(kù)中挖掘其結(jié)構(gòu)特殊性.我們提出的采用編碼預(yù)篩選的子圖同構(gòu)算法恰恰可以有效地解決這類(lèi)問(wèn)題.引入晶體結(jié)構(gòu)對(duì)稱(chēng)性和編碼預(yù)篩選這兩套方案分別基于不同的原理,因此將這兩種方法同時(shí)結(jié)合在一起,可以將子結(jié)構(gòu)檢索的效率進(jìn)一步提升.從表2的最終結(jié)果可以看出,同時(shí)采用這兩種改進(jìn)方法的檢索策略是效率最高的,對(duì)于簡(jiǎn)單的結(jié)構(gòu)通?？梢栽? s之內(nèi)完成檢索;對(duì)于相對(duì)復(fù)雜的結(jié)構(gòu),檢索時(shí)間會(huì)略有增加,但仍在實(shí)際可接受的范圍內(nèi).

4 結(jié)論

提出了一種針對(duì)無(wú)機(jī)晶體材料的子結(jié)構(gòu)檢索方法.該方法基于子圖同構(gòu)的VF2算法,利用晶體結(jié)構(gòu)的對(duì)稱(chēng)性和編碼預(yù)篩選策略降低結(jié)構(gòu)檢索的復(fù)雜度,可以在無(wú)機(jī)晶體數(shù)據(jù)庫(kù)中快速準(zhǔn)確地檢索包含特定子結(jié)構(gòu)的記錄,為無(wú)機(jī)晶體材料的結(jié)構(gòu)分析提供了重要的研究工具.本文以分子篩結(jié)構(gòu)為例展示了這種結(jié)構(gòu)檢索方法的效率.除此之外,該方法同樣可以用于其他無(wú)機(jī)晶體結(jié)構(gòu)的檢索,包括在假想分子篩結(jié)構(gòu)數(shù)據(jù)庫(kù)、23多配位態(tài)的開(kāi)放骨架結(jié)構(gòu)數(shù)據(jù)庫(kù)、24甚至致密的礦物晶體結(jié)構(gòu)數(shù)據(jù)庫(kù)中進(jìn)行的子結(jié)構(gòu)檢索.采用Perl語(yǔ)言實(shí)現(xiàn)了這種檢索方法,其高度的可移植性使得這種檢索方法可以在絕大多數(shù)計(jì)算機(jī)平臺(tái)上得以實(shí)現(xiàn).

(1) Rijnbeek,M.;Steinbeck,C.J.Cheminf.2009,1,17.

(2) Worlein,M.Extension and Parallelization of a Graph-Mining-Algorithm.Ph.D.Dissertation, Friedrich-Alexander-Universit?t Erlangen-Nürnberg,Germany, 2006.

(3) Meinl,T.;Borgelt,C.;Berthold,M.R.Discriminative Closed Fragment Mining and Perfect Extensions in MoFa.In Frontiers in Artificial Intelligence and Applications;Onaindia,E.,Staab, S.Eds.;IOS Press:Amsterdam,2004;Vol.109,pp 3-14.

(4) Huan,J.;Wang,W.;Prins,J.Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism.In Proceedings of the 3rd IEEE International Conference on Data Mining, Melbourne,FL,USA,Nov 19-22,2003;Wu,X.D.,Tuzhilin, A.,Shavlik,J.Eds.;IEEE Computer Soc.:LosAlamitos,CA, 2003.

(5)Yan,X.F.;Han,J.W.gSpan:Graph-Based Substructure Pattern Mining.In Proceedings of 2002 IEEE International Conference on Data Mining,Maebashi City,Japan,Dec 9-12,2002; Kumark,V.Ed.;IEEE Computer Soc.:LosAlamitos,CA,2002.

(6) Nijssen,S.;Kok,J.N.Electronic Notes in Theoretical Computer Science 2005,127(1),77.

(7) Rahman,S.A.;Bashton,M.;Holliday,G.L.;Schrader,R.; Thornton,J.M.J.Cheminf.2009,1,12.

(8) Sastre,G.;Vidal-Moya,J.A.;Blasco,T.;Rius,J.;Jordá,J.L.; Navarro,M.T.;Rey,F.;Corma,A.Angew.Chem.Int.Edit. 2002,41,4722.

(9) Corma,A.;Rey,F.;Valencia,S.;Jordá,J.L.;Rius,J.Nature Mater.2003,2,493.

(10) Cambridge Structure Database.http://www.ccdc.cam.ac.uk/ products/csd/(accessedAug 30,2011).

(11) Bruno,I.J.;Cole,J.C.;Edgington,P.R.;Kessler,M.K.; MacRae,C.F.;McCabe,P.;Pearson,J.;Taylor,R.Acta Crystallogr.B:Struct.Sci.2002,58,389.

(12) Cook,S.A.The Complexity of Theorem-Proving Procedures.In Proceedings of the Third Annual ACM Symposium on the Theory of Computing,Ohio,USA,May 3-5,1971;Harrison, M.A.,Banerji,R.B.,Ullman,J.D.Eds.;ACM:New York, 1971.

(13) Ullmann,J.R.J.Assoc.Comput.Mach.1976,23,31.

(14) Schmidt,D.C.;Druffel,L.E.J.Assoc.Comput.Mach.1976, 23,433.

(15) McKay,B.D.Congressus Numerantium 1981,30,45.

(16) Cordella,L.P.;Foggia,P.;Sansone,C.;Vento,M.Performance Evaluation of the VF Graph MatchingAlgorithm.In Proceedings of the 10th International Conference on Image Analysis and Processing,Venice,Italy,Sept 27-29,1999; Roberto,G.,Cantoni,V.,Levialdi,S.Eds.;IEEE Computer Society Press:LosAlamitos,1999.

(17) Cordella,L.P.;Foggia,P.;Sansone,C.;Vento,M.IEEE Transactions on Pattern Analysis and Machine Intelligence 2004,26(10),1367.

(18) Su,Z.Q.;Liao,C.Z.;Xie,A.H.;Lu,X.P.;Shi,L.M. Computers and Applied Chemistry 2003,20(5),556.[蘇振強(qiáng),廖晨鐘,謝愛(ài)華,魯先平,石樂(lè)明.計(jì)算機(jī)與應(yīng)用化學(xué), 2003,20(5),556.]

(19) Li,X.;Song,T.T.;He,X.F.Computers and Applied Chemistry 2007,24(11),1551.[李 欣,宋婷婷,何險(xiǎn)峰.計(jì)算機(jī)與應(yīng)用化學(xué),2007,24(11),1551.]

(20) Song,T.T.;He,X.F.;Wen,H.Computers and Applied Chemistry 2008,25(9),1152.[宋婷婷,何險(xiǎn)峰,溫 浩.計(jì)算機(jī)與應(yīng)用化學(xué),2008,25(9),1152.]

(21) Feng,H.J.;Wang,Y.;Zhou,J.L.;Haji,A.Computer Applications and Software 2010,27(10),117. [馮紅君,汪 漪,周俊林,阿吉艾克拜爾·艾薩.計(jì)算機(jī)與應(yīng)用軟件, 2010,27(10),117.]

(22) The Database of Zeolite Structures.http://www.iza-structure.org (accessedAug 30,2011).

(23) Li,Y.;Yu,J.H.;Xu,R.R.Hypothetical Zeolite Database.http:// mezeopor.jlu.edu.cn/hypo/(accessedAug 30,2011).

(24) Li,Y.;Yu,J.H.;Xu,R.R.AlPO Database.http://mezeopor.jlu. edu.cn/alpo/(accessedAug 30,2011).

November 17,2011;Revised:December 27,2011;Published on Web:January 4,2012.?

.Email:yili@jlu.edu.cn;Tel:+86-431-85168609.

A Computational Method for Specified Substructure Search in Inorganic Crystal Structures

HUO Wei-Feng1LI Yi1,*LU Jun-Ran1YU Ji-Hong1XU Ru-Ren1LI Jing2
(1State Key Laboratory of Inorganic Synthesis and Preparative Chemistry,Jilin University,Changchun 130012,P.R.China;2Department of Applied Mechanics,University of Science and Technology Beijing,Beijing 100083,P.R.China)

In this paper,a computational method for the substructure search in inorganic crystal structures is proposed.This method is based on the VF2 subgraph isomorphism algorithm.Furthermore, two additional approaches have been introduced into this method to improve the calculation efficiency of VF2:(1)introduction of crystal symmetry information with a view to avoiding redundant calculations among equivalent nodes(atoms);(2)a prescreening encoding treatment to enhance the calculation efficiency by greatly reducing the number of target structures.We tested the efficiency of this method by searching the zeolite crystal structure database from the International Zeolite Association for entries containing specified building units.The test results showed that this method could quickly and correctly retrieve all the entries containing the queried substructure in the zeolite structure database.The introduction of crystal symmetry information and the prescreening encoding treatment greatly reduce the complexity of substructure search. The search speed was significantly enhanced by at least 3-5 orders of magnitude.This method was developed using Perl programming language,ensuring that this method could be easily applied to various platforms.

Inorganic crystal structure;Database;Substructure search;VF2 algorithm;Zeolite; Building unit

10.3866/PKU.WHXB201201041

O641

The project was supported by the National Natural Science Foundation of China(21001049).

國(guó)家自然科學(xué)基金(21001049)資助項(xiàng)目