by Alberto Caprara, Robert Carr, Sorin Istrail, Giuseppe Lancia, Brian Walenz
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.
Reference:
Alberto Caprara, Robert Carr, Sorin Istrail, Giuseppe Lancia, Brian Walenz, "1001 optimal PDB structure alignments: integer programming methods for finding the maximum contact map overlap", In Journal of Computational Biology, vol. 11, no. 1, pp. 27-52, 2004.
Bibtex Entry:
@ARTICLE{Caprara2004,
author = {Caprara, Alberto and Carr, Robert and Istrail, Sorin and Lancia,
Giuseppe and Walenz, Brian},
title = {1001 optimal PDB structure alignments: integer programming methods
for finding the maximum contact map overlap},
journal = {Journal of Computational Biology},
year = {2004},
volume = {11},
pages = {27--52},
number = {1},
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.},
doi = {citeulike-article-id:165612},
keywords = {alignment
protein
structure},
owner = {Derek},
timestamp = {2012.05.08},
url = {http://www.brown.edu/Research/Istrail_Lab/papers/1001-JCB.pdf},
category = {Protein Structure}
}