Tel-Aviv University - Computer Science Colloquium

Sunday, May 21, 2006, 11:15-12:15

Room 309
Schreiber Building


Maxim Shatsky


Title: The Common Point Set Problem with Applications to Protein Structure




In this thesis, we study computational problems related to the analysis of

protein 3D folds and protein binding sites. Specifically, we deal with

one of the fundamental problems in the field of Structural Proteome

research, the problem of common spatial pattern detection in a set of

protein structures, protein binding sites and protein-protein



We discuss the computational problems of multiple common point set

detection under different metrics. We prove NP-Hardness results even

for the case of practically defined geometrical constraints on the

input point sets. While the generally defined problem and sub-problems

of common point set detection are hard to approximate, under the

practical constraints we present polynomial time approximation



On the practical side, we present novel computational methods for

multiple alignment of protein structures, structure based multiple

sequence alignment, multiple binding site and multiple protein-protein

interface alignment. Due to the hardness of the computational

problems, we apply a combination of heuristic, approximation and

branch-and-bound techniques in order to achieve a trade-off between

practical efficiency and accuracy of the biological results.


This talk describes the results of my PhD thesis which is done under the

supervision of Prof. Haim Wolfson and Prof. Ruth Nussinov.