This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Strickland, D. M. Articles by Sokol, J. S. Search for Related Content

Optimal Protein Structure Alignment Using Maximum Cliques

Department of Mathematics, Winthrop University, Rock Hill, South Carolina 29733
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
stricklandd{at}winthrop.edu
ebarnes{at}isye.gatech.edu
jsokol{at}isye.gatech.edu

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.

Subject classifications: networks/graphs:applications; heuristics; programming:integer.
History: Received August 2003; revision received December 2003; accepted April 2004.

This article has been cited by other articles:

				C. N. Goulimis ASP, The Art and Science of Practice: Appeal to NP-Completeness Considered Harmful: Does the Fact That a Problem Is NP-Complete Tell Us Anything? Interfaces, November 1, 2007; 37(6): 584 - 586. [Abstract] [PDF]