Description
There are several real world problems that require embedding a specific structure to another. In our case finite metric spaces will play the roles of these structures. A widely known approach to solve these problems is constructing a special auxiliary graph -- a kind of product graph -- and trying to locate a maximum or k-clique in this graph. In the first part of my talk I will introduce these problems and the basic approach to solve them. One of those are of special interest to us is a drug molecule docking into a protein.
One shortcoming of this method is that it is assumed that the docking drug molecule is assumed to be geometrically rigid. This leads to not fully adequate solutions or even to straight-away false solutions. We suggest to relax the rigidity assumption of the drug molecule. In this new situation we have a rigid protein molecule (a larger structure) and a non-rigid drug molecule (smaller structures). This non-rigid molecule is modeled by a finite family of rigid molecules. We are looking for a smaller structure within the family that can be injected into the larger structure optimally. We argue that the new more realistic model can also be handled by constructing a new type of product graph in which one should locate a maximum or k-clique. We will show that such an approach can be used for solving several non trivial problems as well.
joint work with Janez Konc, Peter Madarasi, and Sandor Szabo