Abstract
To enumerate chemical compounds with given path frequencies is a fundamental procedure in Chemo- and Bio-informatics. The applications include structure determination, novel molecular development, etc. The problem complexity has been proven as NP-hard. Many methods have been proposed to solve this problem. However, most of them are heuristic algorithms. Fujiwara et al. propose a sequential branch-and-bound algorithm. Although it reaches all solutions and avoids exhaustive searching, the computation time still increases significantly when the number of atoms increases. Hence, in this paper, a parallel algorithm is presented for solving this problem. The experimental results showed that computation time was reduced even when more processes were launched. Moreover, the speed-up ratio for most of the test cases was satisfactory and, furthermore, it showed potential for use in drug design.
This work is partially supported by Nation Science Council. (NSC98-2221-E-216-023 and NSC97-2221-E-216-020).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Buchanan, B., Feigenbaum, E.: DENDRAL and Meta-DENDRAL, Their Applications Dimension. Artif. Intell. 11, 5–24 (1978)
Funatsu, K., Sasaki, S.: Recent advances in the automated structure elucidation system, chemics. Utilization of two-dimensional nmr spectral information and development of peripheral functions for examination of candidates. J. Chem. Inf. Comput. Sci. 36(2), 190–204 (1996)
Faulon, J., Churchwell, C., Visco Jr., D.: The signature molecular descriptor. 2. Enumerating molecules from their extended valence sequences. J. Chem. Inf. Comput. Sci. 43(3), 721–734 (2003)
Hall, L., Dailey, R., Kier, L.: Design of molecules from quantitative structure-activity relationship models. 3. Role of higher order path counts: path 3. J. Chem. Inf. Comput. Sci. 33(4), 598–603 (1993)
Deshpande, M., Kuramochi, M., Wale, N., Karypis, G.: Frequent substructure-based approaches for classifying chemical compounds. IEEE Trans. Knowl. Data Eng. 17(8), 1036–1050 (2005)
Fink, T., Reymond, J.: Virtual Exploration of the Chemical Universe up to 11 Atoms of C, N, O, F: Assembly of 26.4 Million Structures (110.9 Million Stereoisomers) and Analysis for New Ring Systems, Stereochemistry. J. Chem Inf. Model. 47(2), 342–353 (2007)
Mauser, H., Stahl, M.: Chemical fragment spaces for de novo design. J. Chem. Inf. Model. 47(2), 318–324 (2007)
Kashima, H., Tsuda, K., Inokuchi, A.: Marginalized kernels between labeled graphs. In: ICML, pp. 321–328 (2003)
Akutsu, T., Fukagawa, D.: Inferring a Graph from Path Frequency. In: Apostolico, A., Crochemore, M., Park, K. (eds.) LOPSTR 2004. LNCS, vol. 3573, pp. 371–382. Springer, Heidelberg (2005)
Yu, C., Wah, B.: Efficient branch-and-bound algorithms on a two-level memory system. IEEE Trans. Softw. Eng. 14(9), 1342–1356 (1988)
Fujiwara, H., Wang, J., Zhao, L., Nagamochi, H., Akutsu, T.: Enumerating Treelike Chemical Graphs with Given Path Frequency. J. Chem. Inf. Model. 48(7), 1345–1357 (2008)
OpenMP, http://openmp.org/
Nakano, S., Uno, T.: Generating colored trees. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 249–260. Springer, Heidelberg (2005)
Wright, R., Richmond, B., Odlyzko, A., McKay, B.: Constant time generation of free trees. SIAM J. Comput. 15, 540 (1986)
Jordan, C.: Sur les assemblages de lignes. J. Reine Angew. Math. 70(185), 81 (1869)
KEGG Ligand database, http://www.genome.jp/kegg/ligand.html
Zhang, J., Yu, K., Zhu, W., Jiang, H.: Neuraminidase pharmacophore model derived from diverse classes of inhibitors. Bioorg. Med. Chem. Lett. 16, 3009–3014 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhou, J., Yu, KM., Lin, C.Y., Shih, KC., Tang, C.Y. (2010). Balanced Multi-process Parallel Algorithm for Chemical Compound Inference with Given Path Frequencies. In: Hsu, CH., Yang, L.T., Park, J.H., Yeo, SS. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2010. Lecture Notes in Computer Science, vol 6082. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13136-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-13136-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13135-6
Online ISBN: 978-3-642-13136-3
eBook Packages: Computer ScienceComputer Science (R0)