?
Techniques for Speeding up H-Core Protein Fitting
Restoration of the 3D structure of a protein from the sequence of its amino acids (“folding”) is one of the most important and challenging problems in computational biology. The most accurate methods require enormous computational resources due to the large number of variables determining a protein’s shape. Coarse-grained models combining several protein atoms into one unified globule partially mitigate this issue. The paper studies one of these models where globules are located in the nodes of the two-dimensional triangular lattice. In this model, folding is reduced to the discrete optimization problem: find positions of protein’s globules to maximize the number of contacts between them. We consider a standard procedure that finds an exact solution to this problem. It first generates an H-core—a set of positions for hydrophobic globules, which is followed by mapping of protein’s hydrophobic globules to these positions by the constraint satisfaction techniques. We propose a way to avoid unnecessary enumeration by skipping infeasible H-cores prior to mapping. Another contribution of our paper is a procedure that automatically generates constraints to simplify finding the feasible mapping of proteins globules to the lattice nodes. Experiments show that the proposed techniques tremendously accelerate the problem’s solving process.