Exact Algorithm for Generating H-Cores in Simplified Lattice-Based Protein Model

Modeling protein folding, which is the process by which a protein obtains its spacial shape, still remains a challenging problem. Protein geometry might be simplified by using the coarse-grained models. The highest level of simplification is achieved in HP-models where only polarity of amino acid residues is considered, and the unified monomers are located in nodes of some discrete lattice. One possible way of predicting the spacial structure of a protein in this model implies creating a maximally dense hydrophobic core (H-core), and fitting a protein into it afterwards. The paper proposes setups of Linear Programming (LP) problems for constructing both maximally dense H-cores and H-cores with the predefined number of contacts. Setups are developed for two lattices – Pseudo-triangular and Face-Centered Cubic. Results of the conducted experiments show that the proposed methodology is efficient enough to be utilized in the protein structure prediction process.