A reduction-based exact algorithm for the contact map overlap problem.
Aligning proteins based on their structural similarity is a fundamental problem in molecular biology with applications in many settings, including structure classification, database search, function prediction, and assessment of folding prediction methods. Structural alignment can be done via several methods, including contact map overlap (CMO) maximization that aligns proteins in a way that maximizes the number of common residue contacts. In this paper, we develop a reduction-based exact algorithm for the CMO problem. Our approach solves CMO directly rather than after transformation to other combinatorial optimization problems. We exploit the mathematical structure of the problem in order to develop a number of efficient lower bounding, upper bounding, and reduction schemes. Computational experiments demonstrate that our algorithm runs significantly faster than existing exact algorithms and solves some hard CMO instances that were not solved in the past. In addition, the algorithm produces protein clusters that are in excellent agreement with the SCOP classification. An implementation of our algorithm is accessible as an on-line server at http://eudoxus.scs.uiuc.edu/cmos/cmos.html.
Department of Chemical and Biomolecular Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801, USA.
Wei
W
Xie
Nikolaos V
NV
Sahinidis
D000465:Algorithms; D000818:Animals; D001426:Bacterial Proteins / Q000737:chemistry / Q000235:genetics; D019295:Computational Biology / Q000639:trends; D008956:Models, Chemical; D016415:Sequence Alignment / Q000379:methods / Q000639:trends; D020539:Sequence Analysis, Protein / Q000379:methods / Q000639:trends; D040681:Structural Homology, Protein
D001426:Bacterial Proteins