Title: A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics
Authors: Schietgat, Leander ×
Ramon, Jan
Bruynooghe, Maurice #
Issue Date: Dec-2013
Publisher: J.C. Baltzer
Series Title: Annals of Mathematics and Artificial Intelligence vol:69 issue:4 pages:343-376
Abstract: Metrics for structured data have received an increasing interest in the machine learning community. Graphs provide a natural representation for structured data, but a lot of operations on graphs are computationally intractable. In this article, we present a polynomial-time algorithm that computes a maximum common subgraph of two outerplanar graphs. The algorithm makes use of the block-and-bridge preserving subgraph isomorphism, which has significant efficiency benefits and is also motivated from a chemical perspective. We focus on the application of learning structure-activity relationships, where the task is to predict the chemical activity of molecules. We show how the algorithm can be used to construct a metric for structured data and we evaluate this metric and more generally also the block-and-bridge preserving matching operator on 60 molecular datasets, obtaining state-of-the-art results in terms of predictive performance and efficiency.
ISSN: 1012-2443
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
leander_schietgat_mcs2011_amai_final_version.pdf Accepted 1735KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science