Optimal Protein Structure Alignment Using Maximum Cliques

Dawn M. Strickland (), Earl Barnes () and Joel S. Sokol ()
Additional contact information
Dawn M. Strickland: Department of Mathematics, Winthrop University, Rock Hill, South Carolina 29733
Earl Barnes: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Joel S. Sokol: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Operations Research, 2005, vol. 53, issue 3, 389-402

Abstract: In biology, the protein structure alignment problem answers the question of how similar two proteins are. Proteins with strong physical similarities in their tertiary (folded) structure often have similar functions, so understanding physical similarity could be a key to developing protein-based medical treatments. One of the models for protein structure alignment is the maximum contact map overlap (CMO) model. The CMO model of protein structure alignment can be cast as a maximum clique problem on an appropriately defined graph. We exploit properties of these protein-based maximum clique problems to develop specialized preprocessing techniques and show how they can be used to more quickly solve contact map overlap instances to optimality.

Keywords: networks/graphs:applications; heuristics; programming:integer (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0189 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:53:y:2005:i:3:p:389-402

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().