大规模化合物子结构检索的并行实现与优化
Parallel chemical substructure searching of large scale chemical database on PC cluster
查看参考文献26篇
文摘
|
化合物的子结构检索在计算机辅助药物设计、波普学、化学数据库等领域是不可或缺的工具. 然而由于子结构检索是一个NP完备性的问题,获得用户可接受的平均检索时间一直是研究人员十分关注的问题,其方法主要有改进算法和提升硬件条件2个方面. 当化学结构数据库的规模达到百万乃至千万级别时,尽管改进算法的方式能够获得一定的检索效率提升,但其提升的空间有限,因而,集群并行方式是大规模化合物子结构检索应用的必然选择. 本文以Chem DB 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 Chem DB 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 |
来源
|
计算机与应用化学
,2010,27(6):728-734 【核心库】
|
关键词
|
化学子结构检索
;
大规模化学结构检索
;
集群并行
;
化学数据库
;
化学信息学
|
地址
|
中国科学院过程工程研究所, 多相复杂系统国家重点实验室, 北京, 100190
|
语种
|
中文 |
文献类型
|
研究性论文 |
ISSN
|
1001-4160 |
学科
|
化学;自动化技术、计算机技术 |
基金
|
国家自然科学基金资助项目
|
文献收藏号
|
CSCD:3942540
|
参考文献 共
26
共2页
|
1.
Ray L C. Finding chemical records by digital computers.
Science,1957,126:814-819
|
被引
1
次
|
|
|
|
2.
Ullmann J R. An algorithm for subgraph isomorphism.
J Assoc Comput Machin,1976,23:31-42
|
被引
97
次
|
|
|
|
3.
Xu Jun. GMA: A generic match algorithm for structure homomorphism,isomorphism,and maximal common substructure match and its application.
J Chem Inf Compu Sci,1996,36:25-34
|
被引
19
次
|
|
|
|
4.
Cordella L P. An efficient algorithm for the inexact matching of ARG graphs using a contextual transformational model.
Proceedings of the 13th Intemational Conference on Pattern Recognition,1996:180-184
|
被引
1
次
|
|
|
|
5.
Foggia P. Introducing generalized attributed relational graphs (GARG's) as prototypes of ARG's.
Proceedings of the 2ed IAPR-TC-15 International Workshop on Graph-based Representations,1999:184-192
|
被引
1
次
|
|
|
|
6.
Cordella L P. Graph matching: A fast algorithm and its evaluation.
Proceedings of the 14th International Conference on Pattern Recognition,1998:1582-1584
|
被引
1
次
|
|
|
|
7.
Cordella L P. Subgraph transformations for inexact matching of attributed relational graphs.
Computing,1998,12:43-52
|
被引
7
次
|
|
|
|
8.
Cordella L P. Performance evaluation of the VF graph matching algorithm.
Proceedings of the 10th International Conference on Image Analysis and Processing,1999:1172-1177
|
被引
1
次
|
|
|
|
9.
Foggia P. An improved algorithm for matching large graphs.
Proceedings of the 3rd IAPR-TC-15 International Workshop on Graph-based Representation in Pattern Recognition,2001:149-159
|
被引
1
次
|
|
|
|
10.
Foggia P. A Performance comparison of five algorithms for graph isomorphism.
Proceedings of the 3rd IAPR International Workshop on Graph-based Representations in Pattern Recognition,2001:188-199
|
被引
1
次
|
|
|
|
11.
李琰. VF算法在化学结构检索中的应用.
计算机与应用化学,2002,19(5):575-580
|
被引
3
次
|
|
|
|
12.
刘冰. 化学结构二维子结构检索的开发.
过程工程学报,2003,3(4):376-380
|
被引
3
次
|
|
|
|
13.
孙婉怡. 一种新的分子二维子结构检索算法.
计算机与应用化学,2009,26(16):1539-1542
|
被引
5
次
|
|
|
|
14.
.
SciFinder Scholar
|
被引
1
次
|
|
|
|
15.
.
PubChem
|
被引
3
次
|
|
|
|
16.
.
eMolecules
|
被引
1
次
|
|
|
|
17.
苏振强. 基于甲骨文数据库管理系统的化学结构检索数据库的设计与实现.
计算机与应用化学,2003,20(5):556-562
|
被引
7
次
|
|
|
|
18.
苏振强. 分布式多线程并行处理技术在大规模化学结构检索数据库系统中的应用.
计算机与应用化学,2004,21(5):659-664
|
被引
1
次
|
|
|
|
19.
储春梅. 定向查询引擎在Web化学数据库集成检索中的应用.
计算机与应用化学,2005,22(8):659-666
|
被引
9
次
|
|
|
|
20.
卓流艺. XML技术在化学深层网数据提取中的应用.
计算机与应用化学,2006,23(11):1137-1141
|
被引
8
次
|
|
|
|
|