化學結(jié)構二維子結(jié)構檢索的開發(fā)

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

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

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

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

5、的原子原子、 鍵鍵的逐一比較， 而且這種方法已被證明是一種 NP(Nondeterministic Polynomial完全問題8，即是一種非常耗時的 工作，并且匹配時間隨著輸入的提問藥效團原子數(shù)目的增加而迅速增加. 因此，必須尋找一種高 效可行的搜索算法來解決這個矛盾. VF 算法是用于圖的同構及子圖匹配問題的回溯算法， 它是一種不針對特定對象的通配圖算法. 本文把這種思想應用于化學領域分子結(jié)構的二維子結(jié)構檢索. VF 算法對圖形采用了深度優(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 的思想，其匹配過程如下8： 3 子結(jié)構匹配的實現(xiàn) 子結(jié)構檢索的實現(xiàn)分為 4 個模塊：結(jié)構讀取模塊、信息存儲模塊、匹配模塊和結(jié)果輸出模塊. 由于使用了面向?qū)ο蟮脑O計思想，4 個模塊之間相互獨立，所以代碼可重復利用率高，可以方便 地嵌入到其它系統(tǒng)中. 3.1 結(jié)構讀取模塊 二維化學結(jié)構數(shù)據(jù)庫的描述主要有連接表和 線性編碼兩種方法. 前者不僅可以描述原子及其 鍵的關系，還可以表達原子的空間坐標，常用的 文件格式有 MDL 信息系統(tǒng)公司(MDL Information System 的

8、 MOL10 文 件 格 式 、 TRIPOS 公 司 的 MOL211文件格式、以及 CML(Chemical Markup Language，化學標記語言1112文件格式. 后者主 要用字符串描述化學結(jié)構信息，它的存儲空間遠 遠小于連接表，但不能描述原子的空間坐標，也 不能保證分子描述的唯一性，比較重要的有 圖 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期 劉冰等：化學結(jié)構二維子結(jié)構檢索的開發(fā) 378 Wisweser line notation(WLN和 Simplified Molecular Input LinE System(SMILES. 鑒于連接表可以保證分子結(jié)構描述的唯一性，以及方便地顯示分子各結(jié)點的坐標，提問分子 的結(jié)構描述采用 MDL 公司的 MOL 文件格式(MolReader 類，目標數(shù)據(jù)庫也使用該公司的 SDF 數(shù) 據(jù)庫格式(SdfReader 類. 表 1 是圖 2 中提問圖 2(a的 MOL 文件. 表 1 提問圖 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 信息存儲模塊 信息存儲模塊主要分鍵性質(zhì)存儲描述、原 子結(jié)點存儲描述、 分子存儲描述 3 部分， 用 (1 Edge 類表達鍵， 主要屬性是相鄰原子序號及鍵 的性質(zhì)Edge(int nToNodeId, int nAttr；(2 用 Node 類表達結(jié)點原子， 主要屬性是原子序號和 原子符號Node(int

12、 nNodeId, CString sAttr以 及 Edge 類鏈表； 用 Molecule 類描述整個分 (3 子結(jié)構， 主要屬性是一個 Node 類鏈表. 圖 4 為 圖 2(a分子信息存儲圖. 3.3 匹配模塊 以提問圖為指導，依次提取數(shù)據(jù)庫中化合 物進行匹配，主要由 VFSubState 類、HashMap 類、Match 類組成. 其中在 Match 類中使用了 回溯算法. 3.4 查詢結(jié)果輸出模塊 成功匹配的分子以其 MOL 文件格式輸出， 由 OutHitMOL 類來完成. 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分子信息存儲圖 Fig.4 The molecular information storage graph o

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

15、合物 結(jié)構數(shù)據(jù)庫進行搜索比較，結(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ù)目及雜原子數(shù)

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

17、芍藥醇 Fig.5 Paeonol 4期 劉冰等：化學結(jié)構二維子結(jié)構檢索的開發(fā) 圖 6 10 個命中化合物 Fig.6 Ten compounds of hit 380 圖中化合物可作為治療麻醉、鎮(zhèn)靜催眠等病癥藥物的先導化合物進行深入研究. 我們還對抗 細胞毒素、抗真菌、抗癌菌素、抗腫瘤等藥效團進行檢索，并與 3DFS 比較，結(jié)果均一致. 參考文獻： 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 算法在化學結(jié)構檢索中的應用 J. 計算機與應用化學, 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.