Eliminating superfluous neighbor pairs while threading fold models.

In this paper we address the problem of identifying which of various possible spatial residue-residue neighbor pairs are plausible physical contacts without reference to the native structure side chain geometry. We propose an algorithm that eliminates most of the implausible physical contacts from the fold models. This algorithm exploits the correlations between the amino acid side chain rotamers and the direction of the physical contacts between the amino acid side chains. We use this algorithm to "filter" the score of the sequence-to-structure alignment. Filtering is dynamic, in the sense that the set of neighbor pairs contributing to the alignment score varies during threading. Whether or not a neighbor pair contributes to the score depends on the threaded amino acids. This score filtering improves the accuracy of the predicted sequence-to-structure alignment.

Protein fold recognition by total alignment probability.

We present a protein fold-recognition method that uses a comprehensive statistical interpretation of structural Hidden Markov Models (HMMs). The structure/fold recognition is done by summing the probabilities of all sequence-to-structure alignments. The optimal alignment can be defined as the most probable, but suboptimal alignments may have comparable probabilities. These suboptimal alignments can be interpreted as optimal alignments to the "other" structures from the ensemble or optimal alignments under minor fluctuations in the scoring function. Summing probabilities for all alignments gives a complete estimate of sequence-model compatibility. In the case of HMMs that produce a sequence, this reflects the fact that due to our indifference to exactly how the HMM produced the sequence, we should sum over all possibilities. We have built a set of structural HMMs for 188 protein structures and have compared two methods for identifying the structure compatible with a sequence: by the optimal alignment probability and by the total probability. Fold recognition by total probability was 40% more accurate than fold recognition by the optimal alignment probability. Proteins 2000;40:451-462.

Filtered neighbors threading.

We present a knowledge-based threading scoring function that exploits the information about protein structure contained in residue packing/neighbor preferences. The proposed algorithm eliminates the stereochemically improbable physical contacts for each possible sequence-to-structure alignment. We use this algorithm to "filter" the score of the sequence-to-structure alignment. Filtering is dynamic, in the sense that the set of neighbor pairs contributing to the alignment score varies during threading. Whether or not a neighbor pair contributes to the score depends on the threaded amino acids. We use a detailed structure description that encodes amino acid side-chain rotamer and physical contact preferences but does not imprint the fold model with the native sequence or native physical contacts. We discretize this description to collect accurate statistics for the scoring function generation. We use the original detailed description for the neighbor filtering. On average, the filtered neighbors threading (FNT) method predicts the sequence-to-structure alignment twice as accurately as does the "standard" unfiltered neighbors threading. For the set of threadings tested by the PHDthreader method, the FNT gives predictions with a sequence-to-structure alignment accuracy of 46.9%, which amounts to a 74% improvement in alignment sensitivity compared with PHDthreader predictions. These results show that reduction of noise from the observed neighbor pair preferences by filtering leads to noticeable improvements in the predicted sequence-to-structure alignments.

Performance of threading scoring functions designed using new optimization method.

We present a new procedure for optimization of a threading scoring function. A scoring function is usually formulated in terms of the structural environment states that describe the protein fold model. We propose a method for the optimal selection of those structural environment states that naturally follows from the probabilistic description of the threading problem and is done prior to threading experiments. We demonstrate the selection of the optimal structural environment states for the solvent exposure of the amino acid position, and present the results of threading experiments performed using scoring functions designed with and without the optimization of the structural environment states. These results confirm that the optimal scoring function predicts the sequence-to-structure alignments most accurately. Threading experiments performed with 15 optimally designed scoring functions show that the correlation coefficient between the information content of the amino acid distribution that determines the scoring function and the accuracy of the optimal sequence-to-structure alignment is 0.94.