Acta Phys. -Chim. Sin. ›› 2012, Vol. 28 ›› Issue (03): 536-540.doi: 10.3866/PKU.WHXB201201041


A Computational Method for Specified Substructure Search in Inorganic Crystal Structures

HUO Wei-Feng1, LI Yi1, LU Jun-Ran1, YU Ji-Hong1, XU Ru-Ren1, LI Jing2   

  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:2011-11-17 Revised:2011-12-27 Published:2012-02-23
  • Contact: LI Yi
  • Supported by:

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

Abstract: 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.

Key words: Inorganic crystal structure, Database, Substructure search, VF2 algorithm, Zeolite, Building unit