A branch-and-reduce algorithm for the contact map overlap problem

Wei Xie, Nikolaos V. Sahinidis

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A fundamental problem in molecular biology is the comparison of 3-dimensional protein folds in order to develop similarity measures and exploit them for protein clustering, database searches, and drug design, Contact map overlap (CMO) is one of the most reliable and robust measures of protein structure similarity. Fold comparison can be done by aligning the amino acid residues of two proteins in a way that maximizes the number of common residue contacts. CMO maximization is gaining increasing attention because it results in protein clusterings in good agreement with classification by experts. However, CMO maximization is an NP-hard problem and few exact algorithms exist for solving this problem to global optimality. In this paper, we propose a branch-and-reduce exact algorithm for the CMO problem. Contrary to previous approaches, we do not transform CMO to other combinatorial optimization problems for solution. Instead, we address the problem directly in its natural form. By exploiting the problem's mathematical structure, we develop bounding and reduction procedures that lead to a very efficient algorithm. We present extensive computational results for over 36000 test problems from the literature. These results demonstrate that our algorithm is significantly faster and solves many more challenging test sets than the best previous algorithms for CMO. Furthermore, the algorithm results in protein clusters that are in excellent agreement with the SCOP database.

Original languageEnglish (US)
Title of host publicationResearch in Computational Molecular Biology - 10th Annual International Conference, RECOMB 2006, Proceedings
EditorsAlberto Apostolico, Concettina Guerra, Sorin Istrail, Pavel A Pevzner, Michael Waterman
Number of pages14
ISBN (Print)3540332952, 9783540332954
StatePublished - 2006
Event10th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2006 - Venice, Italy
Duration: Apr 2 2006Apr 5 2006

Publication series

NameLecture Notes in Computer Science
Volume3909 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference10th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A branch-and-reduce algorithm for the contact map overlap problem'. Together they form a unique fingerprint.

Cite this