A Graph Theoretic Approach to Protein Structure Selection

Protein Structure Prediction (PSP) aims to reconstruct the 3D structure of a given protein starting from its primary structure (chain of amino acids). It is a well known fact that the 3D structure of a protein only depends on its primary structure. PSP is one of the most important and still unsolved problems in computational biology. Protein Structure Selection (PSS), instead of reconstructing a 3D model for the given chain, aims to select among a given, possibly large, number of 3D structures (called decoys) those that are closer (according to a given notion of distance) to the original (unknown) one. Each decoy is represented by a set of points in 3D. Existing methods for solving PSS make use of suitably defined energy functions which heavily rely on the primary structure of the protein and on protein chemistry. In this paper we present a completely different approach to PSS which does not take advantage at all of the knowledge of the primary structure of the protein but only relies on the graph theoretic properties of the decoys graphs (vertices represent amino acids and edges represent pairs of amino acids whose euclidean distance is less than or equal to a fixed threshold). Even if our methods only rely on approximate geometric information, experimental results show that some of the graph properties we adopt score similarly to energy-based filtering functions in selecting the best decoys. Our results show the principal role of geometric information in PSS, setting a new starting point and filtering method, for existing energy function-based techniques.