BACKGROUND
protein subcellular localization  is important to elucidate protein functions as proteins cooperate towards a common function in the same subcellular compartment  <cit> .
it is also essential to annotate genomes, to design proteomics experiments, and to identify potential diagnostic, drug and vaccine targets  <cit> .
determining the localization sites of a protein through experiments can be time-consuming and labor-intensive.
with the large number of sequences that continue to emerge from the genome sequencing projects, computational methods for protein subcellular localization at a proteome scale become increasingly important.
most existing psl predictors are based on machine learning algorithms.
they can be categorized by the feature sets used for building prediction models.
a group of methods use features derived from primary sequence  <cit> ; some utilize various biological features extracted from literature or public databases  <cit> .
other features are also used in different methods, e.g., phylogenetic profiling  <cit> , domain projection  <cit> , sequence homology  <cit> , and compartment-specific features  <cit> .
a simple and reliable way to predict localization site is to inherit subcellular localization from homologous proteins.
therefore, in  <cit>  a hybrid method was proposed, which combined an svm based method with a sequence comparison tool to find homology to improve the performance.
however, some homologous proteins are not similar in sequences, but in structures.
for example, the sequence identity between proteins 1aab and 1j <dig> is only  <dig> % but they are structurally homologous and classified into the same family  in the scop classification.
for such cases, it is difficult to discover the homologous relationship using sequence comparison methods.
profile-profile alignment methods  <cit>  are capable of identifying remote homology; nevertheless, they are relatively slow.
most of the psl prediction systems are established particularly for single-localized proteins.
a significant number of eukaryotic proteins are, however, known to be localized into multiple subcellular organelles  <cit> .
in fact, proteins may simultaneously locate or move between different cellular compartments and be involved in different biological processes with different roles.
this type of proteins may take a high proportion, even more than 35%  <cit> .
in addition, the majority of existing computational methods have the following disadvantages  <cit> : 1) they only predict a limited number of locations; 2) they are limited to subsets of proteomes which contain signal peptide sequences or with prior structural/functional information; 3) the datasets used for training are for specific species, which is not sufficiently robust to represent the entire proteomes.
thus, most of the computational methods are not sufficient for proteome-wide prediction of psl across various species.
thus in this study, we propose a knowledge based approach, called knowpredsite, using local sequence similarity to find useful proteins as templates for site prediction of the query protein.
it is designed to predict localization site of single- and multi-localized proteins and is applicable to proteome-wide prediction.
furthermore, it only requires protein sequence information and no functional or structural information is required.
notably, prediction results can be explained by the template proteins which are used to vote for the localization sites.
the knowledge-based prediction scheme has been shown to be effective in predicting protein secondary structure  <cit>  and local structure  <cit> .
to evaluate our knowledge-based site prediction method, we used the ngloc dataset  <cit>  to perform ten-fold cross validation to compare with existing methods.
the dataset consists of ten subcellular proteomes from  <dig> species with single- and multi-localized proteins.
knowpredsite achieved  <dig> % accuracy for single-localized proteins and  <dig> % accuracy with both sites correctly predicted for multiple localized proteins.
methods
the main idea behind knowpredsite
knowpredsite predicts psl based on a knowledge base, which is constructed to capture local sequence similarity of two proteins even when they have sequence identity less than 25%.
however, such local similarity is difficult to be detected using the traditional alignment algorithm due to the low sequence similarity.
therefore we adopt the transitivity relationship, which was firstly used in  <cit>  for clustering protein sequences, to capture local similarity between protein sequences.
transitivity refers to deducing a possible similarity between protein a and protein c from the existence of a third protein b, such that a and b as well as b and c are homologues if the sequence identity between a and b as well as that between b and c is above the predefined threshold.
figure  <dig> shows an example of transitivity relationship among protein a, protein b, and protein c. protein a and protein b share sequence identity of 34%, and protein b and protein c share sequence identity of 27%, whereas protein a and protein c only share sequence identity of 12%.
using the transitivity relationship, remote homologous relationship and local similarity between protein a and protein c can be detected.
in this paper, we apply the transitivity concept to peptide fragments instead of the protein sequences to obtain local similarities between remotely homologues.
protein a and protein c share local similarity if there is a peptide fragment similar  to subsequences in protein a and protein c. figure  <dig> illustrates the idea, in which protein a and c are aligned with protein b <dig> and protein b <dig> .
if there is a peptide fragment shared by both b <dig> and b <dig>  the corresponding peptide fragments in protein a and protein c are inferred as locally similar between protein a and protein c. the shared peptide may represent a possible sequence variation in evolution.
moreover, if protein a and protein c are remotely homologous, there is likely more "shared" sequence fragments in different protein b's to characterize their similarity.
however, not all such proteins a and c which share local similarity are homologous.
some local similarities may arise without common ancestry.
short sequences may be similar by chance, and sequences may be similar because both are selected to bind to a particular protein.
in order to avoid ambiguity, we define such proteins a and c which share local similarity as "related sequences".
construction of the knowledge base spkb
given a dataset of proteins with known localization sites, we construct a knowledge base, called similar-peptide knowledge base .
the dataset used to construct spkb will be described in the result section.
to construct the knowledge base, we first use the native sequence of each protein in the dataset to extract the fixed-length peptide fragments by using a sliding window of length w. each peptide sequence as well as its protein source and the localization site information are stored in spkb.
since the performance of knowledge-based methods relies on the size of the knowledge base, we then perform psi-blast search with parameters j =  <dig>  e =  <dig>  on each protein in the dataset against the ncbinr database to find similar sequences.
since the ncbinr database contains only the protein sequence information, the localization annotation of peptides generated by similar sequences is determined as follows.
specifically, given a query protein sequence q, psi-blast would generate a large number of significant local pairwise alignments called high-scoring segment pairs  between q and its similar proteins.
an example of an hsp is shown in figure  <dig>  statistically significant blast hits usually signify sequence homology.
we assumed that in an hsp, the similar peptide sequences in the counterpart sequence  represent the possible sequence variations to the corresponding peptide in the query , i.e., the protein q. we use the same sliding window of length w to generate all peptide fragments in each hsp.
two amino acids aligned together in an hsp are said to be interchangeable if they have a positive score in the blosum <dig> .
the number of amino acid pairs being interchangeable within a sliding window represents the similarity level of the two peptide fragments.
a peptide in sbjct is called a similar peptide if it has at least k residues interchangeable to those of the corresponding peptide in query.
a similar peptide is used to signify local sequence similarity between sbjct and query and thus is assigned the localization annotation of the protein q.
performing psi-blast search for all proteins in the dataset, we can generate a huge number, possibly multi-millions, of similar peptides with localization annotation.
each record in the knowledge base is indexed by a similar peptide, and stores its similar peptide sequences and protein sources , similarity level and localization site information .
note that a similar peptide may occur multiple times in different hsps of a single psi-blast search result, i.e., derived from different similar proteins found in the psi-blast search.
we cluster them together and store the frequency in the peptide record.
table  <dig> shows a record of the similar peptide myskill , which is generated by performing psi-blast search on the three proteins  with known localization sites, respectively.
the frequencies of myskill in the psi-blast search results of proteins a, b, and c are  <dig>   <dig>  and  <dig>  respectively.
the localization site information is inherited from the three protein sources.
three protein sources with known localization sites contain peptides that are aligned and similar to the peptide myskill in their hsps.
the similarity level indicates the number of amino acid pairs that are interchangeable between the native peptide sequence and the similar peptide sequence.
the frequency represents the number of occurrences they are aligned in hsps.
knowpredsite: a localization prediction method using spkb
the main idea of knowpredsite is illustrated in figure  <dig>  given a target protein t, whose localization annotation is unknown and to be predicted, we perform psi-blast search and use the same procedure as described in the last subsection for knowledge base construction to generate all similar peptides of t and their frequencies from its native sequence and hsps.
each similar peptide hp is then matched against spkb, and the peptide record with index hp is called a hit.
for each hit, we calculate two types of scores associated with each localization site i: the voting score si and the confidence score cs.
the calculation of the voting score si is as follows: let f denote the frequency of hp found in all t's hsps.
for each record in spkb, we calculate the score wi associated with each localization site by summing up the frequencies of the similar peptides that contain the specific site.
for example, for the peptide record myskill shown in table  <dig>  the score of cytoplasm is  <dig> , and those of nuclear and extracellular are  <dig> and  <dig>  respectively.
then the voting score si is defined as f multiplied by .
for example, if myskill is a similar peptide of t and its frequency is  <dig> in t's hsps, then the voting scores of cytoplasm, nuclear, and extracellular are  <dig>  ,  <dig>  , and  <dig>  , respectively, while those of other localization sites are all  <dig>
the localization site prediction of the protein t is determined by the confidence score cs, which is the total voting score aggregated from all hit records.
finally, each cs is divided by the summation of all frequencies f of all t's hits and then multiplied by  <dig> to normalize the confidence score in the range of  <dig> and  <dig>  knowpredsite predicts t being localized into the site with the highest confidence score for single-localized proteins or into the sites with the two highest confidence scores for multi-localized proteins .
to differentiate single-localized proteins from those that are multi-localized, we followed king and guda's method  <cit>  to calculate the multi-localized confidence score  associated with a protein t, which gives a relative measure of the likelihood that the protein t is multi-localized.
it is derived from the two highest confidence scores  and is defined as follows:
and mlcs is bounded by  <dig>  i.e., when the calculated mlcs is over  <dig>  it is assigned  <dig>
blast-hit prediction method
since blast is the most popular method for sequence comparison, we implemented a simple prediction method based on the blast search result.
given a dataset of proteins with known localization site, to predict the localization site of a test protein t we first perform the blast search against the dataset and then assign the localization annotations of the best blast hit to the protein t. if there is no hit at the e-value cutoff  <dig> , no annotation will be assigned to the protein t. as reported by jones and swindells, the e-value of  <dig>  generally produces a safe searching  <cit> .
the performance of blast-based prediction method is usually treated as the baseline to compare with those of other methods  <cit> .
evaluation measure
the performance is estimated using the following measurements.
to assess the performance in each localization site, precision, accuracy and matthew's correlation coefficient  are calculated by equations  to , respectively.
the overall accuracy is defined in equation .
where tpi, tni, fpi, fni, and ni are, respectively, the number of true positives, true negatives, false positives, false negatives, and proteins in localization site i. mcc, which considers both under- and over-predictions, provides a complementary measure of the predictive performance, where mcc =  <dig> indicates a perfect prediction, mcc =  <dig> indicates a completely random assignment, and mcc = - <dig> indicates a perfectly reverse correlation.
RESULTS
knowpredsite was implemented as a parallel program under the linux environment.
it was implemented using c++ and mpich library.
we used the ngloc dataset  <cit>  to construct the knowledge base and test the performance of knowpredsite.
the dataset is compiled from  <dig> different species and contains  <dig> protein sequences , including  <dig> single localized proteins and  <dig> multi-localized proteins.
there are ten different subcellular locations among these proteins, which are cytoplasm , cytoskeleton , endoplasmic reticulum , extracellular , golgi apparatus , lysosome , mitochondria , nuclear , plasma membrane , and perixosome .
we conducted two types of experiment on the dataset.
first, in order to take advantages of local similarities from as many proteins as possible, we conducted the leave-one-out cross validation experiment to determine the parameters and to evaluate the performance of knowpredsite.
in this experiment, each protein was in turn used as the test protein and the remaining  <dig> proteins were used to construct the knowledge base.
second, we compared the performance of knowpredsite with existing methods.
since the dataset is from ngloc and ngloc has been shown to be better than psort  <cit> , ptarget  <cit>  and ploc  <cit>  using the same dataset, we directly compare knowpredsite against ngloc using ten-fold cross validation.
in this experiment, all proteins were partitioned into  <dig> subsets, and each subset was in turn used as the test set and the remaining nine subsets were used to construct the knowledge base.
determining window size w and similarity threshold k for knowpredsite
knowpredsite aims to utilize the localization annotations of similar peptides.
the determination of similar relations, which depends on the window size w and the threshold of similarity level k, can affect the performance of knowpredsite.
using a smaller w, similar peptides have a higher probability to be hit against the knowledge base; however, shorter peptide sequences are likely to appear in many unrelated proteins.
given a fixed w, there is also a trade-off in choosing the threshold of similarity level k. a smaller k produces looser similarity relations, which leads to extracting more, but less reliable, similar peptides.
to make an appropriate selection of w and k, we conducted a leave-one-out cross validation experiments on only the single-localized proteins in the ngloc dataset for w ranging from  <dig> to  <dig> and k ranging from  <dig> to w.
overall accuracy
overall accuracy
the combination of w =  <dig> and k =  <dig> provides the best accuracy.
some results are shown to have identical overall accuracies due to the rounding off to the first decimal place.
prediction performance of knowpredsite
after the best parameters have been determined, we conducted a ten-fold cross validation experiment on the entire dataset to compare knowpredsite with ngloc and blast-hit prediction.
we used the top n accuracy for evaluation, where n ranges from  <dig> to  <dig>  a protein is considered to be correctly predicted when the real localization site rank among the top n of the predicted sites.
.)
notably, for multi-localized proteins, the accuracy is measured in two ways: first, at least one site correctly predicted and second, both sites correctly predicted.
using the first measurement, a true positive is a multi-localized protein with at least one localization site correctly predicted; whereas a true positive using the second measurement is a multi-localized protein with both sites correctly predicted.
the prediction performance of knowpredsite, ngloc, and blast-hit is summarized in table  <dig>  in which knowpredsite performance is reported with ten-fold cross validation and leave-one-out cross validation as denoted by #knowpredsite and *knowpredsite, respectively.
it is observed that knowpredsite outperforms ngloc and blast-hit.
multi-localized
multi-localized
*knowpredsite represents the experiment result using leave-one-out cross validation; #knowpredsite represents the experiment result using 10-fold cross validation.
for single-localized proteins, the overall accuracies of knowpredsite are from  <dig>  to  <dig>  when the correct prediction is considered within the top  <dig> to top  <dig> most probable sites.
those of ngloc are from  <dig> % to  <dig> %.
the accuracy of blast-hit is  <dig> %, which means  <dig> % of single-localized proteins could be correctly predicted by blast searches.
it is noteworthy that  <dig> sequences among all single-localized proteins failed to find significant similar proteins by blast-hit method; however,  <dig> % of them were correctly predicted by knowpredsite.
it shows that the local similarity helps identify related sequences for subcellular localization prediction.
the experiment result shows that knowpredsite has much higher accuracy on multi-localized proteins than the other methods.
using the first accuracy measurement, i.e., at least one site correctly predicted, knowpredsite achieves more than 90% of the top  <dig> accuracy, which is higher than ngloc by  <dig> %.
using the tighter second accuracy measurement, knowpredsite achieves  <dig> % of the top  <dig> accuracy, which is higher than ngloc by  <dig> %.
further observing the top n accuracy, we find that knowpredsite is more able to narrow down the number of false positives than ngloc.
the top  <dig> and top  <dig> accuracies of the blast-hit method are  <dig> % and  <dig> % for the two accuracy measurements.
notably,  <dig> proteins among all multi-localized proteins failed to find any significant blast hit; however,  <dig> % and  <dig> % of them were correctly predicted by knowpredsite using the two accuracy measurements, respectively.
site-specific prediction performance
in contrast to the overall accuracy of the dataset reported in table  <dig>  we further analyze the prediction performance on each of the  <dig> distinct localization sites.
the results are summarized in table  <dig>  among the  <dig> localization sites, the precision ranges from  <dig> % to  <dig> % and the accuracyi ranges from  <dig> % to  <dig> %.
it is observed that higher occurrence of the localization site, e.g., exc  and pla , leads to better prediction, e.g., the precision and accuracy on exc are  <dig> % and  <dig> %, respectively.
low occurrence of the localization site can deteriorate prediction, for example, csk  and gol  have mcci of  <dig>  and  <dig> , respectively.
however, if the similar peptide records of a site have higher specificity, prediction performance can be good despite low occurrence.
for example, the precision and accuracy on lys  and pox  are  <dig> % and  <dig> %, and  <dig> % and  <dig> %, respectively.
furthermore, it is noteworthy that although cyt represents  <dig> % of the dataset, its mcci is  <dig> , much lower than other highly occurring sites.
its low mcci is due to low precision since knowpredsite yields more false positives for cyt.
high false positives usually occur when the similar peptide records of a site have lower specificity and higher diversity.
as a result, proteins of other localization sites are misclassified as cyt.
mcc
i
evaluation of the multi-localized confidence score
a significant number of eukaryotic proteins are known to be localized into multiple subcellular organelles; therefore, it is important to differentiate single-localized proteins from multi-localized proteins.
we used the entire ngloc dataset to compare different mlcs thresholds on the correct distinction between single-localized and multi-localized proteins.
specifically, we used the portions of true positives in the multi-localized proteins and true negatives in the single-localized proteins as the performance measures.
a true positive represents a multi-localized protein whose mlcs is above the threshold and a true negative represents a single-localized protein whose mlcs is below the threshold.
we illustrate the cumulative percentages of true positive and true negative versus the mlcs threshold in figure  <dig>  which shows that the true negative curve is increasing along the mlcs axis whereas the true positive curve is decreasing.
if the mlcs threshold is set to be  <dig>   <dig> % of multi-localized proteins are true positives and  <dig> % of single-localized proteins are true negatives.
it shows that  <dig> % of multi-localized proteins obtained mlcs of  <dig> or better, whereas only  <dig> % of single-localized proteins within this range.
if the mlcs threshold is set to be  <dig>   <dig> % of multi-localized proteins are true positives and  <dig> % of single-localized proteins are true negatives.
in ngloc, the best result shows that 76% of multi-localized proteins belong to true positives and 81% of single-localized proteins belong to true negatives when  <dig> of mlcs threshold is applied.
the result shows that knowpredsite better differentiate multi-localized proteins from those that are single-localized.
discussion
unlike most machine learning methods that the parameters of the prediction models are not biologically interpretable, the prediction result of knowpredsite is interpretable and the prediction process is transparent and traceable.
to predict the localization sites of a protein, knowpredsite shows the template sequences and their associated contributive confidence scores for a query protein.
such information is useful for interpretation of the prediction results.
in this section, we select the four sequences ef1a2_rabit, rash_human, mca3_mouse, and cfdp2_bovin from the ngloc dataset, to demonstrate the interpretation of knowpredsite prediction results.
the prediction result of each of the first three proteins and its template sequences extracted from the knowledge base used for prediction are shown in table  <dig>   <dig>   <dig>  respectively.
in each table, the prediction result shows the mlcs and the confidence score of each localization site that the query protein would be localized into.
moreover, the template proteins which are used to vote for the localization sites are shown in each table.
we only list the top eight template proteins which contribute most to the confidence scores of the query sequence.
for each template sequence, its contribution to confidence score of each localization site and the sequence identity to the query protein calculated by clustalw  are shown.
*: correct answer; si: sequence identity.
*: correct answer; si: sequence identity.
*: correct answer; si: sequence identity.
in the example of ef1a2_rabit shown in table  <dig>  knowpredsite predicts it being single-localized at cytoplasm  since mlcs is very low  and cyt has the highest confidence score.
however, the localization site of ef1a2_rabit reported in the ngloc dataset is nuclear .
examining the eight template proteins, we find that they all have high sequence identities with ef1a2_rabit and most of them are localized into cyt except ef1a2_rat localized into nuc.
according to the gene ontology annotation, it is localized into cyt and nuc, which are the two sites with the highest confidence scores in knowpredsite's prediction.
in the example of rash_human shown in table  <dig>  knowpredsite predicts rash_human being localized into plasma membrane  and cytoplasm .
however, the correct localization site is cytoplasm and golgi apparatus .
referring to the prediction result, the confidence score of pla is much higher than those of cyt and gol.
it is also observed that most of the template proteins are localized into pla.
according to the annotation in gene ontology and swissprot, rash_human is localized into pla and gol, and the template protein, rasn_human, is also localized into pla and gol.
if applying the new annotation data, knowpredsite can predict rash_human correctly.
as for mca3_mouse shown in table  <dig>  knowpredsite predicts its mlcs  <dig> and it being localized into cytoplasm  and nuclear  correctly.
examining the template proteins, we observe that knowpredsite identifies some related proteins, i.e., which have the same localization with the query protein.
ef1g1_yeast and nu155_rat, even though they share very low sequence identity  <dig> % and  <dig> %, respectively, with the query protein.
notably, the two template proteins rank second and seventh, respectively, among all template proteins.
furthermore, though gsta_plepl has higher sequence identity  with the query protein than ef1g1_yeast, the confidence score contributed by ef1g1_yeast is much higher than that by gsta_plepl .
it shows that the contributive confidence score is not necessary to be positively correlated with the sequence identity when template sequences are dissimilar with the query sequence.
in this example, ef1g1_yeast shares more local similarities  with the query protein than gsta_plepl does.
if mca3_human, the one that shares  <dig> % sequence identity with the query protein, is taken out from the template pool, knowpredsite can still predict correctly for protein mca3_mouse.
for the multi-localized proteins, there are  <dig> proteins unable to find similar sequences by the blast-hit method.
however, the localization sites of around half of them can be correctly predicted by knowpredsite.
we randomly choose an example, cfdp2_bovin, to demonstrate the knowpredsite's capability of identifying related sequences from the template pool.
the two highest confidence scores of cfdp2_bovin are  <dig>   and  <dig>  .
among the top  <dig> templates ,  <dig> of them are localized into cyt and nuc,  <dig> are localized into cyt only, and  <dig> are localized into nuc only.
their sequence identities against cfdp2_bovin are very low, ranging from  <dig> % to  <dig> %.
the result suggests that local similarity captured by our method is beneficial for psl prediction when global sequence similarity is very low.
CONCLUSIONS
in this paper, we propose a highly accurate subcellular localization prediction method for single- and multi-localized proteins, called knowpredsite, which is based on a knowledge base instead of frequently used machine learning approaches.
the knowledge base, called spkb, is constructed from a given dataset of proteins with known localization site annotation to capture local similarity between proteins so that related proteins with the same localization can be identified.
using these related proteins obtained form the knowledge base, the localization site of a query protein can be better predicted.
we used the ngloc dataset to evaluate the performance of knowpredsite.
the dataset consists of  <dig> single-localized proteins and  <dig> multi-localized proteins of ten subcellular proteomes from  <dig> species.
in order to compare knowpredsite with ngloc and the baseline blast-hit method, we performed ten-fold cross validation on the dataset.
the experiment results show that knowpredsite achieves higher prediction accuracy than ngloc and blast-hit.
particularly, on multi-localized sequences knowpredsite outperformed ngloc by  <dig> % in accuracy when a protein is correctly predicted if at least one site is correctly identified and by  <dig> % in accuracy when a protein is correctly predicted if both sites are correctly identified.
a major advantage of knowledge base approaches is that the prediction process is transparent and interpretable.
we can examine the prediction process to see how knowpredsite generates the prediction.
furthermore, with close observation from the prediction results in our experiments as described in the discussion section, we find that knowpredsite can efficiently use local similarity to identify related sequences even when their sequence identity is low so as to predict localization site with high accuracy.
when more proteins have known localization sites, most machine learning based methods need to retrain the prediction models, in contrast, knowpredsite can be easily improved by incrementally expanding the knowledge base, i.e., adding new peptide records or updating existing records with new protein sources and their localization site information.
this feature indicates the expansibility and efficiency in maintaining the knowpredsite prediction system.
competing interests
the authors declare that they have no competing interests.
authors' contributions
hsin-nan lin developed the method, carried out the computational predictions.
ching-tai chen and hsin-nan lin were involved in the literature survey, result interpretation, statistical analysis, and manuscript writing.
ting-yi sung, shinn-ying ho and wen-lian hsu coordinated the study and revised the manuscript.
all authors read and approved the final manuscript.
note
other papers from the meeting have been published as part of bmc genomics volume  <dig> supplement  <dig>  2009: eighth international conference on bioinformatics : computational biology, available online at http://www.biomedcentral.com/1471-2164/10?issue=s <dig>
supplementary material
additional file 1
ngloc dataset.
the file contains whole ngloc dataset, in which the row starts with '>' represents the protein name, the next row represents localization site.
the localization site is numbered from  <dig> to  <dig>  denoting cytoplasm , cytoskeleton , endoplasmic reticulum , extracellular , golgi apparatus , lysosome , mitochondria , nuclear , plasma membrane , and perixosome .
the ngloc dataset can be also downloaded via http://bio-cluster.iis.sinica.edu.tw/kbloc/dataset.htm.
click here for file
additional file 2
knowpredsite prediction results for single-localized proteins using leave-one-out cross validation.
each row is a prediction result for a protein sequence.
columns a, and b represent protein name and localization site annotation, respectively.
columns c to l are the confidence scores corresponding to each localization site.
columns n to q are the top  <dig> to top  <dig> accuracies.
click here for file
additional file 3
knowpredsite prediction results for single-localized proteins using ten-fold cross validation.
the columns' definition is the same as that for additional file  <dig>
click here for file
additional file 4
knowpredsite prediction results for multi-localized proteins using leave-one-out cross validation.
each row is a prediction result for a protein sequence.
columns a to l are the same to additional file  <dig>  columns n to q are the top  <dig> to top  <dig> accuracies based on the "at least one correct" criterion.
columns s to u are top  <dig> to top  <dig> accuracies based on the "both correct" criterion.
click here for file
additional file 5
knowpredsite prediction results for multi-localized proteins using ten-fold cross validation.
the columns' definition is the same as that for additional file  <dig>
click here for file
acknowledgements
thanks to all who developed psi-blast and made it publicly available.
we also appreciate chia-yu su for helpful discussions.
this article has been published as part of bmc bioinformatics volume  <dig> supplement  <dig>  2009: eighth international conference on bioinformatics : bioinformatics.
the full contents of the supplement are available online at http://www.biomedcentral.com/1471-2105/10?issue=s <dig>

 protein subcellular localization is important to elucidate protein functions as proteins cooperate towards a common function in the same subcellular compartment. it is also essential to annotate genomes, to design proteomics experiments, and to identify potential diagnostic, drug and vaccine targets. determining the localization sites of a protein through experiments can be time-consuming and labor-intensive. with the large number of sequences that continue to emerge from the genome sequencing projects, computational methods for protein subcellular localization at a proteome scale become increasingly important. most existing psl predictors are based on machine learning algorithms. they can be categorized by the feature sets used for building prediction models. a group of methods use features derived from primary sequence; some utilize various biological features extracted from literature or public databases. other features are also used in different methods, e.g., phylogenetic profiling, domain projection, sequence homology, and compartment-specific features. a simple and reliable way to predict localization site is to inherit subcellular localization from homologous proteins. therefore, in a hybrid method was proposed, which combined an svm based method with a sequence comparison tool to find homology to improve the performance. however, some homologous proteins are not similar in sequences, but in structures. for example, the sequence identity between proteins 1aab and 1j is only % but they are structurally homologous and classified into the same family in the scop classification. for such cases, it is difficult to discover the homologous relationship using sequence comparison methods. profile-profile alignment methods are capable of identifying remote homology; nevertheless, they are relatively slow. most of the psl prediction systems are established particularly for single-localized proteins. a significant number of eukaryotic proteins are, however, known to be localized into multiple subcellular organelles. in fact, proteins may simultaneously locate or move between different cellular compartments and be involved in different biological processes with different roles. this type of proteins may take a high proportion, even more than 35%. in addition, the majority of existing computational methods have the following disadvantages: 1) they only predict a limited number of locations; 2) they are limited to subsets of proteomes which contain signal peptide sequences or with prior structural/functional information; 3) the datasets used for training are for specific species, which is not sufficiently robust to represent the entire proteomes. thus, most of the computational methods are not sufficient for proteome-wide prediction of psl across various species. thus in this study, we propose a knowledge based approach, called knowpredsite, using local sequence similarity to find useful proteins as templates for site prediction of the query protein. it is designed to predict localization site of single- and multi-localized proteins and is applicable to proteome-wide prediction. furthermore, it only requires protein sequence information and no functional or structural information is required. notably, prediction results can be explained by the template proteins which are used to vote for the localization sites. the knowledge-based prediction scheme has been shown to be effective in predicting protein secondary structure and local structure. to evaluate our knowledge-based site prediction method, we used the ngloc dataset to perform ten-fold cross validation to compare with existing methods. the dataset consists of ten subcellular proteomes from species with single- and multi-localized proteins. knowpredsite achieved % accuracy for single-localized proteins and % accuracy with both sites correctly predicted for multiple localized proteins. methods the main idea behind knowpredsite knowpredsite predicts psl based on a knowledge base, which is constructed to capture local sequence similarity of two proteins even when they have sequence identity less than 25%. however, such local similarity is difficult to be detected using the traditional alignment algorithm due to the low sequence similarity. therefore we adopt the transitivity relationship, which was firstly used in for clustering protein sequences, to capture local similarity between protein sequences. transitivity refers to deducing a possible similarity between protein a and protein c from the existence of a third protein b, such that a and b as well as b and c are homologues if the sequence identity between a and b as well as that between b and c is above the predefined threshold. figure shows an example of transitivity relationship among protein a, protein b, and protein c. protein a and protein b share sequence identity of 34%, and protein b and protein c share sequence identity of 27%, whereas protein a and protein c only share sequence identity of 12%. using the transitivity relationship, remote homologous relationship and local similarity between protein a and protein c can be detected. in this paper, we apply the transitivity concept to peptide fragments instead of the protein sequences to obtain local similarities between remotely homologues. protein a and protein c share local similarity if there is a peptide fragment similar to subsequences in protein a and protein c. figure illustrates the idea, in which protein a and c are aligned with protein b and protein b. if there is a peptide fragment shared by both b and b the corresponding peptide fragments in protein a and protein c are inferred as locally similar between protein a and protein c. the shared peptide may represent a possible sequence variation in evolution. moreover, if protein a and protein c are remotely homologous, there is likely more "shared" sequence fragments in different protein b's to characterize their similarity. however, not all such proteins a and c which share local similarity are homologous. some local similarities may arise without common ancestry. short sequences may be similar by chance, and sequences may be similar because both are selected to bind to a particular protein. in order to avoid ambiguity, we define such proteins a and c which share local similarity as "related sequences". construction of the knowledge base spkb given a dataset of proteins with known localization sites, we construct a knowledge base, called similar-peptide knowledge base. the dataset used to construct spkb will be described in the result section. to construct the knowledge base, we first use the native sequence of each protein in the dataset to extract the fixed-length peptide fragments by using a sliding window of length w. each peptide sequence as well as its protein source and the localization site information are stored in spkb. since the performance of knowledge-based methods relies on the size of the knowledge base, we then perform psi-blast search with parameters j = e = on each protein in the dataset against the ncbinr database to find similar sequences. since the ncbinr database contains only the protein sequence information, the localization annotation of peptides generated by similar sequences is determined as follows. specifically, given a query protein sequence q, psi-blast would generate a large number of significant local pairwise alignments called high-scoring segment pairs between q and its similar proteins. an example of an hsp is shown in figure statistically significant blast hits usually signify sequence homology. we assumed that in an hsp, the similar peptide sequences in the counterpart sequence represent the possible sequence variations to the corresponding peptide in the query, i.e., the protein q. we use the same sliding window of length w to generate all peptide fragments in each hsp. two amino acids aligned together in an hsp are said to be interchangeable if they have a positive score in the blosum. the number of amino acid pairs being interchangeable within a sliding window represents the similarity level of the two peptide fragments. a peptide in sbjct is called a similar peptide if it has at least k residues interchangeable to those of the corresponding peptide in query. a similar peptide is used to signify local sequence similarity between sbjct and query and thus is assigned the localization annotation of the protein q. performing psi-blast search for all proteins in the dataset, we can generate a huge number, possibly multi-millions, of similar peptides with localization annotation. each record in the knowledge base is indexed by a similar peptide, and stores its similar peptide sequences and protein sources, similarity level and localization site information. note that a similar peptide may occur multiple times in different hsps of a single psi-blast search result, i.e., derived from different similar proteins found in the psi-blast search. we cluster them together and store the frequency in the peptide record. table shows a record of the similar peptide myskill, which is generated by performing psi-blast search on the three proteins with known localization sites, respectively. the frequencies of myskill in the psi-blast search results of proteins a, b, and c are and respectively. the localization site information is inherited from the three protein sources. three protein sources with known localization sites contain peptides that are aligned and similar to the peptide myskill in their hsps. the similarity level indicates the number of amino acid pairs that are interchangeable between the native peptide sequence and the similar peptide sequence. the frequency represents the number of occurrences they are aligned in hsps. knowpredsite: a localization prediction method using spkb the main idea of knowpredsite is illustrated in figure given a target protein t, whose localization annotation is unknown and to be predicted, we perform psi-blast search and use the same procedure as described in the last subsection for knowledge base construction to generate all similar peptides of t and their frequencies from its native sequence and hsps. each similar peptide hp is then matched against spkb, and the peptide record with index hp is called a hit. for each hit, we calculate two types of scores associated with each localization site i: the voting score si and the confidence score cs. the calculation of the voting score si is as follows: let f denote the frequency of hp found in all t's hsps. for each record in spkb, we calculate the score wi associated with each localization site by summing up the frequencies of the similar peptides that contain the specific site. for example, for the peptide record myskill shown in table the score of cytoplasm is, and those of nuclear and extracellular are and respectively. then the voting score si is defined as f multiplied by. for example, if myskill is a similar peptide of t and its frequency is in t's hsps, then the voting scores of cytoplasm, nuclear, and extracellular are,, and, respectively, while those of other localization sites are all the localization site prediction of the protein t is determined by the confidence score cs, which is the total voting score aggregated from all hit records. finally, each cs is divided by the summation of all frequencies f of all t's hits and then multiplied by to normalize the confidence score in the range of and knowpredsite predicts t being localized into the site with the highest confidence score for single-localized proteins or into the sites with the two highest confidence scores for multi-localized proteins. to differentiate single-localized proteins from those that are multi-localized, we followed king and guda's method to calculate the multi-localized confidence score associated with a protein t, which gives a relative measure of the likelihood that the protein t is multi-localized. it is derived from the two highest confidence scores and is defined as follows: and mlcs is bounded by i.e., when the calculated mlcs is over it is assigned blast-hit prediction method since blast is the most popular method for sequence comparison, we implemented a simple prediction method based on the blast search result. given a dataset of proteins with known localization site, to predict the localization site of a test protein t we first perform the blast search against the dataset and then assign the localization annotations of the best blast hit to the protein t. if there is no hit at the e-value cutoff, no annotation will be assigned to the protein t. as reported by jones and swindells, the e-value of generally produces a safe searching. the performance of blast-based prediction method is usually treated as the baseline to compare with those of other methods. evaluation measure the performance is estimated using the following measurements. to assess the performance in each localization site, precision, accuracy and matthew's correlation coefficient are calculated by equations to, respectively. the overall accuracy is defined in equation. where tpi, tni, fpi, fni, and ni are, respectively, the number of true positives, true negatives, false positives, false negatives, and proteins in localization site i. mcc, which considers both under- and over-predictions, provides a complementary measure of the predictive performance, where mcc = indicates a perfect prediction, mcc = indicates a completely random assignment, and mcc = - indicates a perfectly reverse correlation.  knowpredsite was implemented as a parallel program under the linux environment. it was implemented using c++ and mpich library. we used the ngloc dataset to construct the knowledge base and test the performance of knowpredsite. the dataset is compiled from different species and contains protein sequences, including single localized proteins and multi-localized proteins. there are ten different subcellular locations among these proteins, which are cytoplasm, cytoskeleton, endoplasmic reticulum, extracellular, golgi apparatus, lysosome, mitochondria, nuclear, plasma membrane, and perixosome. we conducted two types of experiment on the dataset. first, in order to take advantages of local similarities from as many proteins as possible, we conducted the leave-one-out cross validation experiment to determine the parameters and to evaluate the performance of knowpredsite. in this experiment, each protein was in turn used as the test protein and the remaining proteins were used to construct the knowledge base. second, we compared the performance of knowpredsite with existing methods. since the dataset is from ngloc and ngloc has been shown to be better than psort, ptarget and ploc using the same dataset, we directly compare knowpredsite against ngloc using ten-fold cross validation. in this experiment, all proteins were partitioned into subsets, and each subset was in turn used as the test set and the remaining nine subsets were used to construct the knowledge base. determining window size w and similarity threshold k for knowpredsite knowpredsite aims to utilize the localization annotations of similar peptides. the determination of similar relations, which depends on the window size w and the threshold of similarity level k, can affect the performance of knowpredsite. using a smaller w, similar peptides have a higher probability to be hit against the knowledge base; however, shorter peptide sequences are likely to appear in many unrelated proteins. given a fixed w, there is also a trade-off in choosing the threshold of similarity level k. a smaller k produces looser similarity relations, which leads to extracting more, but less reliable, similar peptides. to make an appropriate selection of w and k, we conducted a leave-one-out cross validation experiments on only the single-localized proteins in the ngloc dataset for w ranging from to and k ranging from to w. overall accuracy overall accuracy the combination of w = and k = provides the best accuracy. some results are shown to have identical overall accuracies due to the rounding off to the first decimal place. prediction performance of knowpredsite after the best parameters have been determined, we conducted a ten-fold cross validation experiment on the entire dataset to compare knowpredsite with ngloc and blast-hit prediction. we used the top n accuracy for evaluation, where n ranges from to a protein is considered to be correctly predicted when the real localization site rank among the top n of the predicted sites..) notably, for multi-localized proteins, the accuracy is measured in two ways: first, at least one site correctly predicted and second, both sites correctly predicted. using the first measurement, a true positive is a multi-localized protein with at least one localization site correctly predicted; whereas a true positive using the second measurement is a multi-localized protein with both sites correctly predicted. the prediction performance of knowpredsite, ngloc, and blast-hit is summarized in table in which knowpredsite performance is reported with ten-fold cross validation and leave-one-out cross validation as denoted by #knowpredsite and *knowpredsite, respectively. it is observed that knowpredsite outperforms ngloc and blast-hit. multi-localized multi-localized *knowpredsite represents the experiment result using leave-one-out cross validation; #knowpredsite represents the experiment result using 10-fold cross validation. for single-localized proteins, the overall accuracies of knowpredsite are from to when the correct prediction is considered within the top to top most probable sites. those of ngloc are from % to %. the accuracy of blast-hit is %, which means % of single-localized proteins could be correctly predicted by blast searches. it is noteworthy that sequences among all single-localized proteins failed to find significant similar proteins by blast-hit method; however, % of them were correctly predicted by knowpredsite. it shows that the local similarity helps identify related sequences for subcellular localization prediction. the experiment result shows that knowpredsite has much higher accuracy on multi-localized proteins than the other methods. using the first accuracy measurement, i.e., at least one site correctly predicted, knowpredsite achieves more than 90% of the top accuracy, which is higher than ngloc by %. using the tighter second accuracy measurement, knowpredsite achieves % of the top accuracy, which is higher than ngloc by %. further observing the top n accuracy, we find that knowpredsite is more able to narrow down the number of false positives than ngloc. the top and top accuracies of the blast-hit method are % and % for the two accuracy measurements. notably, proteins among all multi-localized proteins failed to find any significant blast hit; however, % and % of them were correctly predicted by knowpredsite using the two accuracy measurements, respectively. site-specific prediction performance in contrast to the overall accuracy of the dataset reported in table we further analyze the prediction performance on each of the distinct localization sites. the results are summarized in table among the localization sites, the precision ranges from % to % and the accuracyi ranges from % to %. it is observed that higher occurrence of the localization site, e.g., exc and pla, leads to better prediction, e.g., the precision and accuracy on exc are % and %, respectively. low occurrence of the localization site can deteriorate prediction, for example, csk and gol have mcci of and, respectively. however, if the similar peptide records of a site have higher specificity, prediction performance can be good despite low occurrence. for example, the precision and accuracy on lys and pox are % and %, and % and %, respectively. furthermore, it is noteworthy that although cyt represents % of the dataset, its mcci is, much lower than other highly occurring sites. its low mcci is due to low precision since knowpredsite yields more false positives for cyt. high false positives usually occur when the similar peptide records of a site have lower specificity and higher diversity. as a result, proteins of other localization sites are misclassified as cyt. mcc i evaluation of the multi-localized confidence score a significant number of eukaryotic proteins are known to be localized into multiple subcellular organelles; therefore, it is important to differentiate single-localized proteins from multi-localized proteins. we used the entire ngloc dataset to compare different mlcs thresholds on the correct distinction between single-localized and multi-localized proteins. specifically, we used the portions of true positives in the multi-localized proteins and true negatives in the single-localized proteins as the performance measures. a true positive represents a multi-localized protein whose mlcs is above the threshold and a true negative represents a single-localized protein whose mlcs is below the threshold. we illustrate the cumulative percentages of true positive and true negative versus the mlcs threshold in figure which shows that the true negative curve is increasing along the mlcs axis whereas the true positive curve is decreasing. if the mlcs threshold is set to be % of multi-localized proteins are true positives and % of single-localized proteins are true negatives. it shows that % of multi-localized proteins obtained mlcs of or better, whereas only % of single-localized proteins within this range. if the mlcs threshold is set to be % of multi-localized proteins are true positives and % of single-localized proteins are true negatives. in ngloc, the best result shows that 76% of multi-localized proteins belong to true positives and 81% of single-localized proteins belong to true negatives when of mlcs threshold is applied. the result shows that knowpredsite better differentiate multi-localized proteins from those that are single-localized. discussion unlike most machine learning methods that the parameters of the prediction models are not biologically interpretable, the prediction result of knowpredsite is interpretable and the prediction process is transparent and traceable. to predict the localization sites of a protein, knowpredsite shows the template sequences and their associated contributive confidence scores for a query protein. such information is useful for interpretation of the prediction results. in this section, we select the four sequences ef1a2_rabit, rash_human, mca3_mouse, and cfdp2_bovin from the ngloc dataset, to demonstrate the interpretation of knowpredsite prediction results. the prediction result of each of the first three proteins and its template sequences extracted from the knowledge base used for prediction are shown in table respectively. in each table, the prediction result shows the mlcs and the confidence score of each localization site that the query protein would be localized into. moreover, the template proteins which are used to vote for the localization sites are shown in each table. we only list the top eight template proteins which contribute most to the confidence scores of the query sequence. for each template sequence, its contribution to confidence score of each localization site and the sequence identity to the query protein calculated by clustalw are shown. *: correct answer; si: sequence identity. *: correct answer; si: sequence identity. *: correct answer; si: sequence identity. in the example of ef1a2_rabit shown in table knowpredsite predicts it being single-localized at cytoplasm since mlcs is very low and cyt has the highest confidence score. however, the localization site of ef1a2_rabit reported in the ngloc dataset is nuclear. examining the eight template proteins, we find that they all have high sequence identities with ef1a2_rabit and most of them are localized into cyt except ef1a2_rat localized into nuc. according to the gene ontology annotation, it is localized into cyt and nuc, which are the two sites with the highest confidence scores in knowpredsite's prediction. in the example of rash_human shown in table knowpredsite predicts rash_human being localized into plasma membrane and cytoplasm. however, the correct localization site is cytoplasm and golgi apparatus. referring to the prediction result, the confidence score of pla is much higher than those of cyt and gol. it is also observed that most of the template proteins are localized into pla. according to the annotation in gene ontology and swissprot, rash_human is localized into pla and gol, and the template protein, rasn_human, is also localized into pla and gol. if applying the new annotation data, knowpredsite can predict rash_human correctly. as for mca3_mouse shown in table knowpredsite predicts its mlcs and it being localized into cytoplasm and nuclear correctly. examining the template proteins, we observe that knowpredsite identifies some related proteins, i.e., which have the same localization with the query protein. ef1g1_yeast and nu155_rat, even though they share very low sequence identity % and %, respectively, with the query protein. notably, the two template proteins rank second and seventh, respectively, among all template proteins. furthermore, though gsta_plepl has higher sequence identity with the query protein than ef1g1_yeast, the confidence score contributed by ef1g1_yeast is much higher than that by gsta_plepl. it shows that the contributive confidence score is not necessary to be positively correlated with the sequence identity when template sequences are dissimilar with the query sequence. in this example, ef1g1_yeast shares more local similarities with the query protein than gsta_plepl does. if mca3_human, the one that shares % sequence identity with the query protein, is taken out from the template pool, knowpredsite can still predict correctly for protein mca3_mouse. for the multi-localized proteins, there are proteins unable to find similar sequences by the blast-hit method. however, the localization sites of around half of them can be correctly predicted by knowpredsite. we randomly choose an example, cfdp2_bovin, to demonstrate the knowpredsite's capability of identifying related sequences from the template pool. the two highest confidence scores of cfdp2_bovin are and. among the top templates, of them are localized into cyt and nuc, are localized into cyt only, and are localized into nuc only. their sequence identities against cfdp2_bovin are very low, ranging from % to %. the result suggests that local similarity captured by our method is beneficial for psl prediction when global sequence similarity is very low.  in this paper, we propose a highly accurate subcellular localization prediction method for single- and multi-localized proteins, called knowpredsite, which is based on a knowledge base instead of frequently used machine learning approaches. the knowledge base, called spkb, is constructed from a given dataset of proteins with known localization site annotation to capture local similarity between proteins so that related proteins with the same localization can be identified. using these related proteins obtained form the knowledge base, the localization site of a query protein can be better predicted. we used the ngloc dataset to evaluate the performance of knowpredsite. the dataset consists of single-localized proteins and multi-localized proteins of ten subcellular proteomes from species. in order to compare knowpredsite with ngloc and the baseline blast-hit method, we performed ten-fold cross validation on the dataset. the experiment results show that knowpredsite achieves higher prediction accuracy than ngloc and blast-hit. particularly, on multi-localized sequences knowpredsite outperformed ngloc by % in accuracy when a protein is correctly predicted if at least one site is correctly identified and by % in accuracy when a protein is correctly predicted if both sites are correctly identified. a major advantage of knowledge base approaches is that the prediction process is transparent and interpretable. we can examine the prediction process to see how knowpredsite generates the prediction. furthermore, with close observation from the prediction results in our experiments as described in the discussion section, we find that knowpredsite can efficiently use local similarity to identify related sequences even when their sequence identity is low so as to predict localization site with high accuracy. when more proteins have known localization sites, most machine learning based methods need to retrain the prediction models, in contrast, knowpredsite can be easily improved by incrementally expanding the knowledge base, i.e., adding new peptide records or updating existing records with new protein sources and their localization site information. this feature indicates the expansibility and efficiency in maintaining the knowpredsite prediction system. competing interests the authors declare that they have no competing interests. authors' contributions hsin-nan lin developed the method, carried out the computational predictions. ching-tai chen and hsin-nan lin were involved in the literature survey, result interpretation, statistical analysis, and manuscript writing. ting-yi sung, shinn-ying ho and wen-lian hsu coordinated the study and revised the manuscript. all authors read and approved the final manuscript. note other papers from the meeting have been published as part of bmc genomics volume supplement 2009: eighth international conference on bioinformatics: computational biology, available online at http://www.biomedcentral.com/1471-2164/10?issue=s supplementary material additional file 1 ngloc dataset. the file contains whole ngloc dataset, in which the row starts with'>' represents the protein name, the next row represents localization site. the localization site is numbered from to denoting cytoplasm, cytoskeleton, endoplasmic reticulum, extracellular, golgi apparatus, lysosome, mitochondria, nuclear, plasma membrane, and perixosome. the ngloc dataset can be also downloaded via http://bio-cluster.iis.sinica.edu.tw/kbloc/dataset.htm. click here for file additional file 2 knowpredsite prediction results for single-localized proteins using leave-one-out cross validation. each row is a prediction result for a protein sequence. columns a, and b represent protein name and localization site annotation, respectively. columns c to l are the confidence scores corresponding to each localization site. columns n to q are the top to top accuracies. click here for file additional file 3 knowpredsite prediction results for single-localized proteins using ten-fold cross validation. the columns' definition is the same as that for additional file click here for file additional file 4 knowpredsite prediction results for multi-localized proteins using leave-one-out cross validation. each row is a prediction result for a protein sequence. columns a to l are the same to additional file columns n to q are the top to top accuracies based on the "at least one correct" criterion. columns s to u are top to top accuracies based on the "both correct" criterion. click here for file additional file 5 knowpredsite prediction results for multi-localized proteins using ten-fold cross validation. the columns' definition is the same as that for additional file click here for file acknowledgements thanks to all who developed psi-blast and made it publicly available. we also appreciate chia-yu su for helpful discussions. this article has been published as part of bmc bioinformatics volume supplement 2009: eighth international conference on bioinformatics: bioinformatics. the full contents of the supplement are available online at http://www.biomedcentral.com/1471-2105/10?issue=s 
