LocTree3 prediction of localization

1Many experimental methods annotate protein localization, enriching resources such as SWISS-PROT. However, even for the well-studied yeast, the experimental data are not nearly complete. Bridging the sequence-annotation gap for localization, therefore, calls for cheaper and faster in silico approaches. Many machine learning methods predict the native localization of a protein from its amino acid sequence; among the best known are CELLO, WoLF PSORT, YLoc and PSORTb. A recent study suggested homology-based inference to outperform machine learning. Homology-based inference proceeds as follows: build a data set with all proteins of known localization, run a simple pairwise BLAST against this set, and predict the localization of the first hit.

2LocTree2 predicts a single localization for all proteins in all domains of life through machine learning. The method implements a hierarchical system of Support Vector Machines (SVMs) to imitate the cascading mechanism of cellular sorting. An independent, recent benchmark proved LocTree2 to be an excellent successor and/or complement to other top-of-the-line prediction methods in situations in which no experimental information is available for the query protein or its homologs.

3Here, we introduce LocTree3. It provides the web server front end for LocTree2, and improves over LocTree2 by including information about homologs if available. Thereby, LocTree3 combines ‘the best of both worlds’, employing homology when possible and machine learning otherwise. The major steps of improvement are as follows: (i) inclusion of annotation transfer from close homologs with experimentally annotated localization through PSI-BLAST; (ii) runtime reduction of LocTree2 by using a new fast implementation of the SVM profile kernel; (iii) Gene Ontology annotations for prediction results; (iv) caching of the results for faster processing of the repeated searches.

