Finding largest common substructures of molecules in quadratic time

DOI10.1007/978-3-319-51963-0_24MaRDI QIDQ2971143zbMATH OpenOpenAlexWikidataFDO

Authors Andre Droschinsky, Nils Kriege, Petra Mutzel

Publication date 4 April 2017

Published in SOFSEM 2017: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.08739

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

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 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 $mathcalO(Delta{n}^2)$ in outerplanar graphs on $n$ vertices with maximum degree $Delta$. 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.

Recommendations

• A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
• A polynomial-time algorithm for computing the maximum common subgraph of outerplanar graphs of bounded degree
• Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
• A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
• scientific article; zbMATH DE number 4081609

Cites work

• A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
• Faster algorithms for the maximum common subtree isomorphism problem
• Finding maximum common biconnected subgraphs in series-parallel graphs
• Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On maximum common subgraph problems in series-parallel graphs
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• The subgraph isomorphism problem for outerplanar graphs

Cited in

(9)

• A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
• A fast discovery algorithm for large common connected induced subgraphs
• Learning Block-Preserving Outerplanar Graph Patterns and Its Application to Data Mining
• scientific article; zbMATH DE number 4081609 (Why is no real title available?)
• scientific article; zbMATH DE number 2080091 (Why is no real title available?)
• Largest Weight Common Subtree Embeddings with Distance Penalties
• Algorithmic data science (invited talk)
• scientific article; zbMATH DE number 2239324 (Why is no real title available?)
• Identify five kinds of simple super-secondary structures with quadratic discriminant algorithm based on the chemical shifts

This page was built for publication: Finding largest common substructures of molecules in quadratic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2971143)