大规模化合物子结构检索的并行实现与优化  

Parallel chemical substructure searching of large scale chemical database on PC cluster

作　　者：井银玲[1,2] 李晓霞[1] 袁小龙[1] 郭力[1] 

机构地区：[1]中国科学院过程工程研究所多相复杂系统国家重点实验室,北京100190 [2]中国科学院研究生院,北京100049

出　　处：《计算机与应用化学》2010年第6期728-734,共7页Computers and Applied Chemistry

基　　金：国家自然科学基金资助项目(20673119;90612015;20221603;20821092)

摘　　要：化合物的子结构检索在计算机辅助药物设计、波普学、化学数据库等领域是不可或缺的工具。然而由于子结构检索是一个NP完备性的问题,获得用户可接受的平均检索时间一直是研究人员十分关注的问题,其方法主要有改进算法和提升硬件条件2个方面。当化学结构数据库的规模达到百万乃至千万级别时,尽管改进算法的方式能够获得一定的检索效率提升,但其提升的空间有限,因而,集群并行方式是大规模化合物子结构检索应用的必然选择。本文以ChemDB Portal的化学子结构检索系统为基础,实现了基于集群并行的化学子结构检索系统,并进行了任务均分、多线程并行等优化。在包含800万个化合物结构的化学结构数据库中,利用5个节点的小型集群,选取10个较为典型的提问结构进行子结构检索测试。测试结果为基于集群的化学子结构检索的平均检索时间由初始单节点时的34.1 min降低为2.75 min,检索效率平均提高12.4倍,表明在大规模乃至超大规模的数据条件下,集群并行化方式能够显著地提高子结构检索系统的执行效率。Chemical substructure searching is an indispensable tool in many fields such as the computer-aided drug design, spectroscopy,and chemistry structure database.Chemical substructure searching is equivalent to the subgraph isomorphism problem in graph theory,which is known to belong to the class of NP-complete computational problem,because it is a traversal method that must be done at atom-by-atom match level.Finding subgraph isomorphism algorithms which operate with acceptable average time has occupied the attention of researchers for many years and is still the subject of active research.Our aim in this paper was to reduce the time required to perform substructure searching,particularly in a large database with over millions of chemical structures.Based on ChemDB Portal,a parallel chemical substructure searching system of large scale chemical database on PC cluster was established,and optimized with computing task balance and multithreading.The testing results of substructure searching for 10 representative queries in a chemical database with 8 millions structures,performed on a 5-node cluster show an average 12.4-fold speed up over a single node of the cluster.The executing efficiency of chemical substructure searching of large scale database can be improved significantly by parallel cluster.

关 键 词：化学子结构检索 大规模化学结构检索 集群并行 化学数据库 化学信息学 

分 类 号：TP392[自动化与计算机技术—计算机应用技术] O6-39[自动化与计算机技术—计算机科学与技术]