CMOS

Online Server for Protein Structure Alignment via Contact Map Overlap Maximization

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, drug design, and assessing the quality of computational prediction of unknown structures. Contact map overlap (CMO) is one of the most reliable and robust measures of protein structure similarity. Fold comparison via CMO is 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. CMO is an NP-hard combinatorial optimization problem. CMOS, the Contact Map Overlap Solver, combines branch-and-bound with problem-specific reduction techniques for the CMO problem. The underlying algorithms are described in Xie, W. and N. V. Sahinidis, A reduction-based exact algorithm for the contact map overlap problem, Journal of Computational Biology, 14(5), 637-654, 2007