the experiment results show that knowpredsite achieves higher prediction accuracy than ngloc and blast-hit method. the experiment results show that even though the sequence similarity is low, the local similarity is effective for prediction. experiment results show that knowpredsite is a highly accurate prediction method for both single- and multi-localized proteins. it is worth-mentioning the prediction process of knowpredsite is transparent and biologically interpretable and it shows a set of template sequences to generate the prediction result. many studies have shown that proteins may simultaneously locate or move between different cellular compartments and be involved in different biological processes with different roles. the study of protein subcellular localization is important for elucidating protein functions involved in various cellular processes. when predicting the localization annotation of a query protein, we search against the knowledge base and used a scoring mechanism to determine the predicted sites. we construct a knowledge base to record the possible sequence variations for protein sequences. in this study, we propose a knowledge based method, called knowpredsite, to predict the localization site of both single-localized and multi-localized proteins. knowpredsite demonstrates the power of identifying related sequences in the knowledge base. however, a significant number of eukaryotic proteins are known to be localized into multiple subcellular organelles. for single-localized proteins, the overall accuracy of knowpredsite is %. for multi-localized proteins, the overall accuracy of knowpredsite is %, which is significantly higher than that of ngloc by %. however, determining the localization sites of a protein through wet-lab experiments can be time-consuming and labor-intensive. most of the psl prediction systems are established for single-localized proteins. based on the local similarity, we can identify the "related sequences" for prediction. 7– september asia pacific bioinformatics network eighth international conference on bioinformatics singapore
 the study of protein subcellular localization is important for elucidating protein functions involved in various cellular processes. however, determining the localization sites of a protein through wet-lab experiments can be time-consuming and labor-intensive. thus, computational approaches become highly desirable. most of the psl prediction systems are established for single-localized proteins. however, a significant number of eukaryotic proteins are known to be localized into multiple subcellular organelles. many studies have shown that proteins may simultaneously locate or move between different cellular compartments and be involved in different biological processes with different roles.  in this study, we propose a knowledge based method, called knowpredsite, to predict the localization site of both single-localized and multi-localized proteins. based on the local similarity, we can identify the "related sequences" for prediction. we construct a knowledge base to record the possible sequence variations for protein sequences. when predicting the localization annotation of a query protein, we search against the knowledge base and used a scoring mechanism to determine the predicted sites. we downloaded the dataset from ngloc, which consisted of ten distinct subcellular organelles from species, and performed ten-fold cross validation experiments to evaluate knowpredsite's performance. the experiment results show that knowpredsite achieves higher prediction accuracy than ngloc and blast-hit method. for single-localized proteins, the overall accuracy of knowpredsite is %. for multi-localized proteins, the overall accuracy of knowpredsite is %, which is significantly higher than that of ngloc by %. notably, half of the proteins in the dataset that cannot find any blast hit sequence above a specified threshold can still be correctly predicted by knowpredsite.  knowpredsite demonstrates the power of identifying related sequences in the knowledge base. the experiment results show that even though the sequence similarity is low, the local similarity is effective for prediction. experiment results show that knowpredsite is a highly accurate prediction method for both single- and multi-localized proteins. it is worth-mentioning the prediction process of knowpredsite is transparent and biologically interpretable and it shows a set of template sequences to generate the prediction result. the knowpredsite prediction server is available at http://bio-cluster.iis.sinica.edu.tw/kbloc/. 7– september asia pacific bioinformatics network eighth international conference on bioinformatics singapore 