Citation: HUO Wei-Feng, LI Yi, LU Jun-Ran, YU Ji-Hong, XU Ru-Ren, LI Jing. A Computational Method for Specified Substructure Search in Inorganic Crystal Structures[J]. Acta Physico-Chimica Sinica, ;2012, 28(03): 536-540. doi: 10.3866/PKU.WHXB201201041 shu

A Computational Method for Specified Substructure Search in Inorganic Crystal Structures

HUO Wei-Feng ¹ ,
LI Yi ^1, ,
LU Jun-Ran ¹ ,
YU Ji-Hong ¹ ,
XU Ru-Ren ¹ ,
LI Jing ²

1.
1. State Key Laboratory of Inorganic Synthesis and Preparative Chemistry, Jilin University, Changchun 130012, P. R. China;
2. Department of Applied Mechanics, University of Science and Technology Beijing, Beijing 100083, P. R. China

Received Date: 17 November 2011
Available Online: 4 January 2012
Fund Project: 国家自然科学基金(21001049)资助项目 (21001049)

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 al rithm. 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 al rithm,
- Zeolite,
- Building unit
1. [1]
  (1) Rijnbeek, M.; Steinbeck, C. J. Cheminf. 2009, 1, 17.
2. [2]
  (2) Worlein, M. Extension and Parallelization of a Graph-Mining-Al rithm. Ph.D. Dissertation, Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany, 2006.
