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]
  Pei Li , Yuenan Zheng , Zhankai Liu , An-Hui Lu . Boron-Containing MFI Zeolite: Microstructure Control and Its Performance of Propane Oxidative Dehydrogenation. Acta Physico-Chimica Sinica, 2025, 41(4): 100034-. doi: 10.3866/PKU.WHXB202406012
2. [2]
  Shanghua Li , Malin Li , Xiwen Chi , Xin Yin , Zhaodi Luo , Jihong Yu . 基于高离子迁移动力学的取向ZnQ分子筛保护层实现高稳定水系锌金属负极的构筑. Acta Physico-Chimica Sinica, 2025, 41(1): 2309003-. doi: 10.3866/PKU.WHXB202309003
3. [3]
  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
4. [4]
  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
5. [5]
  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
6. [6]
  Jiali CHEN , Guoxiang ZHAO , Yayu YAN , Wanting XIA , Qiaohong LI , Jian ZHANG . Machine learning exploring the adsorption of electronic gases on zeolite molecular sieves. Chinese Journal of Inorganic Chemistry, 2025, 41(1): 155-164. doi: 10.11862/CJIC.20240408
7. [7]
  Yiping HUANG , Liqin TANG , Yufan JI , Cheng CHEN , Shuangtao LI , Jingjing HUANG , Xuechao GAO , Xuehong GU . Hollow fiber NaA zeolite membrane for deep dehydration of ethanol solvent by vapor permeation. Chinese Journal of Inorganic Chemistry, 2025, 41(2): 225-234. doi: 10.11862/CJIC.20240224
8. [8]
  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
9. [9]
  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
10. [10]
  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
11. [11]
  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
12. [12]
  Jin Tong , Shuyan Yu . Crystal Engineering for Supramolecular Chirality. University Chemistry, 2024, 39(3): 86-93. doi: 10.3866/PKU.DXHX202308113
13. [13]
  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
14. [14]
  . . Chinese Journal of Inorganic Chemistry, 2024, 40(11): 0-0.
15. [15]
  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
16. [16]
  Bowen Yang , Rui Wang , Benjian Xin , Lili Liu , Zhiqiang Niu . C-SnO₂/MWCNTs Composite with Stable Conductive Network for Lithium-based Semi-Solid Flow Batteries. Acta Physico-Chimica Sinica, 2025, 41(2): 100015-. doi: 10.3866/PKU.WHXB202310024
17. [17]
  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
18. [18]
  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
19. [19]
  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
20. [20]
  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

Get Citation

PDF

XML

Metrics

PDF Downloads(857)
Abstract views(2228)
HTML views(58)

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

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