BACKGROUND
eukaryotic cells are defined by the presence of their nucleus.
the nuclear membrane enclosing the genetic material of the cell is selective in its import of material through its nuclear pores and this translocation is mediated by cellular mechanisms  <cit> .
proteins entering the nucleus must do so through proteins forming the nuclear pores: the nuclear pore complex  <cit> .
the pores allow the passive diffusion of small proteins, but bigger proteins entering the nucleus are usually bound by karyopherin complexes on their nuclear localization signal  <cit> .
although there are many nuclear import pathways in eukaryotic cells, most of these have not been characterized in detail.
the best understood is the classical nls pathway.
the recognition of classical nlss on nuclear proteins is done by the importin-α subunit which in turn is recognized by the importin-β subunit.
this trimer  is then imported to the nucleus after series of enzymatic steps  <cit> .
other families of nlss are independent of importin-α, and may bind directly to one of the members of the importin-β superfamily  <cit> .
classical nlss show characteristic patterns of basic residues loosely matching two consensus sequences, kx and krx10–12krxk, termed the 'monopartite' and 'bipartite' classical nls  <cit> .
psort  <cit>  accurately predicts protein localization by including heuristic scores based on residues frequencies, protein domains as well as motifs.
psort will then offer, based on the cnls consensus sequences, various possible nlss on nuclear proteins.
however, many known nlss do not match any of the consensus sequences described above.
therefore, other computational methods have been proposed to predict nlss based on amino acid sequences.
one method, predictnls  <cit> , employs a database of regular expressions to predict the various types of nlss.
here we sought to test the power of these methods to predict nlss in saccharomyces cerevisiae.
we compiled a list of experimentally verified nlss in yeast and found that predictnls  <cit>  predicts 10% of the nlss in this set.
based on an analysis of the residues frequencies in the nlss in this set, we developed a simple hidden markov model  <cit>  that can be used to predict the nuclear localization signal in proteins, achieving true positive rate of 37%.
we also explored using specific models for the monopartite and bipartite nlss, but surprisingly, found no significant improvement in positive predictive value.
finally, we also show that our method fares well in species other than yeast, consistent with the conservation of import mechanisms.
RESULTS
a set of experimentally verified nuclear localization signals in yeast
in order to test the predictive power of computational methods to predict nlss in s. cerevisiae, we sought to identify a set of experimentally confirmed nlss.
we searched the literature for papers in which specific stretches of amino acids have been shown to act as functional nlss in yeast.
while many approaches have been used to characterize and identify nuclear localization signals in proteins, we took as the nls the minimal sequence in the protein that was proven to be either necessary or sufficient for nuclear import.
to categorize nlss into their respective import pathways, we looked for evidence of their respective pathways which includes receptor binding or pathway dependency.
however, only half of our proteins had a clear reference to these, and many remain unknown.
in all, we found  <dig> nlss.
of these,  <dig> had evidence of importin-α dependence or binding and we here refer to these as cnlss.
in addition, we found  <dig> nlss which depend on other import pathways, which we term non-cnlss.
finally, for  <dig> of our sequences, we failed to find information about the mechanism of import.
the nlss and references are listed in tables  <dig> and  <dig>
characterized yeast nuclear localization signals used in our analysis for which import pathway is known.
a corresponds to classical nlss, b corresponds nlss known not to dependent on the classical nls import pathway.
see text for details of how nlss were classified.
numbers in the last two columns indicate references using pubmed ids .
characterized yeast nuclear localization signals used in our analysis, for which we could not find evidence for a specific import pathway.
numbers in the last column are pubmed ids for references.
see text for details of how nlss were classified.
current nls prediction methods show little predictive power on our yeast data
in order to test the power of nls prediction methods, we first used the consensus sequence-based approach predictnls  <cit>  and found that it was generally too specific: only 10%  of our characterized nlss were identified by their genome wide analysis of the yeast proteome .
these results were surprising, considering that this method had been reported to find 100% of the experimentally characterized nlss considered in the general study  <cit> .
we suggest that predictnls might be underestimating the true variability of nlss, as few yeast nlss  were included in that study.
predictnls also produced  <dig> predictions that were not characterized nlss, suggesting a positive predictive value of 50%.
probabilistic models have been widely used to predict domains in proteins .
profile hmms model a linear series of states which approximately corresponds to the pattern of residues in a consensus motif.
these models can account for length variation using insertion and deletion states.
nlss with different import mechanisms are unlikely to share a consensus motif.
therefore, we tried a profile hmm approach to predict only cnlss.
we manually aligned the labelled cnlss using a proposed biological model of binding specificity of importin-α  <cit>   and built an hmm model using hmmbuild  <cit>  .
we used this model to predict cnlss using hmmsearch, and assessed the predictive power at different e-value thresholds using a leave-one-out cross-validation .
the results are displayed as roc curves in figure 1b  and indicate that hmmer obtains a similar positive predictive value  as predictnls at varying true positive rate .
taken together, our results indicate that both frameworks show some positive predictive value but predictnls shows a low true positive rate, and both methods show ppv of around 50% in our data.
the nuclear localization signal shows a strong statistical difference in residue frequencies
while the nlss can be divided in many functional categories depending on their pathways, we observed that most nlss had an enrichment of basic residues.
we first analyzed the residue content of the characterized cnlss.
consistent with the definition of classical nlss, we observe significant frequency differences  mainly in lysine  and arginine .
to determine whether there were differences between the different types of nlss, we then compared the set of cnls to all other nls  and surprisingly found no significant differences in their residue frequencies.
thinking that maybe the unknown set of nlss might have been mostly composed of cnlss, we also compared the cnls residue frequencies to the non-cnls residue frequencies and also found no significant differences in residue frequencies.
thus, in our data set the three categories of nlss  show no difference in residue frequencies.
because the most apparent statistical difference lies in the frequencies of lysine  and arginine , we plotted each nls in respect to number of k and r residues and their length , and consistent with the previous residue frequencies test, we found that there were generally no discernable differences between the three categories of nlss.
interestingly, we also observe two groups of nlss on this plot, the first showing an average length of  <dig> amino acids containing an average of  <dig>  basic residues while the other showing an average length of  <dig> amino acids containing an average of  <dig>  basic residues.
we suggest that these regions correspond to monopartite and bipartite nlss  <cit> .
we note that even nlss known not to be importin-α dependent showed this pattern.
a simple hidden markov model shows better predictive performance
motivated by the idea that all nlss in our set shared a similar bias in lysines and arginines, we created a simple two-state hmm.
in this model, sequence is generated either from a background model  or an nls model, whose residue frequencies are equal to those in all of the characterized yeast nlss .
to assess the positive predictive value of the model, we performed a leave-one-out cross validation, as above , of the hmm.
we assessed its predictive strength in two ways, either using the most probable path  or by computing the posterior probability and counting predictions when it passed a certain threshold .
relative to predictnls, the results show significantly improved positive predictive value , and higher true positive rate  while producing only  <dig> false positives.
our results were specific to the experimentally defined nlss.
we defined a residue-level correlation coefficient  and found that our model yielded a coefficient of  <dig> .
we also computed the matthews correlation coefficient  <cit>  and found that it was  <dig> , similar to recent results for a predictor of nuclear export signals  <cit> .
we were surprised to observe that a single, simple model could achieve increased performance even though our training data spanned a large diversity of nlss, e.g., some cnlss and others not, both bipartite and monopartite.
nevertheless, we found that our method showed similar positive predictive value on each set of nlss when we analyzed them individually .
while perhaps surprising, these results are consistent with the similar residue compositions of each sets of nlss .
a more complex model does not improve prediction
we observed two main regions within our k-r content plot where nlss seemed to aggregate and this is consistent for the bipartite and monopartite classes of cnlss, but we were surprised to see that this was also observed in the other sets.
to test whether or not we could improve our predictions using this information, we created a four state hmm by modelling a 'spacer' state between two patches of basic residues  and analyzed its predictive power using a leave-one-out cross-validation.
this model is able to recognize the two basic stretches of the nls separated by a spacer region, which we model using the background residue frequencies.
we refer to this model as the 'bipartite model'.
in some cases, this model accurately identifies the boundaries of these regions .
for comparison, we also trained a model using only the shorter nlss, which we refer to as the 'monopartite model'.
we refer to the initial model that uses the frequency of all of the nlss as the 'combined model'.
to test these models, we defined bipartite and monopartite nlss based on the two classes we had observed in figure  <dig>  we tested the bipartite model on the bipartite nlss only.
surprisingly, the positive predictive value and true positive rate of the bipartite model was exactly the same as the combined model , as the combined model can also identify bipartite nlss .
similar predictive power was also observed when comparing the monopartite model to the combined model on only monopartite nlss.
however, a small increase in true positive rate was observed for the monopartite model  but this difference was not significant.
applying the model to other organisms
we were concerned that our predictor might have a bias for yeast proteins.
we therefore tested our method on the set of nlss used to train predictnls  <cit> .
this set of data contains nlss that have been shown to function in vertebrate cells.
we found that our method has a similar true positive rate in this data as it does in yeast, finding 37% of the characterized nlss at the same posterior threshold.
however we do note an increased false positive rate , and modest reductions in the nucleotide-level correlation coefficient to  <dig>   and the matthews correlation coefficient to  <dig>  .
seeking to understand the elevated rate of false predictions, we explored them further and found that  <dig> of the  <dig> vertebrate false positives occur on only three proteins.
when we searched the literature for more information on these proteins we found that one of our 'false' predictions had actually been identified as an nls  <cit> .
we identified on another protein two patches of amino-acid repeats, and finally on the last protein two nucleolar localization signals, which are long stretches of basic amino acid residues, and it is not yet clear if these signals should be considered as nlss  <cit> .
we noted in total three false predictions composed of amino-acid repeats, which were largely absent from our yeast training set.
such repeats are problematic because they violate an assumption of our simple hidden-markov model, namely, that adjacent residues are independent given the value of the hidden state.
taken together, this analysis of vertebrate nlss demonstrates that the true positive rate of our method is not confined to our training data set.
however, we did note an increase in false positives, which might be explained by additional undiscovered nlss in this data set, or repetitive sequences in vertebrate proteins.
discussion
analysis of residue frequency clearly shows that there is a bias in key residues in the nls, and while previous studies have shown that there exists some position requirement in these residues  <cit> , the nlss do not clearly align and therefore we believe that the signal simply do not obey a clear consensus sequence rule.
our results are consistent with the model that nlss may simply be regions of high positive charges with only minor spatial requirements  <cit> .
this idea is consistent with the model that the nls can be masked by phosphorylation  <cit> , by inhibiting the activity of the signal due to addition of negative charges.
there is abundant evidence that cnlss bind at specific positions on importin-α and this binding is mediated by two sites which bind monopartite or bipartite cnlss  <cit> , which suggests that the bipartite cnls is not simply a bigger monopartite cnls.
we were, however, unable to exploit this knowledge to create a stronger predictor.
while each basic patch in the bipartite cnls does not represent a monopartite cnls, the combination of both patches is sufficient for recognition by our predictor.
by examining some false negatives, we find at least two reasons why our method fails to predict them.
first, there are examples that do not seem to show an enrichment of basic residues.
second, other nlss are simply too small to be identified reliably, due to a lack of statistical signal.
we note that unlike psort which is based on the cnls consensus motifs, our method does not attempt to predict nlss belonging to a particular pathway.
we observed that all nlss show an excess of basic residues, and therefore we have developed a simple hmm that can identify stretches of basic residues in protein sequences.
it is somewhat surprising that this method performs reasonably well.
this suggests that the consensus patterns for different import pathways may be more similar than currently anticipated.
we believe that obtaining a higher positive predictive value is certainly possible by combining other biological knowledge; however, this is still under study.
for example, some of our false predictions might either be real nlss that have not yet been characterized, or simply part of other undiscovered protein domains.
CONCLUSIONS
in conclusion, we offer a simplified approach to predicting nuclear localization signals and show that this method can be applied to multiple species.
this agrees with the notion that important regulatory mechanisms are conserved, although it is possible that differences in positive predictive value can be attributed to the existence of multiple importin-α,β homologues in other species  <cit>  or differences in proteins lengths between species.

 eukaryotic cells are defined by the presence of their nucleus. the nuclear membrane enclosing the genetic material of the cell is selective in its import of material through its nuclear pores and this translocation is mediated by cellular mechanisms. proteins entering the nucleus must do so through proteins forming the nuclear pores: the nuclear pore complex. the pores allow the passive diffusion of small proteins, but bigger proteins entering the nucleus are usually bound by karyopherin complexes on their nuclear localization signal. although there are many nuclear import pathways in eukaryotic cells, most of these have not been characterized in detail. the best understood is the classical nls pathway. the recognition of classical nlss on nuclear proteins is done by the importin-α subunit which in turn is recognized by the importin-β subunit. this trimer is then imported to the nucleus after series of enzymatic steps. other families of nlss are independent of importin-α, and may bind directly to one of the members of the importin-β superfamily. classical nlss show characteristic patterns of basic residues loosely matching two consensus sequences, kx and krx10–12krxk, termed the'monopartite' and'bipartite' classical nls. psort accurately predicts protein localization by including heuristic scores based on residues frequencies, protein domains as well as motifs. psort will then offer, based on the cnls consensus sequences, various possible nlss on nuclear proteins. however, many known nlss do not match any of the consensus sequences described above. therefore, other computational methods have been proposed to predict nlss based on amino acid sequences. one method, predictnls, employs a database of regular expressions to predict the various types of nlss. here we sought to test the power of these methods to predict nlss in saccharomyces cerevisiae. we compiled a list of experimentally verified nlss in yeast and found that predictnls predicts 10% of the nlss in this set. based on an analysis of the residues frequencies in the nlss in this set, we developed a simple hidden markov model that can be used to predict the nuclear localization signal in proteins, achieving true positive rate of 37%. we also explored using specific models for the monopartite and bipartite nlss, but surprisingly, found no significant improvement in positive predictive value. finally, we also show that our method fares well in species other than yeast, consistent with the conservation of import mechanisms.  a set of experimentally verified nuclear localization signals in yeast in order to test the predictive power of computational methods to predict nlss in s. cerevisiae, we sought to identify a set of experimentally confirmed nlss. we searched the literature for papers in which specific stretches of amino acids have been shown to act as functional nlss in yeast. while many approaches have been used to characterize and identify nuclear localization signals in proteins, we took as the nls the minimal sequence in the protein that was proven to be either necessary or sufficient for nuclear import. to categorize nlss into their respective import pathways, we looked for evidence of their respective pathways which includes receptor binding or pathway dependency. however, only half of our proteins had a clear reference to these, and many remain unknown. in all, we found nlss. of these, had evidence of importin-α dependence or binding and we here refer to these as cnlss. in addition, we found nlss which depend on other import pathways, which we term non-cnlss. finally, for of our sequences, we failed to find information about the mechanism of import. the nlss and references are listed in tables and characterized yeast nuclear localization signals used in our analysis for which import pathway is known. a corresponds to classical nlss, b corresponds nlss known not to dependent on the classical nls import pathway. see text for details of how nlss were classified. numbers in the last two columns indicate references using pubmed ids. characterized yeast nuclear localization signals used in our analysis, for which we could not find evidence for a specific import pathway. numbers in the last column are pubmed ids for references. see text for details of how nlss were classified. current nls prediction methods show little predictive power on our yeast data in order to test the power of nls prediction methods, we first used the consensus sequence-based approach predictnls and found that it was generally too specific: only 10% of our characterized nlss were identified by their genome wide analysis of the yeast proteome. these results were surprising, considering that this method had been reported to find 100% of the experimentally characterized nlss considered in the general study. we suggest that predictnls might be underestimating the true variability of nlss, as few yeast nlss were included in that study. predictnls also produced predictions that were not characterized nlss, suggesting a positive predictive value of 50%. probabilistic models have been widely used to predict domains in proteins. profile hmms model a linear series of states which approximately corresponds to the pattern of residues in a consensus motif. these models can account for length variation using insertion and deletion states. nlss with different import mechanisms are unlikely to share a consensus motif. therefore, we tried a profile hmm approach to predict only cnlss. we manually aligned the labelled cnlss using a proposed biological model of binding specificity of importin-α and built an hmm model using hmmbuild. we used this model to predict cnlss using hmmsearch, and assessed the predictive power at different e-value thresholds using a leave-one-out cross-validation. the results are displayed as roc curves in figure 1b and indicate that hmmer obtains a similar positive predictive value as predictnls at varying true positive rate. taken together, our results indicate that both frameworks show some positive predictive value but predictnls shows a low true positive rate, and both methods show ppv of around 50% in our data. the nuclear localization signal shows a strong statistical difference in residue frequencies while the nlss can be divided in many functional categories depending on their pathways, we observed that most nlss had an enrichment of basic residues. we first analyzed the residue content of the characterized cnlss. consistent with the definition of classical nlss, we observe significant frequency differences mainly in lysine and arginine. to determine whether there were differences between the different types of nlss, we then compared the set of cnls to all other nls and surprisingly found no significant differences in their residue frequencies. thinking that maybe the unknown set of nlss might have been mostly composed of cnlss, we also compared the cnls residue frequencies to the non-cnls residue frequencies and also found no significant differences in residue frequencies. thus, in our data set the three categories of nlss show no difference in residue frequencies. because the most apparent statistical difference lies in the frequencies of lysine and arginine, we plotted each nls in respect to number of k and r residues and their length, and consistent with the previous residue frequencies test, we found that there were generally no discernable differences between the three categories of nlss. interestingly, we also observe two groups of nlss on this plot, the first showing an average length of amino acids containing an average of basic residues while the other showing an average length of amino acids containing an average of basic residues. we suggest that these regions correspond to monopartite and bipartite nlss. we note that even nlss known not to be importin-α dependent showed this pattern. a simple hidden markov model shows better predictive performance motivated by the idea that all nlss in our set shared a similar bias in lysines and arginines, we created a simple two-state hmm. in this model, sequence is generated either from a background model or an nls model, whose residue frequencies are equal to those in all of the characterized yeast nlss. to assess the positive predictive value of the model, we performed a leave-one-out cross validation, as above, of the hmm. we assessed its predictive strength in two ways, either using the most probable path or by computing the posterior probability and counting predictions when it passed a certain threshold. relative to predictnls, the results show significantly improved positive predictive value, and higher true positive rate while producing only false positives. our results were specific to the experimentally defined nlss. we defined a residue-level correlation coefficient and found that our model yielded a coefficient of. we also computed the matthews correlation coefficient and found that it was, similar to recent results for a predictor of nuclear export signals. we were surprised to observe that a single, simple model could achieve increased performance even though our training data spanned a large diversity of nlss, e.g., some cnlss and others not, both bipartite and monopartite. nevertheless, we found that our method showed similar positive predictive value on each set of nlss when we analyzed them individually. while perhaps surprising, these results are consistent with the similar residue compositions of each sets of nlss. a more complex model does not improve prediction we observed two main regions within our k-r content plot where nlss seemed to aggregate and this is consistent for the bipartite and monopartite classes of cnlss, but we were surprised to see that this was also observed in the other sets. to test whether or not we could improve our predictions using this information, we created a four state hmm by modelling a'spacer' state between two patches of basic residues and analyzed its predictive power using a leave-one-out cross-validation. this model is able to recognize the two basic stretches of the nls separated by a spacer region, which we model using the background residue frequencies. we refer to this model as the'bipartite model'. in some cases, this model accurately identifies the boundaries of these regions. for comparison, we also trained a model using only the shorter nlss, which we refer to as the'monopartite model'. we refer to the initial model that uses the frequency of all of the nlss as the'combined model'. to test these models, we defined bipartite and monopartite nlss based on the two classes we had observed in figure we tested the bipartite model on the bipartite nlss only. surprisingly, the positive predictive value and true positive rate of the bipartite model was exactly the same as the combined model, as the combined model can also identify bipartite nlss. similar predictive power was also observed when comparing the monopartite model to the combined model on only monopartite nlss. however, a small increase in true positive rate was observed for the monopartite model but this difference was not significant. applying the model to other organisms we were concerned that our predictor might have a bias for yeast proteins. we therefore tested our method on the set of nlss used to train predictnls. this set of data contains nlss that have been shown to function in vertebrate cells. we found that our method has a similar true positive rate in this data as it does in yeast, finding 37% of the characterized nlss at the same posterior threshold. however we do note an increased false positive rate, and modest reductions in the nucleotide-level correlation coefficient to and the matthews correlation coefficient to. seeking to understand the elevated rate of false predictions, we explored them further and found that of the vertebrate false positives occur on only three proteins. when we searched the literature for more information on these proteins we found that one of our'false' predictions had actually been identified as an nls. we identified on another protein two patches of amino-acid repeats, and finally on the last protein two nucleolar localization signals, which are long stretches of basic amino acid residues, and it is not yet clear if these signals should be considered as nlss. we noted in total three false predictions composed of amino-acid repeats, which were largely absent from our yeast training set. such repeats are problematic because they violate an assumption of our simple hidden-markov model, namely, that adjacent residues are independent given the value of the hidden state. taken together, this analysis of vertebrate nlss demonstrates that the true positive rate of our method is not confined to our training data set. however, we did note an increase in false positives, which might be explained by additional undiscovered nlss in this data set, or repetitive sequences in vertebrate proteins. discussion analysis of residue frequency clearly shows that there is a bias in key residues in the nls, and while previous studies have shown that there exists some position requirement in these residues, the nlss do not clearly align and therefore we believe that the signal simply do not obey a clear consensus sequence rule. our results are consistent with the model that nlss may simply be regions of high positive charges with only minor spatial requirements. this idea is consistent with the model that the nls can be masked by phosphorylation, by inhibiting the activity of the signal due to addition of negative charges. there is abundant evidence that cnlss bind at specific positions on importin-α and this binding is mediated by two sites which bind monopartite or bipartite cnlss, which suggests that the bipartite cnls is not simply a bigger monopartite cnls. we were, however, unable to exploit this knowledge to create a stronger predictor. while each basic patch in the bipartite cnls does not represent a monopartite cnls, the combination of both patches is sufficient for recognition by our predictor. by examining some false negatives, we find at least two reasons why our method fails to predict them. first, there are examples that do not seem to show an enrichment of basic residues. second, other nlss are simply too small to be identified reliably, due to a lack of statistical signal. we note that unlike psort which is based on the cnls consensus motifs, our method does not attempt to predict nlss belonging to a particular pathway. we observed that all nlss show an excess of basic residues, and therefore we have developed a simple hmm that can identify stretches of basic residues in protein sequences. it is somewhat surprising that this method performs reasonably well. this suggests that the consensus patterns for different import pathways may be more similar than currently anticipated. we believe that obtaining a higher positive predictive value is certainly possible by combining other biological knowledge; however, this is still under study. for example, some of our false predictions might either be real nlss that have not yet been characterized, or simply part of other undiscovered protein domains.  in conclusion, we offer a simplified approach to predicting nuclear localization signals and show that this method can be applied to multiple species. this agrees with the notion that important regulatory mechanisms are conserved, although it is possible that differences in positive predictive value can be attributed to the existence of multiple importin-α,β homologues in other species or differences in proteins lengths between species. 