3. [3]
  (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. [4]
  (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.: Los Alamitos, CA, 2003.
5. [5]
  (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.: Los Alamitos, CA, 2002.
6. [6]
  (6) Nijssen, S.; Kok, J. N. Electronic Notes in Theoretical Computer Science 2005, 127 (1), 77.
7. [7]
  (7) Rahman, S. A.; Bashton, M.; Holliday, G. L.; Schrader, R.; Thornton, J. M. J. Cheminform. 2009, 1, 12.
8. [8]
  (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. [9]
  (9) Corma, A.; Rey, F.; Valencia, S.; Jordá, J. L.; Rius, J. Nature Mater. 2003, 2, 493.
10. [10]
  (10) Cambridge Structure Database. http://www.ccdc.cam.ac.uk/ products/csd/ (accessed Aug 30, 2011).
11. [11]
  (11) Bruno, I. J.; Cole, J. C.; Edgington, P. R.; Kessler, M. K.; MacRae, C. F.; McCabe, P.; Pearson, J.; Taylor, R. Acta Crystallogr., Sect. B: Struct. Sci. 2002, 58, 389.
12. [12]
  (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. [13]
  (13) Ullmann, J. R. J. Assoc. Comput. Mach. 1976, 23, 31.
14. [14]
  (14) Schmidt, D. C.; Druffel, L. E. J. Assoc. Comput. Mach. 1976, 23, 433.
15. [15]
  (15) McKay, B. D. Congressus Numerantium 1981, 30, 45.
16. [16]
  (16) Cordella, L. P.; Foggia, P.; Sansone, C.; Vento, M. Performance Evaluation of the VF Graph Matching Al rithm. 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: Los Alamitos, 1999.
17. [17]
  (17) Cordella, L. P.; Foggia, P.; Sansone, C.; Vento, M. IEEE Transactions on Pattern Analysis and Machine Intelligence 2004, 26 (10), 1367.
18. [18]
  (18) Su, Z. Q.; Liao, C. Z.; Xie, A. H.; Lu, X. P.; Shi, L. M. Computers and Applied Chemistry 2003, 20 (5), 556. [苏振强, 廖晨钟, 谢爱华, 鲁先平, 石乐明. 计算机与应用化学, 2003, 20 (5), 556.]
19. [19]
  (19) Li, X.; Song, T. T.; He, X. F. Computers and Applied Chemistry 2007, 24 (11), 1551. [李欣, 宋婷婷, 何险峰. 计算机与应用化学, 2007, 24 (11), 1551.]
20. [20]
  (20) Song, T. T.; He, X. F.;Wen, H. Computers and Applied Chemistry 2008, 25 (9), 1152. [宋婷婷, 何险峰, 温浩. 计算机与应用化学, 2008, 25 (9), 1152.]
21. [21]
  (21) Feng, H. J.;Wang, Y.; Zhou, J. L.; Haji, A. Computer Applications and Software 2010, 27 (10), 117. [冯红君, 汪漪, 周俊林, 阿吉艾克拜尔·艾萨. 计算机与应用软件, 2010, 27 (10), 117.]
22. [22]
  (22) The Database of Zeolite Structures. http://www.iza-structure.org (accessed Aug 30, 2011).
23. [23]
  (23) Li, Y.; Yu, J. H.; Xu, R. R. Hypothetical Zeolite Database. http:// mezeopor.jlu.edu.cn/hypo/ (accessed Aug 30, 2011).
24. [24]
  (24) Li, Y.; Yu, J. H.; Xu, R. R. AlPO Database. http://mezeopor.jlu. edu.cn/alpo/ (accessed Aug 30, 2011).
1. [1]
  Yufang GAO , Nan HOU , Yaning LIANG , Ning LI , Yanting ZHANG , Zelong LI , Xiaofeng LI . Nano-thin layer MCM-22 zeolite: Synthesis and catalytic properties of trimethylbenzene isomerization reaction. Chinese Journal of Inorganic Chemistry, 2024, 40(6): 1079-1087. doi: 10.11862/CJIC.20240036
2. [2]
  Yuhao SUN , Qingzhe DONG , Lei ZHAO , Xiaodan JIANG , Hailing GUO , Xianglong MENG , Yongmei GUO . Synthesis and antibacterial properties of silver-loaded sod-based zeolite. Chinese Journal of Inorganic Chemistry, 2024, 40(4): 761-770. doi: 10.11862/CJIC.20230169
3. [3]
  Haitang WANG , Yanni LING , Xiaqing MA , Yuxin CHEN , Rui ZHANG , Keyi WANG , Ying ZHANG , Wenmin WANG . Construction, crystal structures, and biological activities of two Ln^Ⅲ₃ complexes. Chinese Journal of Inorganic Chemistry, 2024, 40(8): 1474-1482. doi: 10.11862/CJIC.20240188
4. [4]
  Qi Li , Pingan Li , Zetong Liu , Jiahui Zhang , Hao Zhang , Weilai Yu , Xianluo Hu . Fabricating Micro/Nanostructured Separators and Electrode Materials by Coaxial Electrospinning for Lithium-Ion Batteries: From Fundamentals to Applications. Acta Physico-Chimica Sinica, 2024, 40(10): 2311030-. doi: 10.3866/PKU.WHXB202311030
5. [5]
  Yong Shu , Xing Chen , Sai Duan , Rongzhen Liao . How to Determine the Equilibrium Bond Distance of Homonuclear Diatomic Molecules: A Case Study of H₂. University Chemistry, 2024, 39(7): 386-393. doi: 10.3866/PKU.DXHX202310102
6. [6]
  Wenyan Dan , Weijie Li , Xiaogang Wang . The Technical Analysis of Visual Software ShelXle for Refinement of Small Molecular Crystal Structure. University Chemistry, 2024, 39(3): 63-69. doi: 10.3866/PKU.DXHX202302060
7. [7]
  Xin MA , Ya SUN , Na SUN , Qian KANG , Jiajia ZHANG , Ruitao ZHU , Xiaoli GAO . A Tb₂ complex based on polydentate Schiff base: Crystal structure, fluorescence properties, and biological activity. Chinese Journal of Inorganic Chemistry, 2024, 40(7): 1347-1356. doi: 10.11862/CJIC.20230357
8. [8]
  Jin Tong , Shuyan Yu . Crystal Engineering for Supramolecular Chirality. University Chemistry, 2024, 39(3): 86-93. doi: 10.3866/PKU.DXHX202308113
9. [9]
  Zhaoyang WANG , Chun YANG , Yaoyao Song , Na HAN , Xiaomeng LIU , Qinglun WANG . Lanthanide(Ⅲ) complexes derived from 4′-(2-pyridyl)-2, 2′∶6′, 2″-terpyridine: Crystal structures, fluorescent and magnetic properties. Chinese Journal of Inorganic Chemistry, 2024, 40(8): 1442-1451. doi: 10.11862/CJIC.20240114
10. [10]
  Yan Liu , Yuexiang Zhu , Luhua Lai . Introduction to Blended and Small-Class Teaching in Structural Chemistry: Exploring the Structure and Properties of Crystals. University Chemistry, 2024, 39(3): 1-4. doi: 10.3866/PKU.DXHX202306084
11. [11]
  Liang MA , Honghua ZHANG , Weilu ZHENG , Aoqi YOU , Zhiyong OUYANG , Junjiang CAO . Construction of highly ordered ZIF-8/Au nanocomposite structure arrays and application of surface-enhanced Raman spectroscopy. Chinese Journal of Inorganic Chemistry, 2024, 40(9): 1743-1754. doi: 10.11862/CJIC.20240075
12. [12]
  Liyang ZHANG , Dongdong YANG , Ning LI , Yuanyu YANG , Qi MA . Crystal structures, luminescent properties and Hirshfeld surface analyses of three cadmium(Ⅱ) complexes based on 2-(3-(pyridin-2-yl)-1H-pyrazol-1-yl)benzoate. Chinese Journal of Inorganic Chemistry, 2024, 40(10): 1943-1952. doi: 10.11862/CJIC.20240079
13. [13]
  Dongju Zhang . Exploring the Descriptions and Connotations of Basic Concepts of Teaching Crystal Structures. University Chemistry, 2024, 39(3): 18-22. doi: 10.3866/PKU.DXHX202304003
14. [14]
  Weina Wang , Fengyi Liu , Wenliang Wang . “Extracting Commonality, Delving into Typicals, Deriving Individuality”: Constructing a Knowledge Graph of Crystal Structures. University Chemistry, 2024, 39(3): 36-42. doi: 10.3866/PKU.DXHX202308029
15. [15]
  Junqiao Zhuo , Xinchen Huang , Qi Wang . Symbol Representation of the Packing-Filling Model of the Crystal Structure and Its Application. University Chemistry, 2024, 39(3): 70-77. doi: 10.3866/PKU.DXHX202311100
16. [16]
  Hongwei Ma , Hui Li . Three Methods for Structure Determination from Powder Diffraction Data. University Chemistry, 2024, 39(3): 94-102. doi: 10.3866/PKU.DXHX202310035
17. [17]
  Min WANG , Dehua XIN , Yaning SHI , Wenyao ZHU , Yuanqun ZHANG , Wei ZHANG . Construction and full-spectrum catalytic performance of multilevel Ag/Bi/nitrogen vacancy g-C₃N₄/Ti₃C₂T_x Schottky junction. Chinese Journal of Inorganic Chemistry, 2024, 40(6): 1123-1134. doi: 10.11862/CJIC.20230477
18. [18]
  Yuqiao Zhou , Weidi Cao , Shunxi Dong , Lili Lin , Xiaohua Liu . Study on the Teaching Reformation of Practical X-ray Crystallography. University Chemistry, 2024, 39(3): 23-28. doi: 10.3866/PKU.DXHX202303003
19. [19]
  Linhan Tian , Changsheng Lu . Discussion on Sextuple Bonding in Diatomic Motifs of Chromium Family Elements. University Chemistry, 2024, 39(8): 395-402. doi: 10.3866/PKU.DXHX202401056
20. [20]
  Kai Yang , Gehua Bi , Yong Zhang , Delin Jin , Ziwei Xu , Qian Wang , Lingbao Xing . Comprehensive Polymer Chemistry Experiment Design: Preparation and Characterization of Rigid Polyurethane Foam Materials. University Chemistry, 2024, 39(4): 206-212. doi: 10.3866/PKU.DXHX202308045

Get Citation

PDF

XML

Metrics

PDF Downloads(857)
Abstract views(2164)
HTML views(43)

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142