SAS-Pro: simultaneous residue assignment and structure superposition for protein structure alignment.
Protein structure alignment is the problem of determining an assignment between the amino-acid residues of two given proteins in a way that maximizes a measure of similarity between the two superimposed protein structures. By identifying geometric similarities, structure alignment algorithms provide critical insights into protein functional similarities. Existing structure alignment tools adopt a two-stage approach to structure alignment by decoupling and iterating between the assignment evaluation and structure superposition problems. We introduce a novel approach, SAS-Pro, which addresses the assignment evaluation and structure superposition simultaneously by formulating the alignment problem as a single bilevel optimization problem. The new formulation does not require the sequentiality constraints, thus generalizing the scope of the alignment methodology to include non-sequential protein alignments. We employ derivative-free optimization methodologies for searching for the global optimum of the highly nonlinear and non-differentiable RMSD function encountered in the proposed model. Alignments obtained with SAS-Pro have better RMSD values and larger lengths than those obtained from other alignment tools. For non-sequential alignment problems, SAS-Pro leads to alignments with high degree of similarity with known reference alignments. The source code of SAS-Pro is available for download at http://eudoxus.cheme.cmu.edu/saspro/SAS-Pro.html.
Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania, United States of America.
Shweta B
SB
Shah
Nikolaos V
NV
Sahinidis
D000596:Amino Acids / Q000737:chemistry*; D019295:Computational Biology / Q000379:methods; D020407:Internet; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*; D012984:Software
D000596:Amino Acids; D011506:Proteins