Abstract:
Proteins are ubiquitous macromolecules that are involved in all biological processes. Structural similarities among proteins may hint at distant evolutionary relationships that are hard or impossible to discern from protein sequences alone. Thus, a fundamental computational challenge in the study of protein structure is comparing proteins and structural comparison, or alignment, is an essential tool when classifying known protein structures and analyzing their relationships.
The talk focuses on structural comparison of protein pairs. We formalize the protein structural alignment problem as an optimization problem of a geometric similarity score over the space of rigid transformations. This formulation leads to an approximate polynomial-time alignment algorithm, thus proving that the problem is not NP-hard as was previously thought. We also present a large-scale experiment in which we compare six popular structural alignment heuristic methods by evaluating the quality of their solutions, using a common geometric measure. Our approach to comparing structural alignment methods contrasts with the traditional use of ROC curves and relying on a classification gold standard. We use these tools to evaluate the novelty of proteins solved by the Structural Genomics (SG) initiative – an international endeavor, seeking to explore the entire protein space.
We conclude by mentioning the related problem of modeling protein structure.