Optimizing and Visualizing the Edge Weights in Optimal Assignment Methods

Optimizing edge weights

The optimal assignment method (OA) measures the similarity between two molecular graphs by finding an optimal mapping of the atoms of the smaller molecule on a subset of the atoms of the larger molecule. An optimal mapping of an atom on another atom results in an optimal assignment edge (Figure 1).
Generally, not all parts of the query molecule have the same importance for activity. For instance, the exact topology of a substructure that is crucial for the molecule's binding to the protein target is usually more important than the topology of some linker region. Hence, important substructures should receive more attention in the optimal assignment than unimportant substructures.
The assignment edge weights can be determined by optimizing the virtual screening performance on a data set of known ligands and decoys using evolutionary algorithms. The OAOptimizer software is able to optimize the weights using PSO or three different DE variants on a given data set of known ligands and decoys.
The methodology of optimizing the edge weights was presented at the EvoBio2012 conference [1].

Figure 1: Optimal assignment of two molecules of the COX2 dataset. The atom assignments are based on pairwise-atom similarities calculations of the OAK. Green optimal assignment edges represent a high atom similarity whereas red edges indicate a low atom similarity.

Visualization of edge weights

The optimized edge weights represent the importance of the query molecule's atoms, which can contain information on the binding mode or important substructures. The importance can be visualized with the OAResultViewer software.
The edge weights are represented by the ball size in a Ball&Stick visualization in Figure 2.

Figure 2: Weighted query on the COX2 data set in Ball&Stick visualization. The larger assignment edge weight, the larger the ball size.



[1]     Lars Rosenbaum, Andreas Jahn, and Andreas Zell. Optimizing the edge weights in optimal assignment methods for virtual screening with particle swarm optimization. In Mario Giacobini, Leonardo Vanneschi, and William Bush, editors, Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, volume 7246 of Lecture Notes in Computer Science, pages 26-37. Springer Berlin / Heidelberg, 2012.

[2]     Lars Rosenbaum, Andreas Jahn, Alexander Dörr, and Andreas Zell. Optimization and visualization of the edge weights in optimal assignment methods for virtual screening. BioData Mining, 6:7, 2013.


Lars Rosenbaum, Tel.: (07071) 29-77174, lars.rosenbaum (at) uni-tuebingen.de