title: Optimization and visualization of the edge weights in optimal assignment methods for virtual screening.
abstract: BACKGROUND
  Ligand-based virtual screening plays a fundamental part in the early drug discovery stage. In a virtual screening, a chemical library is searched for molecules with similar properties to a query molecule by means of a similarity function. The optimal assignment of chemical graphs has proven to be a valuable similarity function for many cheminformatic tasks, such as virtual screening. The optimal assignment assumes all atoms of a query molecule to be equally important, which is not realistic depending on the binding mode of a ligand. The importance of a query molecule's atoms can be integrated in the optimal assignment by weighting the assignment edges. We optimized the edge weights with respect to the virtual screening performance by means of evolutionary algorithms. Furthermore, we propose a visualization approach for the interpretation of the edge weights.
  
  
  RESULTS
  We evaluated two different evolutionary algorithms, differential evolution and particle swarm optimization, for their suitability for optimizing the assignment edge weights. The results showed that both optimization methods are suited to optimize the edge weights. Furthermore, we compared our approach to the optimal assignment with equal edge weights and two literature similarity functions on a subset of the Directory of Useful Decoys using sophisticated virtual screening performance metrics. Our approach achieved a considerably better overall and early enrichment performance. The visualization of the edge weights enables the identification of substructures that are important for a good retrieval of ligands and for the binding to the protein target.
  
  
  CONCLUSIONS
  The optimization of the edge weights in optimal assignment methods is a valuable approach for ligand-based virtual screening experiments. The approach can be applied to any similarity function that employs the optimal assignment method, which includes a variety of similarity measures that have proven to be valuable in various cheminformatic tasks. The proposed visualization helps to get a better understanding of the binding mode of the analyzed query molecule.
authors.affiliation: University of Tübingen, Center for Bioinformatics (ZBIT), Sand 1, 72076 Tübingen, Germany. lars.rosenbaum@uni-tuebingen.de.
authors.forename: Lars
authors.initials: L
authors.lastname: Rosenbaum
authors.forename: Andreas
authors.initials: A
authors.lastname: Jahn
authors.forename: Alexander
authors.initials: A
authors.lastname: Dörr
authors.forename: Andreas
authors.initials: A
authors.lastname: Zell