4The number of proteins with experimental annotation for a single localization in SWISS-PROT release 2011_04 was 34 583 for eukaryotes (18 localization classes, visualized in Figure 2), 4765 for bacteria (six classes: cytosol, plasma membrane, periplasmic space, outer membrane, fimbrium and extra-cellular) and 237 for archaea (three classes: cytosol, plasma membrane and extra-cellular). LocTree2 was developed on sequence-unique subsets with 1682 eukaryotic, 479 bacterial and 79 archaeal proteins (Supplementary Table S1, Supporting Online Material). Sequence-redundancy was reduced at HVAL ≤ 0 through UniqueProt. This is commonly done because the bias in data sets from sequence similarity often overestimate performance. However, in order to assess the power of homology-based inference, we had to accept some redundancy because homology-based inference performed below the level of random across sequence-unique proteins (Supplementary Table S2). We accomplished this by running the sequence-unique 1682 eukaryotic proteins against all experimentally annotated proteins, i.e. against the same release of SWISS-PROT putting the redundancy back in to enable PSI-BLAST lookups. For 995 of the 1682, PSI-BLAST found a non-trivial (removal of query protein) at E-value ≤ 10−3 (,; for 687 it did not.

5For further testing, we added three new data sets. We collected all proteins for which experimental annotations had been added between releases 2011_04 and 2013_11. We redundancy reduced those at HVAL ≤ 0. This gave the sets New2013_hval0 (273 for eukaryotes, 57 for bacteria). Additional redundancy reduction to LocTree3 development data provided too small sets (32 eukaryotic and two bacterial proteins) for reliable performance estimates. Next, we simulated the question ‘how well the method will perform on the next 1000 new proteins?’ by simply monitoring all proteins added since we began collecting the data for this manuscript, i.e. the proteins added since 2013_11 (New2014 with 198 eukaryotic proteins and too few in bacteria to proceed). Finally, we investigated a third set with all human proteins (Supplementary Table S3). We deliberately kept the ‘redundancy’ in this set that exists on the level of an organism. Note that throughout we have considered only proteins with single experimental annotations. Our preliminary analysis of proteins with multiple annotations suggested these to constitute a small set of proteins with many problematic annotations (Supplementary Section S1).

6Homology-based inference: We transferred localization annotations by homology through PSI-BLAST. For all proteins with experimentally known localization, we generated PSI-BLAST profiles using an 80% non-redundant database combining UniProt and PDB with two iterations and E-value ≤ 10−3. These profiles were then aligned against all proteins with experimental annotation of a single localization in SWISS-PROT release 2011_04. PSI-BLAST hits to the input protein were excluded.LocTree2 utilizes a hierarchical system of SVMs. At all levels of the tree are binary decisions, which are made by searching through proteins of annotated localization with short stretches of k-consecutive residues (k = 3 for archaea, 5 for bacteria and 6 for eukaryota). The most informative k-mer hit decides on ‘left or right’ for each fork in the tree until reaching a leaf, i.e. the final predicted localization class.LocTree3: Our final method, LocTree3, combines PSI-BLAST and LocTree2 in the settings where they perform best. A single parameter chooses: homology-based inference, if a profile-2-sequence PSI-BLAST hits at E-value ≤ 10−3, else: LocTree2 (‘Results’ section and Supplementary Figures S1 and S2).Public methods (CELLO 2.5, WoLF PSORT, YLoc, PSORTb 3.0): We compared LocTree3 to four publicly available leading prediction methods: CELLO 2.5, WoLF PSORT, YLoc and PSORTb 3.0. If WoLF PSORT or CELLO 2.5 predicted multiple locations, and one of those was correct, we always considered the prediction fully correct. Furthermore, these two methods distinguish cytoskeleton and cytoplasm; here, we considered both as cytosolic. Because no method other than LocTree2/3 distinguishes between membranes other than the cell membrane in eukaryotes, we merged these two classes, i.e. treated nuclear and nuclear-membrane proteins as identical. Plastid and chloroplast proteins were also merged into one class for a comparison of LocTree3 to other methods. For a comparison with CELLO 2.5 and PSORTb 3.0 we combined bacterial secreted and fimbrium proteins into one class and differentiated between Gram-positive and Gram-negative proteins according to Yu et al..

7Homology-based inference: We transferred localization annotations by homology through PSI-BLAST. For all proteins with experimentally known localization, we generated PSI-BLAST profiles using an 80% non-redundant database combining UniProt and PDB with two iterations and E-value ≤ 10−3. These profiles were then aligned against all proteins with experimental annotation of a single localization in SWISS-PROT release 2011_04. PSI-BLAST hits to the input protein were excluded.

8LocTree2 utilizes a hierarchical system of SVMs. At all levels of the tree are binary decisions, which are made by searching through proteins of annotated localization with short stretches of k-consecutive residues (k = 3 for archaea, 5 for bacteria and 6 for eukaryota). The most informative k-mer hit decides on ‘left or right’ for each fork in the tree until reaching a leaf, i.e. the final predicted localization class.

9LocTree3: Our final method, LocTree3, combines PSI-BLAST and LocTree2 in the settings where they perform best. A single parameter chooses: homology-based inference, if a profile-2-sequence PSI-BLAST hits at E-value ≤ 10−3, else: LocTree2 (‘Results’ section and Supplementary Figures S1 and S2).

10Public methods (CELLO 2.5, WoLF PSORT, YLoc, PSORTb 3.0): We compared LocTree3 to four publicly available leading prediction methods: CELLO 2.5, WoLF PSORT, YLoc and PSORTb 3.0. If WoLF PSORT or CELLO 2.5 predicted multiple locations, and one of those was correct, we always considered the prediction fully correct. Furthermore, these two methods distinguish cytoskeleton and cytoplasm; here, we considered both as cytosolic. Because no method other than LocTree2/3 distinguishes between membranes other than the cell membrane in eukaryotes, we merged these two classes, i.e. treated nuclear and nuclear-membrane proteins as identical. Plastid and chloroplast proteins were also merged into one class for a comparison of LocTree3 to other methods. For a comparison with CELLO 2.5 and PSORTb 3.0 we combined bacterial secreted and fimbrium proteins into one class and differentiated between Gram-positive and Gram-negative proteins according to Yu et al..

11The reliability of a prediction is given through a reliability index ranging from 0 (weak prediction) to 100 (confident prediction). For LocTree2, the reliability indices are taken directly from its output. For homology-based inferences from PSI-BLAST, the reliability index was compiled as a simple function of the percentage pairwise sequence identity (PIDE) with a threshold at the saturation of PIDE ≤ 20 (Supplementary Figure S1).

12The performance for a single localization class L was expressed using accuracy (often also referred to as precision) and coverage (often also referred to as recall): with: TP, the true positives (i.e. the number of proteins predicted and observed in localization L); FP, the false positives (i.e. the number predicted in L and observed in non-L); FN, the false negatives (i.e. the number observed in L and predicted in non-L). We measured the overall performance by the n-state accuracy Qn:

13Standard errors were estimated over 1000 bootstrap sets, i.e. randomly select 15% of proteins without replacement from the original data set (in our experience this non-standard procedure yields more long-lived estimates). For each bootstrap set, the performance xi (e.g. accuracy) is estimated through its difference from the overall performance. These 1000 estimates provided the standard deviation of xi with the typical standard error, where n is the number of bootstrap sets:

14For sequences with pre-calculated PSI-BLAST profiles the LocTree2 runtime was measured on a Dell M605 machine with a Six-Core AMD Opteron processor (2.4 GHz, 6MB and 75 W ACP) running on Linux.

15Homology-based inference for a protein of unknown localization U implies to find a protein with known localization K that is sequence similar to U (e.g. sim(U,K) > T and U ≠ K). We experimented with alternative solutions, but avoided to ‘over-optimize’. We simply chose the threshold T to be the standard PSI-BLAST E-value of 10−3 (Supplementary Figure S2, Supporting Online Material). This typically gave several hits: choosing the one with highest percentage pairwise sequence identity slightly outperformed taking the hit with best E-value (Supplementary Table S4).

16Surprisingly, homology inference outperformed our advanced machine learning tool LocTree2 for half of our original data (995 of 1682 eukaryotic and 202 of 479 bacterial proteins, Table 1). However, when we forced PSI-BLAST to return hits for all proteins, LocTree2 consistently outperformed the PSI-BLAST protocol (Table 1).

17These first results suggested a simple protocol: use PSI-BLAST if applicable, LocTree2 if not. We dubbed the method that realized this protocol LocTree3. The combination outperformed both its sources, reaching an overall performance of Q18 = 80 ± 3% in classifying eukaryotic proteins in 18 classes (10 non-membrane and 8 membrane classes) and bacterial proteins in six classes at Q6 = 89 ± 4% (Table 1). LocTree3 predicted eukaryotic extra-cellular proteins best (Acc: 88% and Cov: 96%), followed by nuclear proteins (Acc: 81% and Cov: 86%; Supplementary Figure S3A, Supplementary Table S5). For bacteria, the prediction of plasma membrane proteins was most accurate (Acc: 96% and Cov: 95%), followed by cytosolic proteins (Acc: 91% and Cov: 90%; Supplementary Figure S3B, Supplementary Table S5).

18For both eukaryotes and bacteria, LocTree3 significantly outperformed its competitors on all data sets tested (Table 2 and Supplementary Table S6). Finally, we used all experimentally annotated human proteins to benchmark the methods and found LocTree3 again to provide the most accurate predictions (Supplementary Table S7). The complete human set contained 5016 proteins; LocTree3 reached Q10 = 89%, followed by YLoc, Cello 2.5 and Wolf Psort with 76, 75 and 71% respectively (Supplementary Table S7). LocTree3 appears best when compared on the same number of classes, and it also is the method that distinguishes in most detail with 18 classes for eukaryotes (compared to 12 for Cello 2.5 and Wolf PSORT; 11 for YLoc).

19LocTree3 measures the confidence of each prediction through a reliability index (RI) that scales from 0 (low confidence) to 100 (high confidence). Technically, RI reflects the strength of a prediction. Our task as developers was to provide a measure that allows users to translate this strength into estimates for performance. Indeed, our RI strongly correlated with accuracy (Figure 1): when choosing the 50% most strongly predicted eukaryotic proteins, 95% of the predictions were correct (RI > 70, Figure 1: black arrow). For bacterial proteins the same level of accuracy was also reached for about half of all proteins (but at RI > 80, Figure 1: gray arrow). For users not familiar with reliability indices it is important to point out that the choice of the ‘top N’ does not require knowing the answer. Instead, any user can make this choice for any prediction and can read of Figure 1 what to expect from the choice.

20At this point, the PredictProtein cache holds >11.7 million pre-computed PSI-BLAST profiles that are quickly retrieved by LocTree3. Due to a recent acceleration of the profile kernel, the runtime of LocTree2 could be reduced by up to 100 times, such that now an average SVM kernel lookup takes about 90 s for a typical eukaryotic protein (bacteria: 4s, archaea: 2s).

21Due to considerable ‘start-up’ overhead, the runtime increases sub-linearly with the number of queries. This renders the server fit for queries with entire proteomes, typically requiring few minutes for archaeal, <1 h for bacterial and <1 day for eukaryotic proteomes. If the PSI-BLAST profiles have to be created first, runtimes increase manifold, as creating a profile takes 10–500 times longer than running LocTree2. Interested users may download the LocTree3 Debian package from the web server and run it on their machines.

22Users submit one or more FASTA-formatted protein sequences. For each sequence, the server first checks for the pre-calculated results in the PredictProtein cache. If available, the result is returned immediately (minus queue waiting time); if not, the server retrieves a PSI-BLAST profile through the PredictProtein pipeline. The profile is used to identify hits in a database of experimentally annotated proteins. If no hits are identified, the profile triggers a de novo prediction by LocTree2.

23For every query protein, the result contains four basic values: (i) the protein identifier as provided by the user, (ii) the reliability score of a prediction on a 0–100 scale with 100 being the most confident prediction, (iii) single predicted localization class and (iv) GO term(s) and GO identifier(s) matching the predicted class. Every result is supported by the information on whether it comes from a PSI-BLAST homology search or a LocTree2 de novo prediction. In case of the former, the web site provides ‘per click’ on the prediction result the experimental SWISS-PROT annotation of the best hit and its PSI-BLAST alignment to the query protein. In case of the latter, ‘the click’ on the result will forward to the visual representation of the LocTree2 decision tree and the decision path leading to the final prediction. In addition, every result is supported by a schematic representation of the biological cell highlighting the predicted localization (Figure 2).

24LocTree3 predictions for over 1000 complete eukaryotic and prokaryotic proteomes are available on the web server (http://rostlab.org/services/loctree3/proteomes/). Predictions are based on sequence sets from the European Bioinformatics Institute (EBI: http://www.ebi.ac.uk/genomes/ and http://www.ebi.ac.uk/reference_proteomes/). The high-throughput annotation and prediction of protein sub-cellular localization allows organism-wide comparisons of protein localization patterns and the reconstruction of evolutionary relations (Goldberg et al., in preparation). Predictions for the newly completed proteomes will be added to the web server on a semi-annual basis.

25PSI-BLAST has certainly changed the way we do sequence analysis more than any tool (possibly excluding PubMed and Google). Furthermore, this tool has been improving continuously since its first publication in 1997 adding important value beyond that from growing databases. LocTree2 uses advanced SVM profile kernels. Although it explicitly uses local sequence similarity, LocTree2 arguably falls into the class of de novo methods simply because it reaches its predictions through levels of sequence similarity that are not available directly from sequence comparisons. Nevertheless, we found that a simple PSI-BLAST protocol could outperform LocTree2 for about half of the proteins in our data set (Table 1), an observation in line with the findings of Imai and Nakai. Unfortunately, homology-based inferences became random for the other proteins, dropping the overall average substantially below that for LocTree2 (Table 2). Thus, it would be a very bad idea to annotate an entire proteome only with homology-based inference.

26Our new method LocTree3 successfully navigates a path through homology-based and de novo prediction of localization (Tables 1-2, Supplementary Tables S5–S7, Section S2). The method is so good that it reaches 18-state overall accuracy (Q18, Equation (3)) >95% for half of all the proteins that are most strongly predicted, i.e. have highest reliability (Figure 1). For any new query, users can read off the results whether or not their protein is likely to fall into this top set of ‘>95%’ (RI > 70 for eukaryotes, RI > 80 for bacteria, Figure 1), and whether the prediction comes from a homology search with PSI-BLAST or a de novo prediction with LocTree2. For instance, LocTree3 predicts 77% of the entire proteome in human through homology-based inference (a few other highlights from Supplementary Table S8: yeast 68%, Arabidopsis 61%, Caenorhabditis elegans 47%). However, for yeast only 17% of the predictions originated from direct homology inference, the remainder came from direct experimental annotations (Supplementary Table S8). For human, the corresponding numbers were 30% experimental, 47% through homology inference (Supplementary Table S8). Unfortunately, LocTree2 cannot recover for mistakes made by the homology lookup and all our assessment is based on taking the homology lookup when available. Investigating reasons why homology-based inference was wrong did not give a clear answer (Supplementary Section S3). Due to its high overall performance, reduced prediction time and cached prediction results, LocTree3 web server optimizes well for the handling of large-scale data. Therefore, this web server and its downloadable software should provide an ideal starting point to aid the prediction of protein function through localization predictions.

27Supplementary Data are available at NAR Online.