A_Purva

A_Purva maximizes contact map overlap between two protein structures to quantify structural similarity by producing residue alignments that reflect spatial proximity in 3D structures.

Key Features:

• Integer Programming Model: A_Purva employs an integer programming formulation specifically tailored for contact map overlap (CMO) problems.
• Branch-and-Bound Algorithm: It uses a branch-and-bound algorithm that leverages bounds derived from a Lagrangian relaxation technique.
• Benchmark Performance: The solver outperforms existing exact algorithms for CMO on the Skolnick set of 40 protein domains and on a constructed dataset of 300 protein domains.
• Scalability: It computes similarity measures for all possible pairs within its benchmark sets to enable large-scale structural comparisons.
• Biological Relevance: The resulting alignments correspond with Structural Classification of Proteins (SCOP) classifications, supporting biological interpretation.

Scientific Applications:

• Protein Structure Comparison: Comparing 3D protein structures to identify structural similarities and differences via maximized contact map overlap.
• Evolutionary Studies: Assessing structural conservation across protein families to inform evolutionary relationships.
• Drug Design and Discovery: Highlighting overlapping structural regions that may indicate potential binding sites or conformational changes relevant to therapeutic targeting.

Methodology:

Proteins are represented as contact maps (binary matrices indicating residue proximity), and these maps are aligned to maximize overlap using an integer programming formulation solved by a branch-and-bound algorithm with bounds from Lagrangian relaxation.