Fold Recognition by Combining Sequence Profiles Derived From Evolution and From Depth-Dependent Structural Alignment of Fragments

Sequence Profile From Depth-Dependent Structural Alignment of Fragments

Structure-based sequence profile for a given template structure is generated as follows. Each template structure is divided into structural fragments with a sliding window size of I_w amino acid residues (i.e., from 1 to I_w, 2 to I_w + 1, 3 to I_w + 2, …). Each structural fragment is compared with same-size fragments contained in a large database of protein structures. We measure fragment similarity by both fragment–structural and protein– environment similarities. This is accomplished by using a similarity score that weights equally the root-mean-squared distance between the two fragment structures and an exponential function that characterizes the difference between their solvent exposures. The similarity score between a template fragment and a same-size fragment from structural database is given by the equation

where d_rmsd is the root-mean-squared distance between the two fragment structures, w_d is a weight factor, ${\text{D}}_{\text{j}}^{\text{template}}$ and ${\text{D}}_{\text{j}}^{\text{database}}$ are the depth of the fragment residue j from the surface of the template structure and the depth of the corresponding residue from the surface of the protein structure in the structural database, respectively, and the summation (j = 1, 2, …., I_w) is over all the positions in the fragments. The depth of residue from surface is calculated by the method described in detail in Chakravarty and Varadarajan.⁵⁹ The basic idea is to calculate the average shortest distance of a residue from solvent water molecules. Here, we set w_d = 10 to make the two terms comparable in magnitude. The depth (in Å) is scaled by 2.8 Å, the approximate size of a water molecule. We use a window size of 9 (I_w = 9), the same size used by Simons et al. to build a structural fragment library.⁶⁰ The structure database of fragments is made of 1011 nonhomologous (less than 30% homology) proteins with resolution < 2 Å that was collected by the program PISCES (http://chaos.fccc.edu/research/labs/dunbrack/culledpdb.html).⁶¹

After a template fragment is compared against all same-size fragments in the structural database, the top 25 fragments ranked by the similarity score S_str are retained for profile construction. (One can use more or less fragments for this purpose. We did not attempt to optimize this parameter.) Because each residue position (except near the C or N terminus) associates with 9 template fragments and each template fragment has top 25 similar fragments from the structural database, there are 225 (9 × 25) sequences that can be used to compute the frequencies of the 20 amino acid residues at a given residue position (less for the four residues near the C or N terminus). The frequency profiles obtained are normalized so that the summation over 20 types of amino acid residues is equal to 1. Here and hereafter, this structure-derived frequency profile at sequence position j will be labeled as ${\text{F}}_{\text{template}}^{\text{struc}}(\text{j}).$

There exists a possible bias to the sequence profiles generated by the above method. This happens when there are several hits from the same residue in a single sequence to the same single profile position. The maximum number of such multiple hits is nine. This number is small, relative to the total of 225 sequences used in profile generation. The possible effect of such bias on fold recognition is not tested and will be a subject of further study.

Sequence Profile Derived From Sequence Library

All sequence-derived profiles are constructed by using PSIBLAST. This is done with three iterations of searching against nonredundant (NR) sequence database (ftp://ftp.ncbi.nih.gov/blast/db/FASTA/nr.gz). As in PSIPRED,⁶² the database was filtered to remove low-complexity regions, transmembrane regions, and coiled-coil segments.

Secondary Structures

The secondary structure of query sequence is predicted by a built-in simplified PSIPRED method.⁴³ The secondary structures of templates were obtained by H-bonds (DSSP-like) criteria.⁶³ Three states (helix, strand, coil) were used for all secondary structures.

The Alignment Score and the Alignment Algorithm

The alignment score for aligning query sequence position i with the template sequence position j is given by the equation

where ${\text{F}}_{\text{query}}^{\text{seq}}(\text{i})$ is the sequence-derived frequency profile of the query sequence, ${\text{M}}_{\text{template}}^{\text{seq}}(\text{j})$ is the sequence-based log odd profile (position-specific substitution matrix as in PSIPRED) of the template, ${\text{F}}_{\text{template}}^{\text{struc}}(\text{j})$ is the structure-derived frequency profile of the template, ${\text{M}}_{\text{query}}^{\text{seq}}(\text{i})$ is the sequence-derived, log odd profile (position-specific substitution matrix) of the query sequence, s_shift is a to-be-determined constant shift, w_struc and w_2ndary are two weight parameters for structure-derived sequence profiles and secondary structure profiles, respectively, and δ_si,sj is a simple function of the secondary structure element si of the query at sequence position i and sj of the template at sequence position j.

Because we use the Smith-Waterman local alignment algorithm to align profiles (see below), s_shift is used to avoid the alignment of unrelated regions. A position-dependent gap penalty is employed. No gaps are allowed if si = sj = α or si = sj = β. The gap opening (w₀) and gap extension (w₁) penalties are applied to other regions. Finally, a local–local dynamic programming method⁶⁴ is used to optimize the score that matches the query profiles with template profiles. Note that the optimization of alignment is to minimize the total alignment score due to the negative signs in equation 2.

Ranking Templates and Model Assessments

The following empirical method is used for ranking. First, a difference raw score is calculated. A difference raw score ΔS is the difference between the alignment raw score (S) and the reverse alignment raw score S_r in which the alignment is made with the reversed query sequence.⁹ If there is structural similarity between first two models ranked by ΔS (defined as nonzero MaxSub score⁶⁵), all models will be ranked by ΔS. Otherwise, two normalized scores (S_n1 and S_n2) and their corresponding Z-scores (Z₁ and Z₂) are calculated. All templates will be reranked by either Z₁ or Z₂ depending on which Z-score for the first model ranked by S_n1 and S_n2 is greater. Here, S_n1 is the raw score normalized by the full alignment length between the query and template sequences (including all gaps). The full alignment length is close to the length of longer sequence of the query and the template sequences. S_n2, on the other hand, is the raw score normalized by the alignment length excluding query end gaps. ${\text{Z}}_1(\text{i})=({\text{S}}_{\text{n}1}(\text{i})-{\text{S}}_{\text{n}1}^{\text{ave}})/{\text{S}}_{\text{n}1}^{\text{sd}}$ and ${\text{Z}}_2(\text{i})=({\text{S}}_{\text{n2}}(\text{i})-{\text{S}}_{\text{n2}}^{\text{ave}})/{\text{S}}_{\text{n2}}^{\text{sd}}$, where superscripts ave and sd denote the average and standard deviation of normalized score for all the templates.

The results of fold-recognition alignment are used to build C_α models based on template structure. The models are then assessed by the MaxSub score between the model and the known native structure. MaxSub score⁶⁵ between the predicted (model) structure and the native structure is a measure of similarity between 0.0 (no similarity) and 1.0 (perfect similarity). The value is calculated by searching the largest subset of well-superimposed residues (≤ 3.5 Å). We use MaxSub score because it is the official evaluation method used in the CAFASP (Critical assessment of fully automated protein structure prediction methods) experiments (http://www.cs.bgu.ac.il/dfischer/cafasp1/cafasp1.html).

A Note on Comparison

It should be emphasized that comparison made between this work and other published work is not a strict one. This is because it is impossible to have an exact comparison between the methods that use the time-dependent sequence and/or structural libraries.

Optimization of Parameters Using ProSup Benchmark

For the SP³ fold-recognition method, there are five adjustable parameters (w₀, w₁, w_2ndary, w_struc, and s_shift). For comparison, we also optimized the parameters for the SP (sequence profiles only, w_2ndary= w_struc = 0) and the SP² method (sequence profiles and secondary-structure profiles, w_struc = 0). For SP, position-dependent gap penalty is not used because secondary-structure information is not available. We use the ProSup benchmark set for optimizing all the parameters. This benchmark was prepared by Sippl’s group⁶⁶ to test the alignment accuracy of fold-recognition methods. The set consists of 127 pairs of proteins with “correct” alignments obtained by structural alignment program ProSup. The accuracy of an alignment was obtained by calculating the percent of matches between the “correct” alignment and the alignment made by a fold-recognition method. The optimization is started with random values for all the parameters. Then, all parameters are optimized by grid search sequentially. The optimization procedure is stopped when iterations do not improve the alignment accuracy. This procedure may lead to local minimum. Thus, several independent optimizations based on different initial values were made. The final optimized parameter sets are (6.6, 0.58, −0.9) for (w₀, w₁, s_shift) in SP, (7.8, 0.18, 0.73, −1.30) for (w₀, w₁, w_2ndary, s_shift) in SP2, and (5.2, 0.38, 0.38, 0.50, −1.15) for (w₀, w₁, w_2ndary, w_struc and s_shift) in SP³.

Table I compares the performance of SP, SP², and SP³ methods. It shows that the secondary structure information leads about 7% leap in alignment accuracy whereas the structure-derived profile introduces an additional 2–3% improvement. The performance of several other methods is also listed along with SP methods. Their results are used as a reference because ProSup was a testing benchmark for those methods. Nevertheless, a significantly better performance than the next best (SPARKS or PROSPECT II) (a 7% improvement in terms of one-to-one match) indicates that the SP³ method is promising to provide a more accurate fold-recognition alignment.

Test Set 1: SALIGN Benchmark

To test the alignment accuracy, we used the SALIGN benchmark.¹⁷ This benchmark contains 200 selected pairs of proteins that were structurally aligned by CE program.⁶⁷ The selected structure pairs have an average pair sharing 20% sequence identity and 65% of structurally equivalent C_α atoms superposed with an rmsd of 3.5 Å.¹⁷ This benchmark can be considered as an independent benchmark from the ProSup benchmark because sequence identities between any pairs of proteins from the two benchmarks are less than 40% at least for one of the proteins in the pair. Alignment accuracy for the SALIGN benchmark is assessed by calculating the fraction of the alignment that is the same as the alignment obtained from the CE program (CE overlap).

The results on CE overlap by SP methods are compared with those obtained by several other methods tested by Marti-Renom et al.¹⁷ in Table II. The SP³ method gives slightly better success rate than the best profile–profile alignment method SALIGN by Marti-Renom et al.¹⁷ who compared 13 different alignment protocols and several established methods. This is remarkable considering the fact that SP³ was trained by a different structural alignment program called ProSup whereas SALIGN was trained by and tested on the CE alignment. One-to-one matches defined by ProSup and that by the CE alignment are very different. For example, if the alignment accuracy for one-to-one match in ProSup benchmark is defined by CE alignment, the accuracy of alignment in ProSup benchmark given by SP³ will be reduced significantly from 65.3% to 49.5%.

The change of alignment accuracy from SP, SP², to SP³ in SALIGN benchmark is not as dramatic as the change in the training ProSup benchmark (Table I). The former is only 4.6% compared to 9.4% in the latter. The 4.6% improvement is more-or-less equally distributed between SP and SP² and between SP² to SP³. Nevertheless, the improvement of alignment accuracy from SP to SP³ is reproduced despite different structural alignment programs used in SALIGN and ProSup benchmarks. One important question is whether or not the differences between the performances of SP methods are statistically significant. Simple student t-test⁶⁸ based on the average and standard deviation of the differences indicates that both differences (2.5% and 2.1%) are significant at 95% confidence level.

Test Set 2: Lindahl Benchmark for Fold-Recognition Sensitivity

The Lindahl set⁵² was designed to assess the fold-recognition sensitivity. It has 976 proteins. Each protein is aligned with the rest 975 proteins. There are 555, 434, and 321 pairs of proteins in the same family, superfamily, and fold, respectively. The fold-recognition method is tested by checking whether or not the method can recognize the member of same family, superfamily or fold as the first rank or within the top five ranks. The results of SP³ are compared with several well-established methods in Table III. We stress that the comparison only serves as an approximate guide because the sequence database available for previous methods are smaller than the one used in SP³. It shows that SP³ is the most sensitive method to detect structural similarity on the fold and superfamily levels for the first rank among the eleven methods listed. For example, compared to the popular PSI-BLAST, SP³ is 10%, 28%, and 25% more sensitive in recognizing the member of same family, superfamily, and fold, respectively.

Table III shows that the performances of SP³, SPARKS, and PROSPECT II are very similar to each other. One is only a few percentage (1–3%) better than the other. This sensitivity test, however, may not reflect the true sensitivity or accuracy because the result is based on somewhat subjective SCOP classification.⁶⁹ To address this question more quantitatively, we calculated the MaxSub score between the model built from first-ranked template and the known native structure. It is found that the total number of recognized proteins (MaxSub > 0.01, a measure of sensitivity⁵³) increases from 611 in SPARKS to 665 in SP³ (a 8.6% improvement) whereas the total MaxSub score (a measure of model accuracy) increases from 325.85 in SPARKS to 349.20 in SP³ (a 7.2% increment). (Results reported here are based on C_α models generated from alignment.)

Within SP methods, SP³ improves over SP² and SP at both fold and superfamily levels. For example, 3– 4% improvements of SP³ over SP² are observed for the first ranking models at fold and superfamily levels. At the family level, SP, SP², and SP³ have similar sensitivity (between 81.3%– 82.5%). Improvement in recognition sensitivity is further confirmed based on MaxSub score. The number of the first-ranked models with MaxSub > 0.01 is 606 for SP, 638 for SP², and 665 for SP³ while the total MaxSub score increases from 328.6, 340.8, to 349.2.

Test Set 3: PROSPECTOR 3.0 Benchmark

The PROSPECTOR 3.0 Benchmark is a large benchmark of 1479 targets and 3825 templates. Each target also has a list of templates excluded due to their sequence similarity to the target. (Two targets 1ddqE and 1f5yA are removed from the original 1481 targets due to lack of a template exclusion list for these two targets.) This benchmark is an updated version from what was published.⁷⁰

Table IV compares the results of SPARKS, SP³ with that of PROSPECTOR 3.0. Based on MaxSub score, SP³ is about 15% and 9% more sensitive than PROSPECTOR 3.0 and SPARKS, respectively, and about 16% and 14% more accurate in model accuracy than PROSPECTOR 3.0 and SPARKS, respectively. SP³ also shows significant improvement (3% and 6%, respectively) in both sensitivity and accuracy over SP² and SP. (Comparison of PROSPECTOR 3.0 and SPARKS in Skolnick et al.⁷⁰ suggested that SPARKS is not as accurate as PROSPECTOR 3.0. The conclusion is different from what we obtained here. This is in part due to different definition of model accuracy and the use of different sequence library in their implementation of SPARKS.)

Test Set 4: LiveBench 8

The template library for SP³ was built as the library for SPARKS.⁴³ This was done by using the 40% representative domains of SCOP 1.61. The entire chains of multiple-domain proteins are contained in the library. The library was then updated with new proteins released after SCOP 1.61 if they have less than 40% sequence identity with the sequences already in the library. (This was done by protein sequence culling server PISCES⁶¹).

Unlike SPARKS, SP³ was not directly involved in Live-Bench test. Instead, SP³ used the exactly same template library of SPARKS for each target to “simulate” live testing. Here, all SP³ results are based on C_α models of aligned residues. Only results of top single servers are shown in Table V. Three parameters are used to compare different methods. The accuracy is characterized by the total MaxSub scores. Sensitivity is defined as the number of targets whose first-ranking models have a MaxSub score of greater than 0.01. Specificity is defined as the average number of recognized proteins that have scores better than 1–10 false positives. For 172 Livebench 8 targets, SP³ has the highest sensitivity and second highest in total MaxSub score (behind ShotGun-INBGU). Among the top single servers, ShotGun-INBGU is the only consensus method that provides consensus model from the INBGU components.⁵⁷ Others are single-method servers. It is remarkable that the accuracy of SP³ is comparable to or better than some of the consensus methods such as ShotGun-INBGU, Pmodeller3 (Total MaxSub=42.77),⁷¹ Pcons4 (42.53),⁷¹ and ROBETTA (41.79)⁷² although the model accuracy of SP³ is still about 10% less than the best consensus methods in LiveBench (e.g., ShotGun on 5 and ShotGun on 3). However, the sensitivity of SP³ (120 in 172 proteins) is the highest for all the methods (more than 40 servers) tested in LiveBench 8. The next best is 119 by a consensus method called 3D-JuryB-single. It should be cautioned, however, that only the difference between SPARKS and SP³ is statistically significant based on student-t test. The differences of performance in Live-Bench 8 between all other methods (SAM-T02, ORFeus, FFAS03, STMP, BasD, ShotGun-INBGU and SP³) are statistically insignificant.