Abstract
Finding the common structural features of two molecules is a fundamental task in cheminformatics. Most drugs are small molecules, which can naturally be interpreted as graphs. Hence, the task is formalized as maximum common subgraph problem. Albeit the vast majority of molecules yields outerplanar graphs this problem remains \(\mathsf{NP}\)-hard.
We consider a variation of the problem of high practical relevance, where the rings of molecules must not be broken, i.e., the block and bridge structure of the input graphs must be retained by the common subgraph. We present an algorithm for finding a maximum common connected induced subgraph of two given outerplanar graphs subject to this constraint. Our approach runs in time \(\mathcal {O}(\varDelta n^2)\) in outerplanar graphs on n vertices with maximum degree \(\varDelta \). This leads to a quadratic time complexity in molecular graphs, which have bounded degree. The experimental comparison on synthetic and real-world datasets shows that our approach is highly efficient in practice and outperforms comparable state-of-the-art algorithms.
This work was supported by the German Research Foundation (DFG), priority programme “Algorithms for Big Data” (SPP 1736).
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
Similar content being viewed by others
Notes
- 1.
We are grateful to Leander Schietgat for providing the implementation used in [13].
- 2.
NCI Open Database, GI50, http://cactus.nci.nih.gov.
References
Akutsu, T.: A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E76–A(9), 1488–1493 (1993)
Akutsu, T., Tamura, T.: A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree. Algorithms 6(1), 119–135 (2013)
Droschinsky, A., Kriege, N., Mutzel, P.: Faster algorithms for the maximum common subtree isomorphism problem. MFCS 2016. LIPIcs, 58, 34:1–34:14 (2016). arXiv:1602.07210
Droschinsky, A., Kriege, N., Mutzel, P.: Finding largest common substructures of molecules in quadratic time (2016). CoRR arXiv:1610.08739
Ehrlich, H.C., Rarey, M.: Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review. Wiley Interdiscip. Rev. Comput. Mol. Sci. 1(1), 68–79 (2011)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)
Kriege, N., Kurpicz, F., Mutzel, P.: On maximum common subgraph problems in series-parallel graphs. In: Kratochvíl, J., Miller, M., Froncek, D. (eds.) IWOCA 2014. LNCS, vol. 8986, pp. 200–212. Springer, Heidelberg (2015). doi:10.1007/978-3-319-19315-1_18
Kriege, N., Mutzel, P.: Finding maximum common biconnected subgraphs in series-parallel graphs. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014. LNCS, vol. 8635, pp. 505–516. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44465-8_43
Lingas, A.: Subgraph isomorphism for biconnected outerplanar graphs in cubic time. Theor. Comput. Sci. 63(3), 295–302 (1989)
Matula, D.W.: Subtree isomorphism in \(O(n^{5/2})\). In: Alspach, B., P.H., Miller, D. (eds.) Algorithmic Aspects of Combinatorics, Annals of Discrete Mathematics, vol. 2, pp. 91–106. Elsevier (1978)
Nicholson, V., Tsai, C.C., Johnson, M., Naim, M.: A subgraph isomorphism theorem for molecular graphs. In: Graph Theory and Topology in Chemistry. Studies in Physical and Theoretical Chemistry, no. 51, pp. 226–230. Elsevier (1987)
Raymond, J.W., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Comput. Aided Mol. Des. 16(7), 521–533 (2002)
Schietgat, L., Ramon, J., Bruynooghe, M.: A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics. Ann. Math. Artif. Intell. 69(4), 343–376 (2013)
Sysło, M.M.: The subgraph isomorphism problem for outerplanar graphs. Theor. Comput. Sci. 17(1), 91–97 (1982)
Yamaguchi, A., Aoki, K.F., Mamitsuka, H.: Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees. Inf. Process. Lett. 92(2), 57–63 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Droschinsky, A., Kriege, N., Mutzel, P. (2017). Finding Largest Common Substructures of Molecules in Quadratic Time. In: Steffen, B., Baier, C., van den Brand, M., Eder, J., Hinchey, M., Margaria, T. (eds) SOFSEM 2017: Theory and Practice of Computer Science. SOFSEM 2017. Lecture Notes in Computer Science(), vol 10139. Springer, Cham. https://doi.org/10.1007/978-3-319-51963-0_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-51963-0_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-51962-3
Online ISBN: 978-3-319-51963-0
eBook Packages: Computer ScienceComputer Science (R0)