Inken Wohlers (CWI) gives a lecture about the computation of protein structural alignment

Location: CWI, room M279

Protein structural alignment computes the three-dimensional superposition of protein structures by means of aligning the protein's residues. It is a basic method for identifying proteins of related structure or common evolutionary origin and for measuring three-dimensional similarity.

Unlike protein sequence alignment, the computation of protein structural alignment is an NP-hard problem. It requires elaborate methods to compute good, biologically correct alignments. Many different approaches have been suggested and as a consequence many diverse structural alignment algorithms are available.

"We use an approach that computes an alignment based on the protein's inter-residue distances", says Inken Wohlers. Using these distances the problem is formulated as an Integer Linear Program (ILP) which is subsequently tried to be solved. The ILP and the way of solving it are analogous to an approach for the alignment of protein contact maps suggested by Lancia and Caprara. "The advantage of this method is that it can compute demonstrable optimal alignments in some cases. The bottleneck of the Integer Linear programming approach is its computational complexity which does not allow to incorporate all inter-residue distances in the problem description. On that account we work on an effective selection and weighting of inter-residue distances. Our current work focuses on the determination of an appropriate scoring of aligned distances."

In this talk Wohlers will briefly motivate the biological background and then introduce the original algorithm for alignment of protein contact maps by Lancia and Caprara as well as its further development for the alignment of protein distance matrices.