A reduction-based exact algorithm for the contact map overlap problem

Wei Xie, Nikolaos V. Sahinidis

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)637-654
Number of pages18
JournalJournal of Computational Biology
Issue number5
StatePublished - Jun 2007


  • Branch-and-bound
  • Contact map overlap
  • Dynamic programming
  • Protein structural alignment
  • Reduction

ASJC Scopus subject areas

  • Modeling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'A reduction-based exact algorithm for the contact map overlap problem'. Together they form a unique fingerprint.

Cite this