VF2 Algorithm Based 2D Chemical Structure Search

近二十年来，随着计算机和信息技术在化学科研中的广泛应用，产生了化学信息学这一新的研究领域，其中化学数据库，特别是分子结构数据库的研究受到了化学家以及计算机科学家们的广泛关注。如何有效地存储和获取分子结构数据库中的分子结构信息就成为化学信息学家们首先要解决的问题。 本文采用了MOL格式和SDF格式来表达分子二维结构信息。为了有效地获取分子结构数据库中的分子结构信息，本文采用了一种通用图－子图同构算法——VF2算法来解决分子二维子结构检索问题，取得了很好的效果。同时，还使用了开源化学软件OpenBabel来解决芳香环识别问题。 本文用标准C++语言实现了VF2算法，兼顾了程序的效率和可移植性。并建立了含有61024个分子二维结构的ISIS/Base数据库。 经过与商业软件ISIS/Base对照实验，在配置了Intel Celeron 1.2GHz CPU和256MB PC133 SDRAM的PC上对已经建立好的分子结构数据库进行检索，检索结果正确，检索时间平均约为7.66秒，对于用户是可以接受的。 经实验分析发现，本文实现的程序的检索效率主要与提问分子结构中的出度大的原子个数有关，出度大的原子越多，则检索效率越高；其次，提问分子中的总原子数也对检索效率有一定影响，总原子数越多，检索效率越低。这也符合VF2算法作为通用图匹配算法的基本原理