we test current prediction methods and observe a low true positive rate. we show that our method is able to consistently find 37% of the nlss with a low false positive rate and that our method retains its true positive rate outside of the yeast data set used for the training parameters. the classical nls contains specific patterns of basic residues and computational methods have been designed to predict the location of these motifs on proteins. nuclear localization signals are stretches of residues within a protein that are important for the regulated nuclear import of the protein. of the many import pathways that exist in yeast, the best characterized is termed the'classical' nls pathway. the consensus sequences, or patterns, for the other import pathways are less well-understood. in this paper, we present an analysis of characterized nlss in yeast, and find, despite the large number of nuclear import pathways, that nlss seem to show similar patterns of amino acid residues.
 nuclear localization signals are stretches of residues within a protein that are important for the regulated nuclear import of the protein. of the many import pathways that exist in yeast, the best characterized is termed the'classical' nls pathway. the classical nls contains specific patterns of basic residues and computational methods have been designed to predict the location of these motifs on proteins. the consensus sequences, or patterns, for the other import pathways are less well-understood.  in this paper, we present an analysis of characterized nlss in yeast, and find, despite the large number of nuclear import pathways, that nlss seem to show similar patterns of amino acid residues. we test current prediction methods and observe a low true positive rate. we therefore suggest an approach using hidden markov models to predict novel nlss in proteins. we show that our method is able to consistently find 37% of the nlss with a low false positive rate and that our method retains its true positive rate outside of the yeast data set used for the training parameters.  our implementation of this model, nlstradamus, is made available at: 