Fekete, István
(ELTE) and Kovács, Péter (ChemAxon)
Similarity search on molecular
graphs
This talk is about
similarity search on chemical graphs, which is essential in the early stages of
drug discovery process. We study two related problems and present effective
methods for the representation and comparison of molecular graphs.
A commonly used
mathematical model represents certain features of molecular graphs as 0-1
vectors of large dimension, which are usually called fingerprints. The
k-nearest neighbors (k-NN) problem is to find the k closest fingerprints in a
(large) database with respect to a given query fingerprint. We discuss a simple
but efficient method for solving this task based on locality sensitive hashing.
The second part of the talk
considers the thorough structural comparison of two molecular graphs based on
their maximum common subgraph (MCS), which can be the next step after k-NN
search. Finding the MCS of two graphs is an NP-hard optimization problem. We
present heuristic algorithms along with effective improvements, which exploit
the properties of molecular graphs and greatly enhance the accuracy and
performance of the basic methods.
The talk is held in Hungarian!
Az előadás nyelve magyar!
Date: Nov 6, Tuesday 4:15pm
Place: BME, Building „Q”, Room QBF13