Reconstructing protein structure from solvent exposure using tabu search

OPTIMIZATION BIAS IN ENERGY-BASED STRUCTURE PREDICTION

Physics-based computational approaches to predicting the structure of macromolecules such as proteins are gaining increased use, but there are remaining challenges. In the current work, it is demonstrated that in energy-based prediction methods, the degree of optimization of the sampled structures can influence the prediction results. In particular, discrepancies in the degree of local sampling can bias the predictions in favor of the oversampled structures by shifting the local probability distributions of the minimum sampled energies. In simple systems, it is shown that the magnitude of the errors can be calculated from the energy surface, and for certain model systems, derived analytically. Further, it is shown that for energy wells whose forms differ only by a randomly assigned energy shift, the optimal accuracy of prediction is achieved when the sampling around each structure is equal. Energy correction terms can be used in cases of unequal sampling to reproduce the total probabilities that would occur under equal sampling, but optimal corrections only partially restore the prediction accuracy lost to unequal sampling. For multiwell systems, the determination of the correction terms is a multibody problem; it is shown that the involved cross-correlation multiple integrals can be reduced to simpler integrals. The possible implications of the current analysis for macromolecular structure prediction are discussed.

On lattice protein structure prediction revisited

Protein structure prediction is regarded as a highly challenging problem both for the biology and for the computational communities. In recent years, many approaches have been developed, moving to increasingly complex lattice models and off-lattice models. This paper presents a Large Neighborhood Search (LNS) to find the native state for the Hydrophobic-Polar (HP) model on the Face-Centered Cubic (FCC) lattice or, in other words, a self-avoiding walk on the FCC lattice having a maximum number of H-H contacts. The algorithm starts with a tabu-search algorithm, whose solution is then improved by a combination of constraint programming and LNS. The flexible framework of this hybrid algorithm allows an adaptation to the Miyazawa-Jernigan contact potential, in place of the HP model, thus suggesting its potential for tertiary structure prediction. Benchmarking statistics are given for our method against the hydrophobic core threading program HPstruct, an exact method which can be viewed as complementary to our method.

QSE: A new 3-D solvent exposure measure for the analysis of protein structure

Solvent exposure of amino acids measures how deep residues are buried in tertiary structure of proteins, and hence it provides important information for analyzing and predicting protein structure and functions. Existing methods of calculating solvent exposure such as accessible surface area, relative accessible surface area, residue depth, contact number, and half-sphere exposure still have some limitations. In this article, we propose a novel solvent exposure measure named quadrant-sphere exposure (QSE) based on eight quadrants derived from spherical neighborhood. The proposed measure forms a microenvironment around Cα atom as a sphere with a radius of 13 Å, and subdivides it into eight quadrants according to a rectangular coordinate system constructed based on geometric relationships of backbone atoms. The number of neighboring Cα atoms whose labels are the same is given as the QSE value of the center Cα atom at hand. As evidenced by histograms that show very different distributions for different structure configurations, the proposed measure captures local properties that are characteristic for a residue's eight-directional neighborhood within a sphere. Compared with other measures, QSE provides a different view of solvent exposure, and provides information that is specific for different tertiary structure. As the experimental results show, QSE measure can potentially be used in protein structure analysis and predictions.

Guiding conformation space search with an all-atom energy potential

The most significant impediment for protein structure prediction is the inadequacy of conformation space search. Conformation space is too large and the energy landscape too rugged for existing search methods to consistently find near-optimal minima. To alleviate this problem, we present model-based search, a novel conformation space search method. Model-based search uses highly accurate information obtained during search to build an approximate, partial model of the energy landscape. Model-based search aggregates information in the model as it progresses, and in turn uses this information to guide exploration toward regions most likely to contain a near-optimal minimum. We validate our method by predicting the structure of 32 proteins, ranging in length from 49 to 213 amino acids. Our results demonstrate that model-based search is more effective at finding low-energy conformations in high-dimensional conformation spaces than existing search methods. The reduction in energy translates into structure predictions of increased accuracy.