化學(xué)結(jié)構(gòu)二維子結(jié)構(gòu)檢索的開(kāi)發(fā)

1、第3卷 第4期 2003 年 8 月 過(guò) 程 工 程 學(xué) 報(bào) The Chinese Journal of Process Engineering Vol.3 No.4 Aug. 2003 化學(xué)結(jié)構(gòu)二維子結(jié)構(gòu)檢索的開(kāi)發(fā) 劉 冰, 周家駒 (中國(guó)科學(xué)院過(guò)程工程研究所, 北京 100080 摘 要：將圖形通用匹配 VF 算法應(yīng)用到化學(xué)結(jié)構(gòu)子結(jié)構(gòu)檢索中，用面向?qū)ο蟮姆椒?，?shí)現(xiàn)了化 學(xué)結(jié)構(gòu)數(shù)據(jù)庫(kù)中二維子結(jié)構(gòu)檢索功能，程序各模塊之間相互獨(dú)立、可移植性強(qiáng)、健壯性好. 通過(guò)與 3DFS 比較，結(jié)果正確，適于處理大型化學(xué)結(jié)構(gòu)數(shù)據(jù)庫(kù)，現(xiàn)已應(yīng)用于中藥數(shù)據(jù)庫(kù)系統(tǒng)藥物先導(dǎo)化合 物的發(fā)現(xiàn). 關(guān)鍵詞：二維子結(jié)構(gòu)檢索；子結(jié)

