Description
Several real-world problems require embedding a specific structure into another. In our case, finite metric spaces will play the roles of these structures. A widely known approach to solving these problems is constructing a special auxiliary graph — a kind of product graph — and attempting 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 solving them. One of those of special interest to us is a drug molecule docking into a protein.
One shortcoming of this method is that it assumes that the docking drug molecule is assumed to be geometrically rigid. This leads to inadequate solutions or even to straightaway false solutions. We suggest relaxing 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 (a smaller structure). 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.
You can join the seminar online using the following Zoom link: