TesseraMap: Dimensionality Reduction by Tessellation of Linear Subspaces with Application in Protein Structure Determination

• Activity Number: 126
• Type: Contributed
• Date/Time: Monday, July 30, 2012 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Computing
• Author(s): Ali Ghodsi*+
• Keywords: Bioinformatics ; Visualization ; High-dimensional data ; Protein folding ; Machine Learning

Abstract

In protein NMR, the 3D structure is determined by making use of a set of distance restraints between proton pairs and exploiting the domain knowledge about proteins. Euclidean distance geometry methods based on semidefinite programming (SDP) provide a natural formulation for realizing a 3D structure from a set of given distance constraints. However, the complexity of SDP solvers is a major obstacle in their applicability to the protein NMR problem. In this talk, first I propose a novel SDP-based dimensionality reduction algorithm, which is both fast and robust. By using a technique called 'semidefinite facial reduction,' the SDP matrix size and the number of equality constraints are approximately one quarter of the original problem. Using this technique results in a one hundred-fold decrease in the running time required by the SDP solver. I show how this algorithm can be used for protein structure determination from NMR data. This method is applied to proteins with a molecular mass less than 15 kDa, and the predicted structures are accurate.