BACKGROUND
it is now often possible to obtain the complete genome sequence of an organism in a few months, but without a directed approach, determining the function of potential gene products through biological experimentation is inefficient.
accordingly, methods for function prediction are required to direct experiments in function verification.
in the context of this paper the term function is used to refer to all aspects of a gene product's behaviour.
this includes the concepts described by the gene ontology classifications for molecular function, biological process and cellular component.
it is explicitly stated in the text when a more specific interpretation of function is intended.
a powerful tool in the annotation of novel genomes is the prediction of function by similarity to a sequence of known function.
such 'transitive function assignment' can work very well where there is a clear match to a homologue with a well established function.
however, accurate functional assignment is difficult in cases where the match is less well defined, either due to lower sequence similarity or the presence of many candidates with differing functions.
gerlt and babbitt  <cit>  reviewed a number of examples where sequence similarity alone cannot provide full function specificity.
the examples they discussed included classes of proteins where the function is similar but sequences are diverse, and classes where sequences are similar but function is diverse, indicating potential pitfalls for automated analyses.
these examples are however quite extreme; sequence similarity can be used to infer function for a large proportion of genes with good results.
function annotation of sequences by tools such as pedant  <cit>  and genequiz  <cit>  was dependent on free text annotations in the sequence databases and was complicated by the difficulty of mining and interpreting natural language.
for example, a function may be described in one way in one sequence annotation, only to have the same function described in a different way in another sequence annotation.
such inconsistencies make computational determination of function equivalence difficult if not impossible.
the use of restricted vocabularies and keywords has gone some way towards addressing this problem since it allows direct comparison of sequences with identical annotation schemes, at least to a match/no match level.
ouzounis and karp  <cit>  proposed the transitive annotation based score  to assess qualitatively the differences between annotations provided by different schemes.
this scale relies on a human curator to determine manually the relationship between potentially conflicting terms, so is not readily applicable to the automated analysis of annotations.
keywords and restricted vocabularies do not solve the problem of conflicting assignments.
unless some computable form of relationship is present between terms, it is not possible to provide any automated form of conflict resolution between terms or to identify computationally where one term is a more specific descriptor than another.
an ontology represented as a graph can provide a solution to this problem.
ontologies are restricted vocabularies, or sets of terms where each term is explicitly related to parent terms and child terms .
the gene ontology   <cit>  is a description of biology represented as a directed acyclic graph  where each node represents a clearly defined biological concept.
gene ontology is continually being developed but contained approximately  <dig>  nodes as at march  <dig>
the availability of the gene ontology has provided for the first time, a broadly accepted classification system for function assignment that can be analysed computationally.
previous work using other classification schemes, such as restricted vocabularies based on swissprot keywords, suffered because of the lack of a distinct relationship between terms and/or due to typographical differences  <cit> .
since the establishment of go, several authors have prepared tools that provide function assignment to gene ontology or a subset thereof.
jensen and co-workers  <cit>  used neural networks to provide predictors for a small subset of  <dig> relatively non-specific go terms.
schug et al.
<cit>  used similarity to protein families defined as prodom  <cit>  or cdd  <cit>  domains, by assigning the most specific common function represented in the set of proteins belonging to the family.
this was a relatively conservative approach, taking similarity to clearly defined families annotated with relatively non-specific functions as a basis for transitive annotation.
xie and coworkers  <cit>  have combined sequence similarity data with protein domain matches, cellular location prediction and literature mining data to improve transitive assignments.
their tools provided mappings to individual go terms using a complex collection of probabalistic models and single linkage clustering.
the method appears to be extremely powerful, taking input from a wide variety of sources, but it is difficult to assess the overall accuracy.
two tools based on blast searches have recently been presented in the literature.
ontoblast  <cit>  provided a list of go-terms prepared from gene-association links to similarity matches from blast searches.
go terms associated with the matching sequences are scored according to the e-value of the pairwise match.
goblet  <cit>  also applies blast searches as the basis for assigning go terms but does not give any estimates of validity beyond restricting matches to those below a user defined e-value threshold and counting the number of matching sequences.
in this paper we present a novel method, gotcha, that can be applied to any database search technique that returns scored matches.
we have initially implemented this with blast searches and extend the analysis from the similarity match scores for a search in order to provide an empirical estimate of the confidence in each predicted function.
we have applied this method to malaria   <cit>  and six other well annotated genomes and compared the results obtained by the gotcha method to the results of annotation with the top informative blast match.
the two methods have been assessed quantitatively with seven-fold cross validation by comparing the predictions obtained by gotcha with those provided by the curators of the respective genome sequence consortia.
the assessment of the global accuracy of a particular annotation method is extremely problematic in the absence of a computable annotation scheme.
gene ontology provides such a computable scheme and we present here a quantitative measure for comparison of function annotations based on assignment to go terms.
this provides a metric for direct objective comparison of annotation methods that is independent of arbitrary cut off values.
the new accuracy measure encompasses true positives, false positives and false negatives, so combining sensitivity and selectivity in one value.
RESULTS
two sets of annotation predictions were determined for each data set in the study.
one was based on all available go annotations and the other on a reduced set of go annotations that excluded gene-associations with the evidence code iea .
iea annotations are usually considered to be less reliable as they have not been assessed by a human curator.
in contrast, iss annotations  are annotations which, whilst being derived electronically, have been assessed by a human curator and can be considered sufficiently reliable.
iea annotations may however give a broader coverage than non-iea annotations.
on average, each dataset contained slightly more than 50% iea annotations, though the vast majority of the sequences had some non-iea annotation.
the number of sequences for each dataset is listed in table  <dig> along with a summary of the number of sequences annotated both with and without iea annotations.
function assignment using all gene-associations
the specificities of function prediction for both gotcha and topblast are illustrated in figure  <dig>  figure 3a shows the proportion of predictions by gotcha that are correct with a p-score above the cutoff on the x-axis.
at a p-score cutoff of 50%, the selectivity of gotcha is  <dig> % .
figure 3b shows the proportion of predictions by topblast that are correct with an e-value below the cutoff on the x-axis.
at an e-value of 10- <dig> topblast shows a selectivity of  <dig> % .
accordingly, gotcha outperforms topblast with improved coverage and better selectivity for each genome examined.
both the gotcha and the topblast analyses include gene associations that are children of obsolete  and the three 'unknowns' .
the obsolete terms comprise a very small proportion  of the total number of annotations  and would not be expected to have any significant effect on the results.
the three 'unknowns' however are considered to be valid function descriptions.
they indicate a clearly observed similarity to a sequence with a function that has not been determined more specifically.
function annotation excluding iea annotations
function assignment was repeated using the same blast search results but excluding the iea coded gene-associations.
figure  <dig> illustrates the recall rate for function assignments.
recovery was lower in all but one genome compared to when iea terms were included.
gotcha retrieved 39%  of annotations with a p-score above 50%.
this is 83%  of the proportion of annotations retrieved by gotcha when iea based term associations are included.
topblast retrieved 18%  of annotations with an e-value below 10- <dig>  this is 31–81% of the proportion of annotations retrieved when iea based term associations are included.
topblast only recovers 47%  of the number of annotations recovered by gotcha.
the number of annotations per sequence was reduced by comparison to the data shown in figure  <dig> though the trends were very similar .
the difference between the analysis with and without iea terms is consistent with the relative numbers of iea and non-iea annotations provided by the genome projects as there are only  <dig> %  go term associations per sequence, 62%  of the number of go term associations per sequence when iea terms are included.
one issue with excluding iea annotations is that the coverage of functions in the genome is lowered.
this inevitably will lead to a higher number of positives that have incorrectly been assigned as false as a result of the incomplete sequence annotations.
despite excluding terms for which there is no annotation to the ontology under examination, the results are skewed by assigning a proportion of true positives as false positives.
this indicates that the method is performing more poorly than is in fact the case.
we have examined the nature of the false positives in more detail below.
a metric for quantitative assessment of function annotation
comparing function assignment methods is difficult.
typically the standard against which they are assessed is an incompletely annotated dataset.
both a lack of experminental data confirming potential functions and a lack of knowledge about potential functions can lead to the standard data being less perfectly annotated that would be desired.
it is not realistically possible in an automated analysis to cope with unrecorded true positives that are registered in the analysis as false positives.
it is therefore the case that any analysis of accuracy can only give an estimate of minimum accuracy.
accuracy can also be difficult to compare between two methods that annotate to different subsets of go.
one method may only annotate to relatively general terms, allowing for a better claimed specificity than a method that attempts to annotate to a more specific level.
gotcha predicts at all levels of the go hierarchy.
it assigns a probability to every combination of go term – sequence association and should be compared to other function assignment algorithms using a global metric, one which can account for over-specificity and under-specificity in a set of predictions as well as incorrect assignment.
ouzounis and karp  <cit>  described the tabs system for qualitative assignment of function annotation to eight categories.
the tabs categories are reproduced in table  <dig>
when applied to annotation using a dag such as go the number of potential categories is reduced from the eight described in tabs to three.
tabs was developed to compare annotations where the terms used are not implicitly related through a computable structure such as a dag.
as we are using a dag where ancestor nodes are implicitly associated with the gene through direct association of a child node, the prediction for a particular sequence becomes a set of go terms  comprising all nodes that match the prediction rather than just the most specific terms.
the accuracy of a prediction can then be assessed by observing the presence of nodes in both the node sets for annotations and for the predictions rather than assigning qualitative values.
the more distant a given prediction node set is from the annotation node set, the smaller a proportion of nodes  they will have in common.
the effect of a quantitative approach on the tabs categories is as follows: tabs category  <dig> is unchanged.
this is an exact match and is represented by the presence of the term in the node sets for both original annotation and current prediction.
tabs category  <dig> is no longer relevant.
a controlled vocabulary is being used so there is no scope for typographical errors of the type described by ouzounis and karp or by tsoka  <cit>  or iliopoulos  <cit> .
tabs category  <dig> is also irrelevant.
go has no undefined terms  and all annotation sources are attributed using evidence codes and references.
tabs category  <dig> is an extreme case of category  <dig>  both these categories are represented by the existence of a function annotation in the original annotation node set but not in the predicted node set.
likewise tabs category  <dig> is an extreme case of tabs category  <dig>  in many cases a false positive is represented as an underprediction in the true branch of the go dag and an overprediction in a false branch.
tabs category  <dig> describes the mechanism of occurrence of an error rather than the error itself and is not relevant to this analysis.
in this analysis we reduce the eight tabs categories describing the accuracy of a function prediction for an individual sequence to three categorise that describe each node in the nodeset comprising a function prediction for an individual sequence.
these categories correspond to false positive, false negative and true positive nodes.
a particular sequence annotation node set could potentially contain nodes from all three categories.
quantitation of the analysis
given two sets a and b corresponding to a given annotation set and a predicted set  we are interested in the true matches , false positives  and the false negatives .
the aim of any prediction method is to maximise the number of matches  whilst minimising the errors .
the number of true negatives does not need to be considered as this number is very large and essentially constant over the analysis.
we can use the following relation as an error quotient to assess prediction methods.
where req is the relative error quotient, n is the total false negatives, p is the total false positives, w is a weighting factor and t is the total true positives.
a low req represents a low proportion of errors.
a higher req indicates a higher proportion of errors.
such a measure is dependent upon the population of the node set which in turn is dependent upon the cut off used for selecting predictions in the node set.
figure 6a shows the change in req with respect to p-score cutoff for the gotcha analysis and figure 6b the req with respect to e-value cutoff for the topblast assignments.
a weighting factor of  <dig> was used in both cases, thus giving equal weight to both false positives and false negatives.
in this figure the minima indicate optimum cutoffs for maximising the similarity between annotation and prediction nodesets.
the gotcha results  indicate broad minima, suggesting that small differences in cut off selection may have only a slight effect on the accuracy of the results.
the minima for blast are difficult to see as they are skewed to very high e-values as a result of a large proportion of false negatives.
this indicates that the topblast search is rejecting important information present in matches with e-values approaching  <dig>  much higher than those normally used for genome annotation.
the req metric therefore appears to perform quite robustly.
this metric assigns identical weight to each go term association.
more complex weighted measures of semantic similarity have been proposed by lord and coworkers for searching databases based on annotation  <cit>  but these are difficult to apply to the present problem in a manner that uses a non-arbitrary weighting.
in the absence of iea annotations the spread of the req curves changes dramatically as shown in figure  <dig>  figure 7a illustrates the req for gotcha with the differences between the genomes far less marked than for figure 6a.
in contrast, the req for topblast is shown in figure 7b and shows much higher and more diverse req than when iea terms are included .
minimum req  has been determined for both gotcha and top blast hit annotation sets, both with and without the use of automated annotations  for transitive function assignment .
when automated annotations  are included in the analysis, there is no significant difference between the minimum req obtained using gotcha or that from topblast.
the minimum req for topblast is obtained at very high e-values,  <dig> – <dig>  when iea terms are included  and  <dig> – <dig>  when iea terms are excluded .
when iea annotations are excluded from the analysis gotcha performs significantly better than topblast .
gotcha excluding iea terms performs better  than when iea annotations are included .
it may be that the annotation set used as the reference in comparing these results was incomplete.
this would result in some true positives being incorrectly assigned as false positives with a corresponding increase in req.
however, this would apply similarly to gotcha and to the top blast hit analysis.
assessment of incorrectly assigned false positives
samples of the false positive function predictions by gotcha with the highest p-scores from three p. falciparum chromosomes  were assessed by hand to give an indication of the completeness of the curated annotations.
results for selected sequences in this set are shown in additional file  <dig>  twenty sequences were examined: ten from chromosome  <dig>  and five taken from each of chromosomes  <dig> and  <dig>  chromosome  <dig> was the first to be sequenced and is the most carefully annotated of the chromosomes.
in each case the sequences selected were those with the highest scoring false positive function assignments.
representative results from the analysis of gotcha annotation with and without iea terms are available as supplementary material.
the proportion of correct annotations generally performed better than the p-score would suggest.
taking a p-score of > 50% as a cutoff, most gotcha predictions agreed with the function assigned by the curator.
the false positives fell into several categories:
differences in curator judgement
in some examples, genes that were annotated as encoding hypothetical proteins could be re-annotated based on gotcha predictions.
go terms had not been assigned during the manual curation phase of the p. falciparum genome project if no function had been identified during the first-pass automatic annotation.
however, the addition of go terms to sequences by gotcha prompted the original annotation to be re-evaluated.
for example, pfl1875w shows a hit to the pfam k+ tetramerisation domain  supports the gotcha annotation although it is at a level that genome annotators may feel is marginal.
in pfl1780w, stronger supporting evidence  indicates again that gotcha can suggest go annotations that have been previously overlooked.
in several examples, gotcha predicted either additional functions or more specific go terms to describe previously annotated functions.
pfc0495w encodes a putative aspartyl protease.
when all evidence codes were included, a molecular function of pepsin a activity is predicted.
this protein matches pepsin a domains defined by the interpro entry ipr <dig> , thus the term from gotcha is likely to be correct.
human error
pfl <dig> encodes a thymidylate kinase, which was correctly annotated by gotcha as being involved in dttp biosynthesis.
gotcha also indicates 'dtdp biosynthesis' as a suitable go process term.
thymidylate kinase catalyses the synthesis of dtdp, a necessary step in dttp biosynthesis.
however, the human annotator missed the fact that dtdp biosynthesis is not a 'part of' dttp biosynthesis within the ontology structure and in such cases, terms describing both processes must be employed.
sometimes, gotcha highlighted erroneous omissions in the go annotation of the p. falciparum genome, many of which have arisen from retrospective corrections and amendments to gene models.
for instance, gotcha provides detailed annotation for a putative atpase synthase f <dig> alpha subunit  almost completely lacking useful go terms.
gotcha also suggested go terms relating to translation elongation for pfl1710c.
a highly significant hit to pfam: <dig>  indicates that this gotcha prediction may well be more accurate then the original genome annotation.
iea vs non iea
annotations performed with iea terms appeared to be more specific than those where iea terms were excluded.
in many cases, such as pfc0495w, the difference was quite pronounced.
here the protein was implicated in 'proteolysis and peptidolysis' when all annotations were included but filtering out iea annotations resulted in the more general, and less useful, description of 'metabolism'.
real false positives
out of the  <dig> genes inspected, pfl1825w was the only example where go terms were incorrectly suggested for the biological process, molecular function and cellular component aspects of go.
in other cases, mis-annotations often had low i scores  or were due to terms taken from slightly too far down a branch in the ontology structure.
for example 'atp-binding and phosphorylation-dependent chloride channel' was predicted for pfb0795w, an atp synthase.
the cellular component of gene products are hard to annotate – often blast is insufficient to recognise the targeting information encoded in signal and transit peptides and specific signal sequence detection methods such as psort ii  <cit>  must be used instead.
gotcha consequently made incorrect predictions of subcellular localisation in some cases.
for instance pfl1710c is annotated as having mitochondrial and apicoplast localisation based on separate lines of evidence  <cit>  but gotcha predicted cytoplasmic localisation with a p-score of 52%.
it is hard to measure what proportion of the calculated false positives does in fact represent serious mis-annotation.
although the hand analysis may provide representative examples, it is too small to be of statistical significance.
genuine false positives  were fewer than would be expected from the p-score.
despite the small sample size, these results show that gotcha performs well as a guide to the manual assignment of go terms.
not only can it provide suggestions for more granular annotation but it can highlight terms that would otherwise be missed by a human annotator.
discussion
data interdependency and annotation accuracy
one of the major problems facing assessment of function assignment is the separation of annotation and test datasets.
in this analysis we have tackled this issue by taking individual genome datasets as the test sets and using other genome datasets for the annotation source from which to transitively assign function.
the scoring mechanism used for estimating accuracy values is independent of both test and annotation datasets, since it makes use of sequences that are found in neither.
whilst the sequences are independent, the annotations associated with these sequences may not be.
many of the computationally assigned annotations are derived from analyses involving the 'independent' datasets and can therefore not be regarded as entirely independent.
iea annotations are primarily obtained from sequence similarity searches.
as a consequence it is not surprising that the results obtained for both gotcha and topblast when iea annotations are included are so similar.
interestingly, when iea based annotations are excluded from the topblast analysis, the req goes up.
this may well indicate a degree of inaccuracy in the iea based annotations, or incomplete coverage by the human curated annotations.
gotcha, however, makes a significantly better use of the blast search result in the quality and coverage of the annotation.
false positive/false negative balance in the relative error quotient
the req analyses performed weighted under prediction errors  equally to over prediction errors .
in order to examine the effect of the weighting on req, the gotcha predictions for the human genome were compared to the genome consortium annotations with weights ranging from  <dig>  to  <dig> .
as expected, an increased emphasis on false positives shifts the minimum req towards a higher p-score cutoff.
weighting can be adjusted depending on the aims of the study in question.
the minimum req should give the best tradeoff between accuracy and coverage and can be used to estimate an optimum p-score cutoff for transitive assignment of function.
investigations that emphasise accuracy over coverage may increase the weight to reduce false positives.
investigations with less concern for accuracy but a greater emphasis on coverage will use a lower weight for minimal req determination to increase coverage.
the metric presented here is an objective measure of method performance but has some drawbacks.
using the req as described in this paper, each term in the nodeset is weighted equally.
this may not be the most appropriate measure.
the granularity of terms in gene ontology is not constant across the ontologies, nor is it readily quantifiable.
this may lead to bias in the metric, where differences in the presence or absence of closely related terms is weighted equally to presence or absence of more distantly related terms even though they have the same graph path distance between them.
there is also the issue of prevalence.
some terms occur in almost every nodeset, others are less prevalent.
the most appropriate form for a quantitative metric will need to be examined in future work.
transitive function assignment is limited by the sensitivity of the underlying search method and the scope of the dataset being searched.
the gotcha method of preparing a weighted composite view of the functions from a complete set of search results provides a significant improvement in the annotation of sequences when compared to a method that selects the most significant annotated hit.
gotcha also provides a confidence measure for the putative function assignments, allowing for the determination of an appropriate level of specificity for the annotation set.
hennig and co-workers examined the ability of blast analysis to transitively assign function from distant taxa, concluding that for the majority of cases, go-based annotation would give a good result  <cit> .
in this study we have performed seven-fold cross validation with seven distinct genomes across the taxonomic range.
it is intended to improve the performance of this method by including further genomes and updating the annotations on those already used.
CONCLUSIONS
the gotcha method has several significant advantages over the transitive assignment of function by topblast.
firstly each function assignment has a directly understandable accuracy estimate that can be interpreted without any knowledge of the prediction methodology.
this accuracy estimate is function-specific, unlike general rules of thumb that are applied to interpretation of blast search results.
secondly, the gotcha method provides much greater coverage than a top annotated match approach, annotating more sequences with reasonable confidence.
in many cases it provides annotations for sequences that otherwise would have no annotations.
finally, it provides term specific annotation accuracy estimates.
this is a significant advantage over topblast where every term in the set predicted for an individual sequence has the same value and a biologist interpreting the results is given little indication of which terms can reasonably be accepted.
in contrast, gotcha provides individual p-scores for each term.
this allows a rapid visual examination of the prediction as a graph or a list, indicating appropriate points at which experimental verification may best be directed.
in order to assess the accuracy of annotations to tree-like ontologies we have developed an objective flexible scoring metric that provides a global analysis, including assessment of both false positives and false negatives.
this metric also provides a means for comparison of methods that is not dependent on the selection of any particular parameter threshold or cutoff in the scoring method used.
the underlying mapping methodology applied in gotcha can readily incorporate other search methods that provide a more sensitive similarity search.
combining search methods should also provide a better coverage of sequence space occupied by distant homologues  <cit> , and such potential improvements are the subject of further work.

 it is now often possible to obtain the complete genome sequence of an organism in a few months, but without a directed approach, determining the function of potential gene products through biological experimentation is inefficient. accordingly, methods for function prediction are required to direct experiments in function verification. in the context of this paper the term function is used to refer to all aspects of a gene product's behaviour. this includes the concepts described by the gene ontology classifications for molecular function, biological process and cellular component. it is explicitly stated in the text when a more specific interpretation of function is intended. a powerful tool in the annotation of novel genomes is the prediction of function by similarity to a sequence of known function. such'transitive function assignment' can work very well where there is a clear match to a homologue with a well established function. however, accurate functional assignment is difficult in cases where the match is less well defined, either due to lower sequence similarity or the presence of many candidates with differing functions. gerlt and babbitt reviewed a number of examples where sequence similarity alone cannot provide full function specificity. the examples they discussed included classes of proteins where the function is similar but sequences are diverse, and classes where sequences are similar but function is diverse, indicating potential pitfalls for automated analyses. these examples are however quite extreme; sequence similarity can be used to infer function for a large proportion of genes with good results. function annotation of sequences by tools such as pedant and genequiz was dependent on free text annotations in the sequence databases and was complicated by the difficulty of mining and interpreting natural language. for example, a function may be described in one way in one sequence annotation, only to have the same function described in a different way in another sequence annotation. such inconsistencies make computational determination of function equivalence difficult if not impossible. the use of restricted vocabularies and keywords has gone some way towards addressing this problem since it allows direct comparison of sequences with identical annotation schemes, at least to a match/no match level. ouzounis and karp proposed the transitive annotation based score to assess qualitatively the differences between annotations provided by different schemes. this scale relies on a human curator to determine manually the relationship between potentially conflicting terms, so is not readily applicable to the automated analysis of annotations. keywords and restricted vocabularies do not solve the problem of conflicting assignments. unless some computable form of relationship is present between terms, it is not possible to provide any automated form of conflict resolution between terms or to identify computationally where one term is a more specific descriptor than another. an ontology represented as a graph can provide a solution to this problem. ontologies are restricted vocabularies, or sets of terms where each term is explicitly related to parent terms and child terms. the gene ontology is a description of biology represented as a directed acyclic graph where each node represents a clearly defined biological concept. gene ontology is continually being developed but contained approximately nodes as at march the availability of the gene ontology has provided for the first time, a broadly accepted classification system for function assignment that can be analysed computationally. previous work using other classification schemes, such as restricted vocabularies based on swissprot keywords, suffered because of the lack of a distinct relationship between terms and/or due to typographical differences. since the establishment of go, several authors have prepared tools that provide function assignment to gene ontology or a subset thereof. jensen and co-workers used neural networks to provide predictors for a small subset of relatively non-specific go terms. schug et al. used similarity to protein families defined as prodom or cdd domains, by assigning the most specific common function represented in the set of proteins belonging to the family. this was a relatively conservative approach, taking similarity to clearly defined families annotated with relatively non-specific functions as a basis for transitive annotation. xie and coworkers have combined sequence similarity data with protein domain matches, cellular location prediction and literature mining data to improve transitive assignments. their tools provided mappings to individual go terms using a complex collection of probabalistic models and single linkage clustering. the method appears to be extremely powerful, taking input from a wide variety of sources, but it is difficult to assess the overall accuracy. two tools based on blast searches have recently been presented in the literature. ontoblast provided a list of go-terms prepared from gene-association links to similarity matches from blast searches. go terms associated with the matching sequences are scored according to the e-value of the pairwise match. goblet also applies blast searches as the basis for assigning go terms but does not give any estimates of validity beyond restricting matches to those below a user defined e-value threshold and counting the number of matching sequences. in this paper we present a novel method, gotcha, that can be applied to any database search technique that returns scored matches. we have initially implemented this with blast searches and extend the analysis from the similarity match scores for a search in order to provide an empirical estimate of the confidence in each predicted function. we have applied this method to malaria and six other well annotated genomes and compared the results obtained by the gotcha method to the results of annotation with the top informative blast match. the two methods have been assessed quantitatively with seven-fold cross validation by comparing the predictions obtained by gotcha with those provided by the curators of the respective genome sequence consortia. the assessment of the global accuracy of a particular annotation method is extremely problematic in the absence of a computable annotation scheme. gene ontology provides such a computable scheme and we present here a quantitative measure for comparison of function annotations based on assignment to go terms. this provides a metric for direct objective comparison of annotation methods that is independent of arbitrary cut off values. the new accuracy measure encompasses true positives, false positives and false negatives, so combining sensitivity and selectivity in one value.  two sets of annotation predictions were determined for each data set in the study. one was based on all available go annotations and the other on a reduced set of go annotations that excluded gene-associations with the evidence code iea. iea annotations are usually considered to be less reliable as they have not been assessed by a human curator. in contrast, iss annotations are annotations which, whilst being derived electronically, have been assessed by a human curator and can be considered sufficiently reliable. iea annotations may however give a broader coverage than non-iea annotations. on average, each dataset contained slightly more than 50% iea annotations, though the vast majority of the sequences had some non-iea annotation. the number of sequences for each dataset is listed in table along with a summary of the number of sequences annotated both with and without iea annotations. function assignment using all gene-associations the specificities of function prediction for both gotcha and topblast are illustrated in figure figure 3a shows the proportion of predictions by gotcha that are correct with a p-score above the cutoff on the x-axis. at a p-score cutoff of 50%, the selectivity of gotcha is %. figure 3b shows the proportion of predictions by topblast that are correct with an e-value below the cutoff on the x-axis. at an e-value of 10- topblast shows a selectivity of %. accordingly, gotcha outperforms topblast with improved coverage and better selectivity for each genome examined. both the gotcha and the topblast analyses include gene associations that are children of obsolete and the three'unknowns'. the obsolete terms comprise a very small proportion of the total number of annotations and would not be expected to have any significant effect on the results. the three'unknowns' however are considered to be valid function descriptions. they indicate a clearly observed similarity to a sequence with a function that has not been determined more specifically. function annotation excluding iea annotations function assignment was repeated using the same blast search results but excluding the iea coded gene-associations. figure illustrates the recall rate for function assignments. recovery was lower in all but one genome compared to when iea terms were included. gotcha retrieved 39% of annotations with a p-score above 50%. this is 83% of the proportion of annotations retrieved by gotcha when iea based term associations are included. topblast retrieved 18% of annotations with an e-value below 10- this is 31–81% of the proportion of annotations retrieved when iea based term associations are included. topblast only recovers 47% of the number of annotations recovered by gotcha. the number of annotations per sequence was reduced by comparison to the data shown in figure though the trends were very similar. the difference between the analysis with and without iea terms is consistent with the relative numbers of iea and non-iea annotations provided by the genome projects as there are only % go term associations per sequence, 62% of the number of go term associations per sequence when iea terms are included. one issue with excluding iea annotations is that the coverage of functions in the genome is lowered. this inevitably will lead to a higher number of positives that have incorrectly been assigned as false as a result of the incomplete sequence annotations. despite excluding terms for which there is no annotation to the ontology under examination, the results are skewed by assigning a proportion of true positives as false positives. this indicates that the method is performing more poorly than is in fact the case. we have examined the nature of the false positives in more detail below. a metric for quantitative assessment of function annotation comparing function assignment methods is difficult. typically the standard against which they are assessed is an incompletely annotated dataset. both a lack of experminental data confirming potential functions and a lack of knowledge about potential functions can lead to the standard data being less perfectly annotated that would be desired. it is not realistically possible in an automated analysis to cope with unrecorded true positives that are registered in the analysis as false positives. it is therefore the case that any analysis of accuracy can only give an estimate of minimum accuracy. accuracy can also be difficult to compare between two methods that annotate to different subsets of go. one method may only annotate to relatively general terms, allowing for a better claimed specificity than a method that attempts to annotate to a more specific level. gotcha predicts at all levels of the go hierarchy. it assigns a probability to every combination of go term – sequence association and should be compared to other function assignment algorithms using a global metric, one which can account for over-specificity and under-specificity in a set of predictions as well as incorrect assignment. ouzounis and karp described the tabs system for qualitative assignment of function annotation to eight categories. the tabs categories are reproduced in table when applied to annotation using a dag such as go the number of potential categories is reduced from the eight described in tabs to three. tabs was developed to compare annotations where the terms used are not implicitly related through a computable structure such as a dag. as we are using a dag where ancestor nodes are implicitly associated with the gene through direct association of a child node, the prediction for a particular sequence becomes a set of go terms comprising all nodes that match the prediction rather than just the most specific terms. the accuracy of a prediction can then be assessed by observing the presence of nodes in both the node sets for annotations and for the predictions rather than assigning qualitative values. the more distant a given prediction node set is from the annotation node set, the smaller a proportion of nodes they will have in common. the effect of a quantitative approach on the tabs categories is as follows: tabs category is unchanged. this is an exact match and is represented by the presence of the term in the node sets for both original annotation and current prediction. tabs category is no longer relevant. a controlled vocabulary is being used so there is no scope for typographical errors of the type described by ouzounis and karp or by tsoka or iliopoulos. tabs category is also irrelevant. go has no undefined terms and all annotation sources are attributed using evidence codes and references. tabs category is an extreme case of category both these categories are represented by the existence of a function annotation in the original annotation node set but not in the predicted node set. likewise tabs category is an extreme case of tabs category in many cases a false positive is represented as an underprediction in the true branch of the go dag and an overprediction in a false branch. tabs category describes the mechanism of occurrence of an error rather than the error itself and is not relevant to this analysis. in this analysis we reduce the eight tabs categories describing the accuracy of a function prediction for an individual sequence to three categorise that describe each node in the nodeset comprising a function prediction for an individual sequence. these categories correspond to false positive, false negative and true positive nodes. a particular sequence annotation node set could potentially contain nodes from all three categories. quantitation of the analysis given two sets a and b corresponding to a given annotation set and a predicted set we are interested in the true matches, false positives and the false negatives. the aim of any prediction method is to maximise the number of matches whilst minimising the errors. the number of true negatives does not need to be considered as this number is very large and essentially constant over the analysis. we can use the following relation as an error quotient to assess prediction methods. where req is the relative error quotient, n is the total false negatives, p is the total false positives, w is a weighting factor and t is the total true positives. a low req represents a low proportion of errors. a higher req indicates a higher proportion of errors. such a measure is dependent upon the population of the node set which in turn is dependent upon the cut off used for selecting predictions in the node set. figure 6a shows the change in req with respect to p-score cutoff for the gotcha analysis and figure 6b the req with respect to e-value cutoff for the topblast assignments. a weighting factor of was used in both cases, thus giving equal weight to both false positives and false negatives. in this figure the minima indicate optimum cutoffs for maximising the similarity between annotation and prediction nodesets. the gotcha results indicate broad minima, suggesting that small differences in cut off selection may have only a slight effect on the accuracy of the results. the minima for blast are difficult to see as they are skewed to very high e-values as a result of a large proportion of false negatives. this indicates that the topblast search is rejecting important information present in matches with e-values approaching much higher than those normally used for genome annotation. the req metric therefore appears to perform quite robustly. this metric assigns identical weight to each go term association. more complex weighted measures of semantic similarity have been proposed by lord and coworkers for searching databases based on annotation but these are difficult to apply to the present problem in a manner that uses a non-arbitrary weighting. in the absence of iea annotations the spread of the req curves changes dramatically as shown in figure figure 7a illustrates the req for gotcha with the differences between the genomes far less marked than for figure 6a. in contrast, the req for topblast is shown in figure 7b and shows much higher and more diverse req than when iea terms are included. minimum req has been determined for both gotcha and top blast hit annotation sets, both with and without the use of automated annotations for transitive function assignment. when automated annotations are included in the analysis, there is no significant difference between the minimum req obtained using gotcha or that from topblast. the minimum req for topblast is obtained at very high e-values, – when iea terms are included and – when iea terms are excluded. when iea annotations are excluded from the analysis gotcha performs significantly better than topblast. gotcha excluding iea terms performs better than when iea annotations are included. it may be that the annotation set used as the reference in comparing these results was incomplete. this would result in some true positives being incorrectly assigned as false positives with a corresponding increase in req. however, this would apply similarly to gotcha and to the top blast hit analysis. assessment of incorrectly assigned false positives samples of the false positive function predictions by gotcha with the highest p-scores from three p. falciparum chromosomes were assessed by hand to give an indication of the completeness of the curated annotations. results for selected sequences in this set are shown in additional file twenty sequences were examined: ten from chromosome and five taken from each of chromosomes and chromosome was the first to be sequenced and is the most carefully annotated of the chromosomes. in each case the sequences selected were those with the highest scoring false positive function assignments. representative results from the analysis of gotcha annotation with and without iea terms are available as supplementary material. the proportion of correct annotations generally performed better than the p-score would suggest. taking a p-score of > 50% as a cutoff, most gotcha predictions agreed with the function assigned by the curator. the false positives fell into several categories: differences in curator judgement in some examples, genes that were annotated as encoding hypothetical proteins could be re-annotated based on gotcha predictions. go terms had not been assigned during the manual curation phase of the p. falciparum genome project if no function had been identified during the first-pass automatic annotation. however, the addition of go terms to sequences by gotcha prompted the original annotation to be re-evaluated. for example, pfl1875w shows a hit to the pfam k+ tetramerisation domain supports the gotcha annotation although it is at a level that genome annotators may feel is marginal. in pfl1780w, stronger supporting evidence indicates again that gotcha can suggest go annotations that have been previously overlooked. in several examples, gotcha predicted either additional functions or more specific go terms to describe previously annotated functions. pfc0495w encodes a putative aspartyl protease. when all evidence codes were included, a molecular function of pepsin a activity is predicted. this protein matches pepsin a domains defined by the interpro entry ipr, thus the term from gotcha is likely to be correct. human error pfl encodes a thymidylate kinase, which was correctly annotated by gotcha as being involved in dttp biosynthesis. gotcha also indicates'dtdp biosynthesis' as a suitable go process term. thymidylate kinase catalyses the synthesis of dtdp, a necessary step in dttp biosynthesis. however, the human annotator missed the fact that dtdp biosynthesis is not a'part of' dttp biosynthesis within the ontology structure and in such cases, terms describing both processes must be employed. sometimes, gotcha highlighted erroneous omissions in the go annotation of the p. falciparum genome, many of which have arisen from retrospective corrections and amendments to gene models. for instance, gotcha provides detailed annotation for a putative atpase synthase f alpha subunit almost completely lacking useful go terms. gotcha also suggested go terms relating to translation elongation for pfl1710c. a highly significant hit to pfam: indicates that this gotcha prediction may well be more accurate then the original genome annotation. iea vs non iea annotations performed with iea terms appeared to be more specific than those where iea terms were excluded. in many cases, such as pfc0495w, the difference was quite pronounced. here the protein was implicated in'proteolysis and peptidolysis' when all annotations were included but filtering out iea annotations resulted in the more general, and less useful, description of'metabolism'. real false positives out of the genes inspected, pfl1825w was the only example where go terms were incorrectly suggested for the biological process, molecular function and cellular component aspects of go. in other cases, mis-annotations often had low i scores or were due to terms taken from slightly too far down a branch in the ontology structure. for example'atp-binding and phosphorylation-dependent chloride channel' was predicted for pfb0795w, an atp synthase. the cellular component of gene products are hard to annotate – often blast is insufficient to recognise the targeting information encoded in signal and transit peptides and specific signal sequence detection methods such as psort ii must be used instead. gotcha consequently made incorrect predictions of subcellular localisation in some cases. for instance pfl1710c is annotated as having mitochondrial and apicoplast localisation based on separate lines of evidence but gotcha predicted cytoplasmic localisation with a p-score of 52%. it is hard to measure what proportion of the calculated false positives does in fact represent serious mis-annotation. although the hand analysis may provide representative examples, it is too small to be of statistical significance. genuine false positives were fewer than would be expected from the p-score. despite the small sample size, these results show that gotcha performs well as a guide to the manual assignment of go terms. not only can it provide suggestions for more granular annotation but it can highlight terms that would otherwise be missed by a human annotator. discussion data interdependency and annotation accuracy one of the major problems facing assessment of function assignment is the separation of annotation and test datasets. in this analysis we have tackled this issue by taking individual genome datasets as the test sets and using other genome datasets for the annotation source from which to transitively assign function. the scoring mechanism used for estimating accuracy values is independent of both test and annotation datasets, since it makes use of sequences that are found in neither. whilst the sequences are independent, the annotations associated with these sequences may not be. many of the computationally assigned annotations are derived from analyses involving the'independent' datasets and can therefore not be regarded as entirely independent. iea annotations are primarily obtained from sequence similarity searches. as a consequence it is not surprising that the results obtained for both gotcha and topblast when iea annotations are included are so similar. interestingly, when iea based annotations are excluded from the topblast analysis, the req goes up. this may well indicate a degree of inaccuracy in the iea based annotations, or incomplete coverage by the human curated annotations. gotcha, however, makes a significantly better use of the blast search result in the quality and coverage of the annotation. false positive/false negative balance in the relative error quotient the req analyses performed weighted under prediction errors equally to over prediction errors. in order to examine the effect of the weighting on req, the gotcha predictions for the human genome were compared to the genome consortium annotations with weights ranging from to. as expected, an increased emphasis on false positives shifts the minimum req towards a higher p-score cutoff. weighting can be adjusted depending on the aims of the study in question. the minimum req should give the best tradeoff between accuracy and coverage and can be used to estimate an optimum p-score cutoff for transitive assignment of function. investigations that emphasise accuracy over coverage may increase the weight to reduce false positives. investigations with less concern for accuracy but a greater emphasis on coverage will use a lower weight for minimal req determination to increase coverage. the metric presented here is an objective measure of method performance but has some drawbacks. using the req as described in this paper, each term in the nodeset is weighted equally. this may not be the most appropriate measure. the granularity of terms in gene ontology is not constant across the ontologies, nor is it readily quantifiable. this may lead to bias in the metric, where differences in the presence or absence of closely related terms is weighted equally to presence or absence of more distantly related terms even though they have the same graph path distance between them. there is also the issue of prevalence. some terms occur in almost every nodeset, others are less prevalent. the most appropriate form for a quantitative metric will need to be examined in future work. transitive function assignment is limited by the sensitivity of the underlying search method and the scope of the dataset being searched. the gotcha method of preparing a weighted composite view of the functions from a complete set of search results provides a significant improvement in the annotation of sequences when compared to a method that selects the most significant annotated hit. gotcha also provides a confidence measure for the putative function assignments, allowing for the determination of an appropriate level of specificity for the annotation set. hennig and co-workers examined the ability of blast analysis to transitively assign function from distant taxa, concluding that for the majority of cases, go-based annotation would give a good result. in this study we have performed seven-fold cross validation with seven distinct genomes across the taxonomic range. it is intended to improve the performance of this method by including further genomes and updating the annotations on those already used.  the gotcha method has several significant advantages over the transitive assignment of function by topblast. firstly each function assignment has a directly understandable accuracy estimate that can be interpreted without any knowledge of the prediction methodology. this accuracy estimate is function-specific, unlike general rules of thumb that are applied to interpretation of blast search results. secondly, the gotcha method provides much greater coverage than a top annotated match approach, annotating more sequences with reasonable confidence. in many cases it provides annotations for sequences that otherwise would have no annotations. finally, it provides term specific annotation accuracy estimates. this is a significant advantage over topblast where every term in the set predicted for an individual sequence has the same value and a biologist interpreting the results is given little indication of which terms can reasonably be accepted. in contrast, gotcha provides individual p-scores for each term. this allows a rapid visual examination of the prediction as a graph or a list, indicating appropriate points at which experimental verification may best be directed. in order to assess the accuracy of annotations to tree-like ontologies we have developed an objective flexible scoring metric that provides a global analysis, including assessment of both false positives and false negatives. this metric also provides a means for comparison of methods that is not dependent on the selection of any particular parameter threshold or cutoff in the scoring method used. the underlying mapping methodology applied in gotcha can readily incorporate other search methods that provide a more sensitive similarity search. combining search methods should also provide a better coverage of sequence space occupied by distant homologues, and such potential improvements are the subject of further work. 
