Sunday, May 21, 2006, 11:15-12:15
Room 309
--------------------------------------------------------------------------------
Maxim Shatsky
TAU
Title: The Common Point Set Problem with Applications to
Protein Structure
Analysis.
Abstract:
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
interfaces.
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
algorithms.
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.