Aligning Protein Structures Using Distance Matrices and Combinatorial Optimization

Inken Wohlers

Structural alignments of proteins are used to identify structural similarities. These similarities can indicate homology or a common or similar function. Many, mostly heuristic methods are available to compute structural alignments.

In this talk I present an algorithm that uses integer linear programming and Lagrangian relaxation to compute provably optimal structural alignments of sparse protein distance matrices. Our algorithm extends an elegant approach proposed by Caprara et al. for the alignment of protein contact maps. We consider different types of distance matrices, with distances either between Cα atoms, Cß atoms, or between the two closest atoms of each residue. Via a comprehensive parameter optimization on HOMSTRAD alignments, we determine a scoring function for aligned pairs of distances. We introduce a negative score for non-structural, purely sequence-based parts of the alignment as a means to adjust the locality of the resulting structural alignments.

Our approach is implemented in a freely available software tool named PAUL (Protein structural Alignment Using Lagrangian relaxation). On the challenging SISY data set of 130 reference alignments we compare PAUL to six state-of-the-art structural alignment algorithms, MATRAS, DALI, FATCAT, SHEBA, CA, and CE. Here, PAUL alignments reach the highest average and median alignment accuracies. PAUL is thus a competitive tool for
pairwise high-quality structural alignment.