The Origin of the Designability of Protein Structures

A simple lattice model for proteins that allows for distinct sizes of the amino acids is presented. The model is found to lead to a significant number of conformations that are the unique ground state of one or more sequences or encodable. Furthermore, several of the encodable structures are highly designable and are the non-degenerate ground state of several sequences. Even though the native state conformations are typically compact, not all compact conformations are encodab...

We present an exact enumeration algorithm for identifying the {\it native} configuration - a maximally compact self avoiding walk configuration that is also the minimum energy configuration for a given set of contact-energy schemes; the process is implicitly sequence-dependent. In particular, we show that the 25-step native configuration on a diamond lattice consists of two sheet-like structures and is the same for all the contact-energy schemes, ${(-1,0,0);(-7,-3,0); (-7,-3,...

We review algorithms for protein design in general. Although these algorithms have a rich combinatorial, geometric, and mathematical structure, they are almost never covered in computer science classes. Furthermore, many of these algorithms admit provable guarantees of accuracy, soundness, complexity, completeness, optimality, and approximation bounds. The algorithms represent a delicate and beautiful balance between discrete and continuous computation and modeling, analogous...

Protein structure prediction based on Hydrophobic-Polar energy model essentially becomes searching for a conformation having a compact hydrophobic core at the center. The hydrophobic core minimizes the interaction energy between the amino acids of the given protein. Local search algorithms can quickly find very good conformations by moving repeatedly from the current solution to its "best" neighbor. However, once such a compact hydrophobic core is found, the search stagnates ...

We present a detailed study of the performance and reliability of design procedures based on energy minimization. The analysis is carried out for model proteins where exact results can be obtained through exhaustive enumeration. The efficiency of design techniques is assessed as a function of protein lengths and number of classes into which amino acids are coarse grained. It turns out that, while energy minimization strategies can identify correct solutions in most circumstan...

Inverse statistical approaches to determine protein structure and function from Multiple Sequence Alignments (MSA) are emerging as powerful tools in computational biology. However the underlying assumptions of the relationship between the inferred effective Potts Hamiltonian and real protein structure and energetics remain untested so far. Here we use lattice protein model (LP) to benchmark those inverse statistical approaches. We build MSA of highly stable sequences in targe...

Understanding of the evolutionary origins of protein structures represents a key component of the understanding of molecular evolution as a whole. Here we seek to elucidate how the features of an underlying protein structural "space" might impact protein structural evolution. We approach this question using lattice polymers as a completely characterized model of this space. We develop a measure of structural comparison of lattice structures that is analgous to the one used to...

Geometrical properties of protein ground states are studied using an algebraic approach. It is shown that independent from inter-monomer interactions, the collection of ground state candidates for any folded protein is unexpectedly small: For the case of a two-parameter Hydrophobic-Polar lattice model for $L$-mers, the number of these candidates grows only as $L^2$. Moreover, the space of the interaction parameters of the model breaks up into well-defined domains, each corres...

We present and discuss a novel approach to the direct and inverse protein folding problem. The proposed strategy is based on a variational approach that allows the simultaneous extraction of amino acid interactions and the low-temperature free energy of sequences of amino acids. The knowledge-based technique is simple and straightforward to implement even for realistic off-lattice proteins because it does not entail threading-like procedures. Its validity is assessed in the c...

A typical protein structure is a compact packing of connected alpha-helices and/or beta-strands. We have developed a method for generating the ensemble of compact structures a given set of helices and strands can form. The method is tested on structures composed of four alpha-helices connected by short turns. All such natural four-helix bundles that are connected by short turns seen in nature are reproduced to closer than 3.6 Angstroms per residue within the ensemble. Since s...