Structural alignment. (c2006)

Abstract

Structural alignment is the process of finding similarities between a pair of proteins based on their three-dimensional shape. Accurate detection of such similarities could reveal evolutionary relationships and predict the functions of different proteins. The algorithmic solutions proposed so far rely on heuristics or approximation methods, but these could provably deliver poor results in general. Moreover, exact solutions tend to be very slow in practice. In this thesis we consider a graph-theoretic approach, which consists of representing tertiary protein structures as labeled graphs, and interpreting the structural alignment problem as a particular case of the Maximum Common Subgraph problem. We discuss the utility of employing a recent algorithmic technique for solving Maximum Common Subgraph. When applied to pairs of proteins, obtained from the Protein Data Bank (PDB), the proposed algorithm is shown to deliver reasonably accurate results. In order to improve the time-efficiency of this approach, a scalable parallel version is presented.