2、構(gòu)匹配；VF 算法；面向?qū)ο?中圖分類號(hào)：O6-39 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009606X(200304037605 1 前 言 二維子結(jié)構(gòu)檢索對(duì)于創(chuàng)新藥物先導(dǎo)化合物的發(fā)現(xiàn)， 化學(xué)數(shù)據(jù)庫(kù)的數(shù)據(jù)挖掘(Data mining和知識(shí) 發(fā)現(xiàn)(Knowledge discovering in database工作都有著重要的意義. 它在化學(xué)結(jié)構(gòu)數(shù)據(jù)庫(kù)的應(yīng)用中扮 演著重要角色. 目前，已經(jīng)有多種算法用于解決二維子結(jié)構(gòu)檢索問(wèn)題. 例如 1957 年提出的 Ray and Kirsch 算 法， 1965 年提出的 Sussenguth 算法， 1972 年提出的 Figueras 算法， 1976 年

3、提出的 Ullmann 算法1， 1984 年提出的 von Scholley 算法，以及 1989 年提出的 GMA 算法2,3(只針對(duì)化學(xué)結(jié)構(gòu)，1992 年提 出的 Brown 算法4,5和 1996 年提出的 VF 算法68(通用算法等. 1995 年之前，Ullmann 算法被公認(rèn)為是執(zhí)行效率最高的子結(jié)構(gòu)匹配算法，而后來(lái)的 VF 通用 算法則實(shí)現(xiàn)了比 Ullmann 算法更高的執(zhí)行效率和較低的復(fù)雜度9. 本文用 C+編程開(kāi)發(fā)了通用 VF 算法對(duì)化學(xué)子結(jié)構(gòu)的檢索. 2 VF 算法 化學(xué)子結(jié)構(gòu)匹配不同于普通的圖形匹配方法，它不僅存在結(jié)點(diǎn)屬性的區(qū)別(如 C, N, O, S 原子 等，邊的屬

4、性亦有差異(如單鍵、雙鍵、三鍵等. 在圖 1 和圖 2 中，(a分別是(b的子圖, 很明顯， 圖 2 較圖 1 復(fù)雜度高許多. O O O (a (b (a (b 圖 1 普通無(wú)向圖 Fig.1 The general undirected graph 收稿日期：20030120, 修回日期：20030310 作者簡(jiǎn)介：劉冰(1976, 女, 山東省濰坊市人, 博士研究生, 計(jì)算機(jī)化學(xué)專業(yè). 圖 2 化學(xué)結(jié)構(gòu)示意圖 Fig.2 The graph of chemical structure 4期 劉冰等：化學(xué)結(jié)構(gòu)二維子結(jié)構(gòu)檢索的開(kāi)發(fā) 377 化學(xué)子結(jié)構(gòu)匹配只能是提問(wèn)藥效團(tuán)分子和數(shù)據(jù)庫(kù)中目標(biāo)分子

5、的原子原子、 鍵鍵的逐一比較， 而且這種方法已被證明是一種 NP(Nondeterministic Polynomial完全問(wèn)題8，即是一種非常耗時(shí)的 工作，并且匹配時(shí)間隨著輸入的提問(wèn)藥效團(tuán)原子數(shù)目的增加而迅速增加. 因此，必須尋找一種高 效可行的搜索算法來(lái)解決這個(gè)矛盾. VF 算法是用于圖的同構(gòu)及子圖匹配問(wèn)題的回溯算法， 它是一種不針對(duì)特定對(duì)象的通配圖算法. 本文把這種思想應(yīng)用于化學(xué)領(lǐng)域分子結(jié)構(gòu)的二維子結(jié)構(gòu)檢索. VF 算法對(duì)圖形采用了深度優(yōu)先遍歷 PROCEDURE Match(s INPUT: an intermediate state s; the initial state s0 h

6、as M(s0 = OUTPUT: the mappings between the two graphs IF M(s covers all the nodes THEN OUTPUT M(s ELSE Compute the set P(s of the pairs candidate for inclusion in M(s FOREACH p P(s IF the feasibility rules succeed for the inclusion of pin M(s THEN Compute the state s' obtained by adding p to M(s

7、 CALL Match(s' END IF END FOREACH END IF END PROCEDURE 的思想，其匹配過(guò)程如下8： 3 子結(jié)構(gòu)匹配的實(shí)現(xiàn) 子結(jié)構(gòu)檢索的實(shí)現(xiàn)分為 4 個(gè)模塊：結(jié)構(gòu)讀取模塊、信息存儲(chǔ)模塊、匹配模塊和結(jié)果輸出模塊. 由于使用了面向?qū)ο蟮脑O(shè)計(jì)思想，4 個(gè)模塊之間相互獨(dú)立，所以代碼可重復(fù)利用率高，可以方便 地嵌入到其它系統(tǒng)中. 3.1 結(jié)構(gòu)讀取模塊 二維化學(xué)結(jié)構(gòu)數(shù)據(jù)庫(kù)的描述主要有連接表和 線性編碼兩種方法. 前者不僅可以描述原子及其 鍵的關(guān)系，還可以表達(dá)原子的空間坐標(biāo)，常用的 文件格式有 MDL 信息系統(tǒng)公司(MDL Information System 的

8、 MOL10 文 件 格 式 、 TRIPOS 公 司 的 MOL211文件格式、以及 CML(Chemical Markup Language，化學(xué)標(biāo)記語(yǔ)言1112文件格式. 后者主 要用字符串描述化學(xué)結(jié)構(gòu)信息，它的存儲(chǔ)空間遠(yuǎn) 遠(yuǎn)小于連接表，但不能描述原子的空間坐標(biāo)，也 不能保證分子描述的唯一性，比較重要的有 圖 3 模塊示意圖 Fig.3 Module sketch map Hit results OutHitMol Matching VFSubState HashMap Match Structure reading MolReader SdfReader Information sav

9、ing Edge Node Molecule 4期 劉冰等：化學(xué)結(jié)構(gòu)二維子結(jié)構(gòu)檢索的開(kāi)發(fā) 378 Wisweser line notation(WLN和 Simplified Molecular Input LinE System(SMILES. 鑒于連接表可以保證分子結(jié)構(gòu)描述的唯一性，以及方便地顯示分子各結(jié)點(diǎn)的坐標(biāo)，提問(wèn)分子 的結(jié)構(gòu)描述采用 MDL 公司的 MOL 文件格式(MolReader 類，目標(biāo)數(shù)據(jù)庫(kù)也使用該公司的 SDF 數(shù) 據(jù)庫(kù)格式(SdfReader 類. 表 1 是圖 2 中提問(wèn)圖 2(a的 MOL 文件. 表 1 提問(wèn)圖 2(a的 MOL 文件 Table 1 The MO

10、L file of 2 (a in Fig.2 ISIS 6 03040322022D 0 0 5.8291 6.6565 5.8255 5.4164 6.6560 7.0672 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0999 V2000 0.0000 C 0 0 0.0000 C 0 0 0.0000 C 0 0 0.0000 C 0 0 0.0000 C 0 0 0.0000 O 0 0 5 1 3 4 2 5 M 6 0 4.9611 4.9599 6.3883 5.6729 6.3912 5.6739 3 1 2 2 4 2 1 1 6

11、 1 6 1 END 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3.2 信息存儲(chǔ)模塊 信息存儲(chǔ)模塊主要分鍵性質(zhì)存儲(chǔ)描述、原 子結(jié)點(diǎn)存儲(chǔ)描述、 分子存儲(chǔ)描述 3 部分， 用 (1 Edge 類表達(dá)鍵， 主要屬性是相鄰原子序號(hào)及鍵 的性質(zhì)Edge(int nToNodeId, int nAttr；(2 用 Node 類表達(dá)結(jié)點(diǎn)原子， 主要屬性是原子序號(hào)和 原子符號(hào)Node(int

12、 nNodeId, CString sAttr以 及 Edge 類鏈表； 用 Molecule 類描述整個(gè)分 (3 子結(jié)構(gòu)， 主要屬性是一個(gè) Node 類鏈表. 圖 4 為 圖 2(a分子信息存儲(chǔ)圖. 3.3 匹配模塊 以提問(wèn)圖為指導(dǎo)，依次提取數(shù)據(jù)庫(kù)中化合 物進(jìn)行匹配，主要由 VFSubState 類、HashMap 類、Match 類組成. 其中在 Match 類中使用了 回溯算法. 3.4 查詢結(jié)果輸出模塊 成功匹配的分子以其 MOL 文件格式輸出， 由 OutHitMOL 類來(lái)完成. Node 1 (C Node 2 (C Node 3 (C Node 4 (C Node 5 (C No

13、de 6 (O 2 D 4 S Atom description (class Node Bond description which connects with the node atom (class Edge 1 D 6 S 5 S 4 D 3 D 1 S 3 S 6 S 2 S 5 S S: There is a single bond between two atoms D: There is a double bond between two atoms 圖 4 圖 2(a分子信息存儲(chǔ)圖 Fig.4 The molecular information storage graph o

14、f Fig.2(a 4 程序優(yōu)化 由于子結(jié)構(gòu)匹配中的原子原子比較是一種非常耗時(shí)的過(guò)程， 對(duì)數(shù)據(jù)庫(kù)的分子進(jìn)行初篩可以大 大縮短這一過(guò)程. 本文中采取的措施：(1 原子個(gè)數(shù)初篩. 數(shù)據(jù)庫(kù)中分子的原子個(gè)數(shù)小于提問(wèn)分子 4期 劉冰等：化學(xué)結(jié)構(gòu)二維子結(jié)構(gòu)檢索的開(kāi)發(fā) 379 原子個(gè)數(shù)的將直接被淘汰，而不進(jìn)行匹配運(yùn)算. (2 雜原子起步. 如果分子中含有 N, P, S, O, Cl 等 常用雜原子，則以其中一個(gè)作為匹配的起始原子，這樣可以大大降低回溯的次數(shù)，從而優(yōu)化程序 執(zhí)行效率. 5 效率及正確度檢驗(yàn) 將本文的可執(zhí)行程序與王亭14的 3DFS(三維藥效團(tuán)柔性搜索程序在 NCI3D 的 126,705 化

15、合物 結(jié)構(gòu)數(shù)據(jù)庫(kù)進(jìn)行搜索比較，結(jié)果均一致，特列舉 4 例： Structure OH O Name Pharmacological activities Anti-inflammatory, reduces intestinal vascular permeability and brittleness, antispasmodic 3DFS hit results 12 VF hit results 12 HO O O N Acacetin OH 32 32 (+-Curcuphenol N Antimicrobial 1 1 N 11 11 效率方面，總耗時(shí)隨藥效團(tuán)分子的原子數(shù)目及雜原子數(shù)

16、目的變化而不同. 在賽揚(yáng) 900 MHz CPU，128 M 內(nèi)存主機(jī)條件下，我們的 VF 算法搜索程序從 NCI3D 數(shù)據(jù)庫(kù)中搜索一個(gè)例程大約耗 時(shí)為 16 min. 在提問(wèn)藥效團(tuán)原子數(shù)目較少時(shí)，3DFS 速度略快；而在提問(wèn)藥效團(tuán)原子數(shù)目較多時(shí)， VF 算法占優(yōu)勢(shì). 6 應(yīng)用舉例 圖 5 是我們中藥化學(xué)數(shù)據(jù)庫(kù)中一種名為芍藥醇的化合物，它可以從白 O OH 牡丹、紅花以及桑葉中提取，具有麻醉、抗菌、抗驚厥、抗高血壓以及鎮(zhèn) 靜催眠等多種藥理活性. 以此種芍藥醇為提問(wèn)圖，在總數(shù)目為 9127 種化合物的中藥數(shù)據(jù)庫(kù)中搜 索，共得到 436 個(gè)命中化合物，圖 6 列出了其中的 10 個(gè). O 圖 5

17、芍藥醇 Fig.5 Paeonol 4期 劉冰等：化學(xué)結(jié)構(gòu)二維子結(jié)構(gòu)檢索的開(kāi)發(fā) 圖 6 10 個(gè)命中化合物 Fig.6 Ten compounds of hit 380 圖中化合物可作為治療麻醉、鎮(zhèn)靜催眠等病癥藥物的先導(dǎo)化合物進(jìn)行深入研究. 我們還對(duì)抗 細(xì)胞毒素、抗真菌、抗癌菌素、抗腫瘤等藥效團(tuán)進(jìn)行檢索，并與 3DFS 比較，結(jié)果均一致. 參考文獻(xiàn)： 1 Ullmann J R. An Algorithm for Subgraph Isomorphism J. J. Ass. Comput. Mach., 1976, 23: 3142. 2 Xu Jun. GMA: A Generic Mat

18、ch Algorithm for Structural Homomorphism,Isomorphism, and Maximal Common Substructure Match and Its Application J. J. Chem. Inf. Comput. Sci., 1996, 36: 2534. 3 Wang T, Zhou J J. EMCSS: A New Method for Maximal Common Substructure Search J. J. Chem. Inf. Comput. Sci., 1997, 37: 828834. 4 Brown Rober

19、t D, Downs Geoffrey M, Willett Peter. A Hyperstructure Model for Chemical Structure Handling: Generation and Atom-by-atom Searching of Hyperstructures J. J. Chem. Inf. Comput. Sci., 1992, 32: 522531. 5 Brown Robert D, Gareth Willett Peter. Matching Two-dimensional Chemical Graphs Using Genetic Algor

20、ithms J. J. Chem. Inf. Comput. Sci., 1994, 34: 6370. 6 Cordella L P, Foggia P, Sansone C, et al. An Efficient Algorithm for the Inexact Matching of ARG Graphs Using a Contextual Transformational Model A. Proc. of the 13th International Conference on Pattern Recognition, Vol. III C. Wien Austria: IEE

21、E Computer Society Press, 1996. 180184. 7 Cordella L P, Foggia P, Sansone C, et al. Subgraph Transformations for the Inexact Matching of Attributed Relational Graphs J. Computing, 1998, 12: 4352. 8 Foggia P, Sansone C, Vento M. An Improved Algorithm for Matching Large Graphs A. Proc. the 3rd IAPR-TC

22、15 Workshop on Graph based Representations C. Ischia: Jean-Michel Jolion, 2001. 7280. 9 李琰, 周家駒. VF 算法在化學(xué)結(jié)構(gòu)檢索中的應(yīng)用 J. 計(jì)算機(jī)與應(yīng)用化學(xué), 2002, 19: 575580. 10 Arthur Dalby, James G N, Hounshell W D, et al. Description of Several Chemical Structure File Formats Used by Computer Programs Developed at Molecular D

23、esign Limited J. J. Chem. Inf. Comput. Sci., 1992, 32: 244255. 11 Murray-Rust P, Rzepa H S. Chemical Markup, XML and the Worldwide Web: 1. Basic Principles J. J. Chem. Inf. Comput. Sci., 1999, 39(6: 928942. 12 Murray-Rust P, Rzepa H S. Chemical Markup, XML and the Worldwide Web: 2. Information Objects and the CMLDOM J. J. Chem. Inf. Comput. Sci., 2000, 41(5: 618634. 13 Murray-Rust P, Rzepa H S. Chemical Markup, XML and the Worldwide Web: 3. Toward a Signed Semantic Chemical Web of Trust J. J. Chem. Inf. Comput. Sci., 2001, 41(5: 11241130.