1001 Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap
Authors:
- 1 January 2004
- journal article
- research article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 11 (1) , 27-52
Abstract
Protein structure comparison is a fundamental problem for structural genomics, with applications to drug design, fold prediction, protein clustering, and evolutionary studies. Despite its importance, there are very few rigorous methods and widely accepted similarity measures known for this problem. In this paper we describe the last few years of developments on the study of an emerging measure, the contact map overlap (CMO), for protein structure comparison. A contact map is a list of pairs of residues which lie in three-dimensional proximity in the protein's native fold. Although this measure is in principle computationally hard to optimize, we show how it can in fact be computed with great accuracy for related proteins by integer linear programming techniques. These methods have the advantage of providing certificates of near-optimality by means of upper bounds to the optimal alignment value. We also illustrate effective heuristics, such as local search and genetic algorithms. We were able to obtain for the first time optimal alignments for large similar proteins (about 1,000 residues and 2,000 contacts) and used the CMO measure to cluster proteins in families. The clusters obtained were compared to SCOP classification in order to validate the measure. Extensive computational experiments showed that alignments which are off by at most 10% from the optimal value can be computed in a short time. Further experiments showed how this measure reacts to the choice of the threshold defining a contact and how to choose this threshold in a sensible way.Keywords
This publication has 26 references indexed in Scilit:
- Structure Comparison and Structure PatternsJournal of Computational Biology, 2000
- The Protein Data BankNucleic Acids Research, 2000
- A Polyhedral Approach to RNA Sequence Structure AlignmentJournal of Computational Biology, 1998
- CATH – a hierarchic classification of protein domain structuresStructure, 1997
- The structural alignment between two proteins: Is there a unique answer?Protein Science, 1996
- Protein Structure Comparison by Alignment of Distance MatricesJournal of Molecular Biology, 1993
- Topology fingerprint approach to the inverse protein folding problemJournal of Molecular Biology, 1992
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981
- A solution for the best rotation to relate two sets of vectorsActa Crystallographica Section A, 1976
- A general method applicable to the search for similarities in the amino acid sequence of two proteinsJournal of Molecular Biology, 1970