the gotcha method is a useful tool for genome annotators. the function of a novel gene product is typically predicted by transitive assignment of annotation from similar sequences. gotcha was compared quantitatively for retrieval of assigned go terms against direct transitive assignment from the highest scoring annotated blast search hit. the gotcha method was applied to the recently sequenced genome for plasmodium falciparum and six other genomes. at a p-score cutoff of 50%, gotcha provided 60% better recovery of annotation terms and 20% higher selectivity than annotation with topblast at an e-value cutoff of 10- gotcha predicts go term associations with term-specific probability measures of confidence. we describe a novel method, gotcha, for predicting gene product function by annotation with gene ontology terms.
 the function of a novel gene product is typically predicted by transitive assignment of annotation from similar sequences. we describe a novel method, gotcha, for predicting gene product function by annotation with gene ontology terms. gotcha predicts go term associations with term-specific probability measures of confidence. term-specific probabilities are a novel feature of gotcha and allow the identification of conflicts or uncertainty in annotation.  the gotcha method was applied to the recently sequenced genome for plasmodium falciparum and six other genomes. gotcha was compared quantitatively for retrieval of assigned go terms against direct transitive assignment from the highest scoring annotated blast search hit. gotcha exploits information deep into the'twilight zone' of similarity search matches, making use of much information that is otherwise discarded by more simplistic approaches. at a p-score cutoff of 50%, gotcha provided 60% better recovery of annotation terms and 20% higher selectivity than annotation with topblast at an e-value cutoff of 10-  the gotcha method is a useful tool for genome annotators. it has identified both errors and omissions in the original plasmodium falciparum annotation and is being adopted by many other genome sequencing projects. 