BACKGROUND
there are currently over six million amino acid sequences known, and only a quarter of a million have been manually annotated  <cit> .
moreover, as estimated by  <cit> , merely for 3% of proteins functional annotation is based on experimental evidence.
due to the advent of super-fast and ultra-low-cost dna sequencing technologies  <cit>  the speed of genome sequencing continues to increase, and sequencing prices continue to plummet.
given the quickly widening gap between the amount of molecular data and the capacity of human experts there is little doubt that electronic annotation by automated software pipelines will be the only source of information about the overwhelming majority of proteins.
in silico annotation generated by bioinformatics methods has the advantage of being efficient and cheap, but at the same time suffers from a notoriously high error level  <cit> .
most of these errors are caused by homology-based annotation transfer where available similarity is not sufficient to warrant the transfer of information from the source to the target sequence, or because the annotation of the source sequence is already wrong.
further complications include the presence of compositionally biased sequence regions, mosaic domain structure of eukaryotic proteins, wrong gene models, and difficulties in recognizing pseudogenes.
the most obvious and direct approach towards improving the reliability and coverage of unsupervised protein annotation entails the development of better bioinformatics tools.
remarkable algorithmic advances of the past decade include more accurate gene prediction techniques , highly sensitive sequence similarity searches based on hidden markov models  <cit> , protein secondary structure prediction approaching the 80% accuracy barrier , novel tools for predicting protein cellular localization  <cit> , improved strategies for annotation transfer by homology , and enhanced protein function prediction by phylogenomics methods  <cit> , to name just a few.
automatic annotation efforts also significantly profit from highly curated and actively maintained information resources, such as sequence  <cit> , pathway  <cit>  and interaction  <cit>  databases, functional and structural classifications of proteins  <cit> , as well as the collections of protein domains and motifs  <cit> .
a complementary tactic to improve the quality of protein sequence databases involves retrospective search for errors in the total corpus of already available annotation.
under this approach protein annotation is considered to be a collection of records, one per each gene, containing a varying number of attributes, ranging from just a few minimal descriptors  for hypothetical proteins, to dozens of annotation items  for better characterized proteins.
modern data mining techniques can be used to identify statistically significant associations between individual attributes, and then to investigate exceptions from such associations that can potentially point to erroneous assignments.
in our earlier work we applied the formalism of association rule mining to extract associations between annotation items in large molecular sequence databases  <cit> .
considering a database with multiple entries, with each entry ascribed a finite number of features, association rules  <cit>  are simple implications that can be formulated in the form  => z, where a <dig> ... an  and z  are different features, and the rule means "database entries that possess all features a <dig> ... an are likely to possess feature z".
the rules of this type are thus positive because they model a positive relation between two item sets.
each rule is characterized by its coverage, the number of entries in the database that possess all features a <dig> ... an, its support, the number of entries satisfying both the left and the right sides of the rule simultaneously, and its strength, which is essentially the probability that a given database entry will satisfy the right side of the rule given that it satisfies the left side of the rule.
our strategy for finding errors in annotation consisted of finding rules with a strength very close, but not equal, to  <dig> , which means that such rules have a minor number of exceptions, and then identifying all proteins that constitute exceptions to these rules.
applied to the swiss-prot  <cit>  database, this approach yielded  <dig>   <dig>  and  <dig> rules with a strength greater than  <dig>  and a coverage of over  <dig> which were not fulfilled exactly once, twice, or three times.
in order to test whether exceptions from strong rules actually correspond to annotation errors subsequent releases of the swiss-prot database were compared and additional manual verification was conducted.
it was indeed found that exceptions to strong rules get corrected substantially more often than the rest of the annotation.
for unsupervised annotation automatically generated by the pedant genome analysis system  <cit>  the total fraction of exceptions from strong rules classified by manual analysis as errors was as high as 68%.
it was also found that most of the errors in the swiss-prot database are under-predictions , consistent with the prudent manual annotation process adopted by swiss-prot, while in pedant errors are typically caused by over-predictions.
in this work we continue to explore the application of rule mining to correcting annotation errors and investigate the utility of negative association rule mining, which, as the name implies, represents the identification of negative relationships between item sets  <cit> .
a negative association rule has the form a <dig> & ... & an  => not z , with a <dig> ... an and z being different features, and the rule means 'database entries that possess all features a <dig> ... an are unlikely to possess feature z'.
for negative rules support is the number of database entries satisfying both the lhs and the rhs, i.e.
those entries that possess all features a <dig> ... an and do not possess the feature z. an additional very important parameter used in this work to characterize negative rules is leverage which is defined as the difference of the rule support and the product of supports of its lhs and rhs.
leverage measures the unexpectedness of a rule as the difference of the actual rule frequency and the probability of finding it by chance with the given frequencies of its rhs and lhs.
a negative association rule is thus an implication from the union of several items to an item negation.
an example of a trivial biologically relevant negative association rule is "nuclear localization => not bacterial origin", i.e.
every protein annotated as localized in the nucleus cannot have a bacterial origin.
as with positive rules, negative rules are not necessarily absolutely strict.
for instance, the rule "operon structure => not eukaryotic origin" has a number of exceptions because bacterial-like operons were described in ceanorhabditis elegans  <cit> .
since these exceptions comprise only a small fraction of the annotated genes, this rule may naturally be interpreted as "the majority of genes constituting an operon structure do not originate from eukaryotic organisms".
in this specific case exceptions from a strong rule are biologically motivated and do not represent errors.
however, in many other cases such exceptions do point to erroneously assigned annotation items.
for example, the rule "intracellular transport vesicles => not bacteria" has four exceptions in the pedant annotation caused by erroneous homology-based transfer of the functional category "intracellular transport vesicles" to four bacterial gene products.
we present a large-scale evaluation of exceptions from strong negative rules in the pedant genome database and assess their utility for detecting and correcting annotation errors.
to our knowledge this is the first application of negative association rule mining to molecular biological data.
methods
extracting item sets from the pedant genome database
pedant software suite  <cit>  is an automatic annotation pipeline that runs various bioinformatics analyses on each protein sequence and stores the results, appropriately parsed, in a relational database.
the associated pedant genome database  <cit>  currently contains pre-computed annotation for  <dig> genomes and a total of more than  <dig>  million gene products.
most of these data were calculated using the version  <dig> of the pedant software, but we are currently deploying the all-new version  <dig> with substantially enhanced capabilities including a new graphical user interface and an extended set of bioinformatics algorithms.
here we used the following  <dig> model genomes freshly processed using pedant <dig> : helicobacter pylori, arabidopsis thaliana, saccharomyces cerevisiae, thermoplasma acidophilum, synechocystis sp., parachlamydia, mycobacterium tuberculosis, aeropyrum pernix, escherichia coli, and bacillus subtilis.
the total of  <dig> gene products were annotated with more than  <dig> million  annotation features suitable for association rule mining .
* for technical reasons gc content values were not available for arabidopsis thaliana genes at the time of writing.
features transferred by similarity  are shown in italic.
a typical annotation entry extracted from pedant for a given gene product has the following form:
"length:s, pi:c, gc:h, bacteria, alpha/beta, do:l, b.
<dig> , fc <dig> , lc: <dig>  fc <dig>  fc <dig> , pf <dig>  cog <dig>  ipr <dig>  fc <dig>  dna-binding, fc <dig>  fc <dig> "
this line describes the antitoxin of the chpb-chps toxin-antitoxin system from escherichia coli as a protein that has small length , acidic isoelectric point , gene with high gc-content, bacterial origin , and low content of disordered regions , does not possess any low complexity regions , has structural class of the 'alpha/beta' type and the pfam  <cit>  domain pf <dig>  it belongs to the ipr <dig> interpro  <cit>  family and the b.
<dig>  scop  <cit>  structural superfamily, and it is a homolog of the uniprot  <cit>  proteins annotated with the keyword "dna-binding".
according to the mips functional catalog  <cit>   the function of this protein is described by the labels fc <dig> , fc <dig>  , fc <dig> , fc <dig>  , fc <dig>  and fc <dig>  .
annotation attributes extracted from pedant can generally be subdivided into three types in terms of their intrinsic susceptibility to errors.
• type  <dig>  features that are definitely known.
this group includes either inherent properties of genes and their products, such as their taxonomic origin, or features that can be unambiguously calculated from primary sequences, such as gc content, length, pi value, percentage of low complexity regions, and so on.
• type  <dig>  structural and functional properties of proteins predicted directly from their amino acid sequences by ab initio computational algorithms .
• type  <dig>  structural and functional properties of proteins derived by similarity searches against previously characterized gene products.
these features include sequence domains, keywords, functional categories, enzyme classes, and functional and structural superfamilies.
it is obvious that the features of type  <dig> are unfaultable and cannot generally contain errors .
features of type  <dig> are typically predicted with the accuracy in the order of 70%  <cit>  by machine learning techniques, such as neural networks or support vector machines.
if no experimental data for a given feature type is available , such predictions can only rarely be further improved by human curation.
finally, features of type  <dig> are transferred from one or several previously annotated gene products to the query protein based on a sufficiently significant degree of similarity.
these features constitute the main bulk of protein-associated information available in the databases, and it is precisely this part of protein annotation that is especially prone to errors due to intrinsic limitations of annotation transfer by homology.
we are interested in applying negative association rule mining for identifying errors in the annotation attributes of type  <dig> transferred by similarity from other proteins; in the annotation entry above such features are shown in italic.
in our dataset there were the total of  <dig> similarity-derived features , more than a half of which were constituted by functional category assignments.
extracting rules from pedant annotation
the annotation set describing  <dig> genes in ten pedant genomes served as input data to extract negative association rules using a modified version of the well-established apriori algorithm for association rule mining.
the basic apriori algorithm, described in detail in  <cit> , is designed to find frequent item sets by consecutive expansion of candidate sets at every step.
it is based on the simple notion that all subsets of a frequent item set are also frequent.
in this work we used a version of this algorithm designed for the efficient negative association rule production  <cit>  implemented and kindly provided by christian borgelt .
the application of the apriori software to pedant annotation results in a file containing one negative rule per line.
each line lists the lhs and the rhs as well as several numerical characteristics of the rule delimited by commas.
a typical rule line in the output file looks like this:
"fc <dig>  & fc <dig>  not length:s,  <dig> ,  <dig>   <dig> ,  <dig>   <dig> ,  <dig>   <dig> ,  <dig> ,  <dig> ,  <dig> "
this notation means that proteins possessing funcat labels  <dig>   and  <dig> ") are unlikely to be of small  length.
the lhs items are joined by the "&" symbol and are followed by the rhs , and the list of numerical attributes of the rule: coverage, coverage count, rhs coverage, rhs coverage count, support, support count, strength, lift, leverage, and leverage count.
in addition to "support count", "coverage count" and "strength", important for positive association rule selection  <cit>  , the numerical parameter "leverage"  is also very important in the case of negative rules.
all existing algorithms allow calculating negative association rules effectively only using a certain threshold on the minimal leverage or leverage count.
here, if not specified otherwise, all rules with the support and the leverage counts of at least  <dig> proteins and strength of at least  <dig>  were retained for further analysis.
analysis of taxon specificity
a considerable and arguably the most valuable part of pedant annotation involves assignments of functional categories based on the mips funcat  <cit> .
a large fraction of negative association rules included a taxon-specific funcat label  on one side of the implication and the taxon of protein origin contradicting this specificity  on the other.
among all  <dig> different funcat labels  used in this study  <dig> were taxon-specific.
for example, one of the taxon-specific rules found was:
"fc <dig>  & fc <dig>  & fc <dig>  & fc <dig>  not bacteria,  <dig> ,  <dig>   <dig> ,  <dig>   <dig> ,  <dig>   <dig> ,  <dig> ,  <dig> ,  <dig> ".
all rules of this kind are a direct consequence of the taxon-specific nature of the underlying  funcat labels.
some of these rules may have exceptions due to annotation transfer by homology between proteins from different taxonomic groups.
we classify such cases as annotation errors according to the general procedure.
manual verification of the rules
for manual verification of negative association rules we randomly selected a limited sample of protein entries from the pedant annotation set that constituted exceptions from rules and could not be corrected by the taxon specific analysis explained in the previous section.
annotation features of these proteins occurring either in the lhs or in the rhs of the rules were subjected to careful manual analysis by an experienced protein annotator according to the established procedures routinely used at mips for genome annotation .
these include assessment of similarity hits and predicted protein features as well as in-depth examination of biological literature describing experimental studies.
an exception was classified as an error if one of the features in the lhs or rhs of the rule was found to be assigned wrongly to the given protein entry.
we then calculated the error rate among all manually analyzed exceptions according to the following formula:
/overall number of exceptions.
manual verification of annotation features
we filtered out wrongly assigned taxon-specific funcat labels and selected randomly a limited sample among all remaining homology-transferred annotation features.
the accuracy of the feature assignment was thoroughly verified by an experienced annotator.
all verified annotation attributes were divided into  <dig> categories: true assignments, false assignments, or "not known".
the latter category was selected if the evidence for a given assignment was not sufficient to make a judgment, but the feature did not obviously contradict the nature of the protein .
features of this category were excluded from further analysis and were not taken into account while estimating the error level.
for example, if in a set of  <dig> features selected for manual verification  <dig> features were classified as 'errors',  <dig> as 'correct assignments', and  <dig> as 'not known', then the final estimate of the error level in this sample was 100*40/ = 42%.
RESULTS
statistics of negative association rules in the pedant annotation
application of the apriori algorithm to the annotation set extracted from pedant resulted in  <dig> negative rules .
for example, one of the most trivial rules found was "bacteria, not eukaryota,  <dig> ,  <dig>   <dig> ,  <dig>   <dig> ,  <dig>   <dig> ,  <dig> ,  <dig> ,  <dig> ".
this rule is satisfied in all possible cases and thus its strength is  <dig>  with no exceptions.
in total there were  <dig> such rules calculated.
much more interesting rules in the context of this study are those of strength very close, but not equal to  <dig> .
these rules have a small number of exceptions that may constitute annotation errors.
there were  <dig> such rules with  <dig> exceptions in total.
an example of such rules is "nuclear protein, not bacteria,  <dig> ,  <dig>   <dig> ,  <dig>   <dig> ,  <dig>   <dig> ,  <dig> ,  <dig> ,  <dig> ".
this statement which is obvious from the biological point of view nevertheless does not make an absolute rule; in fact out of all  <dig> protein entries annotated by the keyword "nuclear protein" in the pedant database only  <dig> actually have eukaryotic origin.
the ten proteins constituting exceptions from this rule  simply inherit this keyword from their eukaryotic homologs.
in our example, the homolog is human oligoribonuclease , one of the alternatively spliced isoforms of which is localized to the nucleus.
some aspects of negative rule statistics differ significantly from positive association rules due to vastly different item frequencies.
because annotation items themselves are rare, and most items are in fact extremely rare  of proteins analyzed), their negations used in negative association rule mining are unavoidably very frequent.
this simple circumstance makes the calculation of negative rules computationally much more challenging compared to positive rules and necessitates the application of much stricter thresholds on the rules of interest.
while analyzing rule strength distribution we considered only the rules exhibiting strength higher than  <dig> .
the number of weaker rules  is too high due to the combinatorial explosion caused by random feature combinations, making their analysis computationally prohibitive.
however, even in the strength interval  <dig>  –  <dig>  the number of negative rules is several orders of magnitude higher that the number of positive rules.
to make the task computationally tractable we additionally imposed a threshold on minimal leverage which effectively helps to select only the most 'non-random' rules  and eliminates all rules with the strength below  <dig> .
the distributions of negative rule strength with different minimal coverage counts are plotted in figure  <dig>
the fraction of proteins in the pedant database constituting exceptions from strong rules in the strength interval between  <dig>  and  <dig>  as well as the fraction of relevant  features participating in such rules is very low.
in total, we identified  <dig> features  in the annotation of  <dig> proteins  as potential annotation errors.
analysis of potentially erroneous annotation features
taxon-specific rules
in order to estimate the number of actual annotation errors among exceptions from strong rules the first test was designed to exclude the influence of taxon specificity.
it turned out that a very large number of rules combined funcat labels on one side of the rule with the taxon of the protein origin on the other side .
there were  <dig> rules  with such structure.
because many funcat labels are taxon-specific , these labels should ideally only be present in the annotation of the genes belonging to the corresponding taxa; homology-based transfer of such annotation attributes is highly prone to error.
where a taxonomically specific funcat label is incompatible with the known gene taxon, it is the funcat assignment which is guaranteed to be erroneous, since the protein origin is doubtlessly known.
this simple test resulted in automatic correction of almost 50% of all exceptions in our set of strong negative rules.
figure  <dig> shows how the fraction of corrected exceptions among all exceptions depends on the rule strength.
performance of the method
after the filter for taxonomy-specific funcat labels was implemented, the set of  <dig> rules formed all negative rules for our annotation sample.
these rules involved  <dig> transferable features  in the annotation of  <dig> proteins .
to estimate the prevalence of errors among exceptions not corrected by the taxonomy procedure described above we selected randomly a sample of  <dig> rules and analyzed their exceptions manually.
in 96% of examined exceptions at least one of the features constituting the rule was assigned wrongly to the given protein.
the overall specificity of the approach was estimated to be as high as 98%: practically all feature combinations associated with exceptions included at least one annotation error.
the specificity of the negative rules is thus much higher than that in the case of positive rules  <cit>  which was estimated to be around 68% based on careful manual verification.
by design, exceptions from negative association rules can only reveal over-annotation, i.e.
erroneous assignment of attributes to protein entries, while under-annotation  cannot be detected.
while manually curated databases are typically under-annotated and this approach is not efficient for them , over-annotation is a typical problem of many automatic software pipelines, including pedant, and the ability to correct this type of errors using negative rule mining is valuable.
at the same time, the approach based on exceptions from strong negative rules yields much smaller coverage than positive rule mining.
as seen in figure  <dig>  negative rule mining allows identifying  <dig> times fewer annotation features  that participate in incompatible feature combinations.
more than two thirds of these features do not get detected by positive rule mining.
what fraction of the annotation features flagged by the negative rules are actual annotation errors?
our approach is designed to flag incompatible feature combinations for subsequent manual inspection rather than to automatically correct annotation errors in an unsupervised fashion.
with the exception of taxon-specific rules where funcat labels incompatible with the taxonomic origin of a protein are guaranteed to be errors, we do not know exactly which feature of a flagged feature combination is wrong.
besides there always exists a chance that all features constituting an exception from a strong negative rule are nevertheless correctly assigned and that the exception is in fact biologically motivated.
it would be desirable to validate our predictions against high-quality manually curated databases such as swiss-prot or brenda  <cit> , but this, unfortunately cannot be done at sufficiently large scale.
as discussed above most of the annotation errors found in pedant are over-predictions which can not easily be confirmed by comparison with swiss-prot entries as the latter tend to be under-annotated.
if a certain feature is present in a swiss-prot entry, it is almost certainly correct, however, if a feature is absent no statement can generally be made.
brenda focuses on one aspect of protein annotation – ec numbers – providing detailed classification of enzymes at four hierarchical levels.
correspondingly, there are only few proteins associated with each four digit ec number while association rule mining relies on frequent annotation items.
in this study rules were required to have coverage count of at least  <dig>  and only six ec numbers satisfied this condition.
we therefore attempted to estimate the fraction of actual annotation errors among those features flagged as suspicious and, for comparison, in non-flagged features by careful manual inspection as described in methods.
as seen in table  <dig>  features flagged as suspicious are almost  <dig>  fold enriched in actual annotation errors than the unmarked ones.
CONCLUSIONS
based on our assessment it becomes apparent that almost all incompatible feature combinations found by negative association rule mining include at least one wrongly assigned annotation term.
the fraction of individual features flagged as suspicious is about  <dig> % from the total number of features assigned by pedant and it is significantly enriched in annotation errors.
moreover, roughly two thirds of such erroneous assignments are not identified by positive rule mining.
we conclude that applying a combination of positive rule mining described earlier  <cit>  and negative rule mining presented creates an opportunity to enhance the fidelity of genome annotation in two alternative ways.
first, insights about the sources of annotation errors gained in this investigation can be used to adjust the automatic annotation pipeline in order to minimize generation of these errors in the future.
examples of such possible modifications include taxon-specific homology-based transfer of functional categories and utilization of individualized similarity thresholds for various features.
second, suspicious features can be visually marked for subsequent inspection by the user.
while this approach is better suited for manually curated databases where errors actually get corrected by human experts, it is also useful for automatic systems such as pedant where users get alerted to specific less trusted annotation items that should be used with caution.
authors' contributions
iia and df conceived the study.
iia designed and executed the analysis of negative rules and rule statistics.
gf conducted manual verification of predicted annotation errors.
df supervised the project.
all authors participated in the drafting and revising of the manuscript, and read and approved the final manuscript.
supplementary material
additional file 1
the set of all negative rules used in this work.
rules.out
click here for file
acknowledgements
we would like to thank christian borgelt for kindly providing his software for association rule mining and his assistance in its adaptation to the negative rule case, shichao and chengqi zhang for providing the initial version of the negative mining algorithm, mikhail gelfand for insightful discussions, urban hafner for technical assistance, and the anonymous reviewers for the valuable suggestions and corrections.
this work was conducted in the framework of the biosapiens network of excellence funded by the european commission fp <dig> programme, under the thematic area "life sciences, genomics and biotechnology for health", contract number lhsg-ct-2003- <dig>  iia was partially supported by the russian academy of sciences .

 there are currently over six million amino acid sequences known, and only a quarter of a million have been manually annotated. moreover, as estimated by, merely for 3% of proteins functional annotation is based on experimental evidence. due to the advent of super-fast and ultra-low-cost dna sequencing technologies the speed of genome sequencing continues to increase, and sequencing prices continue to plummet. given the quickly widening gap between the amount of molecular data and the capacity of human experts there is little doubt that electronic annotation by automated software pipelines will be the only source of information about the overwhelming majority of proteins. in silico annotation generated by bioinformatics methods has the advantage of being efficient and cheap, but at the same time suffers from a notoriously high error level. most of these errors are caused by homology-based annotation transfer where available similarity is not sufficient to warrant the transfer of information from the source to the target sequence, or because the annotation of the source sequence is already wrong. further complications include the presence of compositionally biased sequence regions, mosaic domain structure of eukaryotic proteins, wrong gene models, and difficulties in recognizing pseudogenes. the most obvious and direct approach towards improving the reliability and coverage of unsupervised protein annotation entails the development of better bioinformatics tools. remarkable algorithmic advances of the past decade include more accurate gene prediction techniques, highly sensitive sequence similarity searches based on hidden markov models, protein secondary structure prediction approaching the 80% accuracy barrier, novel tools for predicting protein cellular localization, improved strategies for annotation transfer by homology, and enhanced protein function prediction by phylogenomics methods, to name just a few. automatic annotation efforts also significantly profit from highly curated and actively maintained information resources, such as sequence, pathway and interaction databases, functional and structural classifications of proteins, as well as the collections of protein domains and motifs. a complementary tactic to improve the quality of protein sequence databases involves retrospective search for errors in the total corpus of already available annotation. under this approach protein annotation is considered to be a collection of records, one per each gene, containing a varying number of attributes, ranging from just a few minimal descriptors for hypothetical proteins, to dozens of annotation items for better characterized proteins. modern data mining techniques can be used to identify statistically significant associations between individual attributes, and then to investigate exceptions from such associations that can potentially point to erroneous assignments. in our earlier work we applied the formalism of association rule mining to extract associations between annotation items in large molecular sequence databases. considering a database with multiple entries, with each entry ascribed a finite number of features, association rules are simple implications that can be formulated in the form => z, where a... an and z are different features, and the rule means "database entries that possess all features a... an are likely to possess feature z". the rules of this type are thus positive because they model a positive relation between two item sets. each rule is characterized by its coverage, the number of entries in the database that possess all features a... an, its support, the number of entries satisfying both the left and the right sides of the rule simultaneously, and its strength, which is essentially the probability that a given database entry will satisfy the right side of the rule given that it satisfies the left side of the rule. our strategy for finding errors in annotation consisted of finding rules with a strength very close, but not equal, to, which means that such rules have a minor number of exceptions, and then identifying all proteins that constitute exceptions to these rules. applied to the swiss-prot database, this approach yielded and rules with a strength greater than and a coverage of over which were not fulfilled exactly once, twice, or three times. in order to test whether exceptions from strong rules actually correspond to annotation errors subsequent releases of the swiss-prot database were compared and additional manual verification was conducted. it was indeed found that exceptions to strong rules get corrected substantially more often than the rest of the annotation. for unsupervised annotation automatically generated by the pedant genome analysis system the total fraction of exceptions from strong rules classified by manual analysis as errors was as high as 68%. it was also found that most of the errors in the swiss-prot database are under-predictions, consistent with the prudent manual annotation process adopted by swiss-prot, while in pedant errors are typically caused by over-predictions. in this work we continue to explore the application of rule mining to correcting annotation errors and investigate the utility of negative association rule mining, which, as the name implies, represents the identification of negative relationships between item sets. a negative association rule has the form a &... & an => not z, with a... an and z being different features, and the rule means'database entries that possess all features a... an are unlikely to possess feature z'. for negative rules support is the number of database entries satisfying both the lhs and the rhs, i.e. those entries that possess all features a... an and do not possess the feature z. an additional very important parameter used in this work to characterize negative rules is leverage which is defined as the difference of the rule support and the product of supports of its lhs and rhs. leverage measures the unexpectedness of a rule as the difference of the actual rule frequency and the probability of finding it by chance with the given frequencies of its rhs and lhs. a negative association rule is thus an implication from the union of several items to an item negation. an example of a trivial biologically relevant negative association rule is "nuclear localization => not bacterial origin", i.e. every protein annotated as localized in the nucleus cannot have a bacterial origin. as with positive rules, negative rules are not necessarily absolutely strict. for instance, the rule "operon structure => not eukaryotic origin" has a number of exceptions because bacterial-like operons were described in ceanorhabditis elegans. since these exceptions comprise only a small fraction of the annotated genes, this rule may naturally be interpreted as "the majority of genes constituting an operon structure do not originate from eukaryotic organisms". in this specific case exceptions from a strong rule are biologically motivated and do not represent errors. however, in many other cases such exceptions do point to erroneously assigned annotation items. for example, the rule "intracellular transport vesicles => not bacteria" has four exceptions in the pedant annotation caused by erroneous homology-based transfer of the functional category "intracellular transport vesicles" to four bacterial gene products. we present a large-scale evaluation of exceptions from strong negative rules in the pedant genome database and assess their utility for detecting and correcting annotation errors. to our knowledge this is the first application of negative association rule mining to molecular biological data. methods extracting item sets from the pedant genome database pedant software suite is an automatic annotation pipeline that runs various bioinformatics analyses on each protein sequence and stores the results, appropriately parsed, in a relational database. the associated pedant genome database currently contains pre-computed annotation for genomes and a total of more than million gene products. most of these data were calculated using the version of the pedant software, but we are currently deploying the all-new version with substantially enhanced capabilities including a new graphical user interface and an extended set of bioinformatics algorithms. here we used the following model genomes freshly processed using pedant: helicobacter pylori, arabidopsis thaliana, saccharomyces cerevisiae, thermoplasma acidophilum, synechocystis sp., parachlamydia, mycobacterium tuberculosis, aeropyrum pernix, escherichia coli, and bacillus subtilis. the total of gene products were annotated with more than million annotation features suitable for association rule mining. * for technical reasons gc content values were not available for arabidopsis thaliana genes at the time of writing. features transferred by similarity are shown in italic. a typical annotation entry extracted from pedant for a given gene product has the following form: "length:s, pi:c, gc:h, bacteria, alpha/beta, do:l, b., fc, lc: fc fc, pf cog ipr fc dna-binding, fc fc " this line describes the antitoxin of the chpb-chps toxin-antitoxin system from escherichia coli as a protein that has small length, acidic isoelectric point, gene with high gc-content, bacterial origin, and low content of disordered regions, does not possess any low complexity regions, has structural class of the'alpha/beta' type and the pfam domain pf it belongs to the ipr interpro family and the b. scop structural superfamily, and it is a homolog of the uniprot proteins annotated with the keyword "dna-binding". according to the mips functional catalog the function of this protein is described by the labels fc, fc, fc, fc, fc and fc. annotation attributes extracted from pedant can generally be subdivided into three types in terms of their intrinsic susceptibility to errors. • type features that are definitely known. this group includes either inherent properties of genes and their products, such as their taxonomic origin, or features that can be unambiguously calculated from primary sequences, such as gc content, length, pi value, percentage of low complexity regions, and so on. • type structural and functional properties of proteins predicted directly from their amino acid sequences by ab initio computational algorithms. • type structural and functional properties of proteins derived by similarity searches against previously characterized gene products. these features include sequence domains, keywords, functional categories, enzyme classes, and functional and structural superfamilies. it is obvious that the features of type are unfaultable and cannot generally contain errors. features of type are typically predicted with the accuracy in the order of 70% by machine learning techniques, such as neural networks or support vector machines. if no experimental data for a given feature type is available, such predictions can only rarely be further improved by human curation. finally, features of type are transferred from one or several previously annotated gene products to the query protein based on a sufficiently significant degree of similarity. these features constitute the main bulk of protein-associated information available in the databases, and it is precisely this part of protein annotation that is especially prone to errors due to intrinsic limitations of annotation transfer by homology. we are interested in applying negative association rule mining for identifying errors in the annotation attributes of type transferred by similarity from other proteins; in the annotation entry above such features are shown in italic. in our dataset there were the total of similarity-derived features, more than a half of which were constituted by functional category assignments. extracting rules from pedant annotation the annotation set describing genes in ten pedant genomes served as input data to extract negative association rules using a modified version of the well-established apriori algorithm for association rule mining. the basic apriori algorithm, described in detail in, is designed to find frequent item sets by consecutive expansion of candidate sets at every step. it is based on the simple notion that all subsets of a frequent item set are also frequent. in this work we used a version of this algorithm designed for the efficient negative association rule production implemented and kindly provided by christian borgelt. the application of the apriori software to pedant annotation results in a file containing one negative rule per line. each line lists the lhs and the rhs as well as several numerical characteristics of the rule delimited by commas. a typical rule line in the output file looks like this: "fc & fc not length:s,,,,,,, " this notation means that proteins possessing funcat labels and ") are unlikely to be of small length. the lhs items are joined by the "&" symbol and are followed by the rhs, and the list of numerical attributes of the rule: coverage, coverage count, rhs coverage, rhs coverage count, support, support count, strength, lift, leverage, and leverage count. in addition to "support count", "coverage count" and "strength", important for positive association rule selection, the numerical parameter "leverage" is also very important in the case of negative rules. all existing algorithms allow calculating negative association rules effectively only using a certain threshold on the minimal leverage or leverage count. here, if not specified otherwise, all rules with the support and the leverage counts of at least proteins and strength of at least were retained for further analysis. analysis of taxon specificity a considerable and arguably the most valuable part of pedant annotation involves assignments of functional categories based on the mips funcat. a large fraction of negative association rules included a taxon-specific funcat label on one side of the implication and the taxon of protein origin contradicting this specificity on the other. among all different funcat labels used in this study were taxon-specific. for example, one of the taxon-specific rules found was: "fc & fc & fc & fc not bacteria,,,,,,, ". all rules of this kind are a direct consequence of the taxon-specific nature of the underlying funcat labels. some of these rules may have exceptions due to annotation transfer by homology between proteins from different taxonomic groups. we classify such cases as annotation errors according to the general procedure. manual verification of the rules for manual verification of negative association rules we randomly selected a limited sample of protein entries from the pedant annotation set that constituted exceptions from rules and could not be corrected by the taxon specific analysis explained in the previous section. annotation features of these proteins occurring either in the lhs or in the rhs of the rules were subjected to careful manual analysis by an experienced protein annotator according to the established procedures routinely used at mips for genome annotation. these include assessment of similarity hits and predicted protein features as well as in-depth examination of biological literature describing experimental studies. an exception was classified as an error if one of the features in the lhs or rhs of the rule was found to be assigned wrongly to the given protein entry. we then calculated the error rate among all manually analyzed exceptions according to the following formula: /overall number of exceptions. manual verification of annotation features we filtered out wrongly assigned taxon-specific funcat labels and selected randomly a limited sample among all remaining homology-transferred annotation features. the accuracy of the feature assignment was thoroughly verified by an experienced annotator. all verified annotation attributes were divided into categories: true assignments, false assignments, or "not known". the latter category was selected if the evidence for a given assignment was not sufficient to make a judgment, but the feature did not obviously contradict the nature of the protein. features of this category were excluded from further analysis and were not taken into account while estimating the error level. for example, if in a set of features selected for manual verification features were classified as'errors', as'correct assignments', and as'not known', then the final estimate of the error level in this sample was 100*40/ = 42%.  statistics of negative association rules in the pedant annotation application of the apriori algorithm to the annotation set extracted from pedant resulted in negative rules. for example, one of the most trivial rules found was "bacteria, not eukaryota,,,,,,, ". this rule is satisfied in all possible cases and thus its strength is with no exceptions. in total there were such rules calculated. much more interesting rules in the context of this study are those of strength very close, but not equal to. these rules have a small number of exceptions that may constitute annotation errors. there were such rules with exceptions in total. an example of such rules is "nuclear protein, not bacteria,,,,,,, ". this statement which is obvious from the biological point of view nevertheless does not make an absolute rule; in fact out of all protein entries annotated by the keyword "nuclear protein" in the pedant database only actually have eukaryotic origin. the ten proteins constituting exceptions from this rule simply inherit this keyword from their eukaryotic homologs. in our example, the homolog is human oligoribonuclease, one of the alternatively spliced isoforms of which is localized to the nucleus. some aspects of negative rule statistics differ significantly from positive association rules due to vastly different item frequencies. because annotation items themselves are rare, and most items are in fact extremely rare of proteins analyzed), their negations used in negative association rule mining are unavoidably very frequent. this simple circumstance makes the calculation of negative rules computationally much more challenging compared to positive rules and necessitates the application of much stricter thresholds on the rules of interest. while analyzing rule strength distribution we considered only the rules exhibiting strength higher than. the number of weaker rules is too high due to the combinatorial explosion caused by random feature combinations, making their analysis computationally prohibitive. however, even in the strength interval – the number of negative rules is several orders of magnitude higher that the number of positive rules. to make the task computationally tractable we additionally imposed a threshold on minimal leverage which effectively helps to select only the most'non-random' rules and eliminates all rules with the strength below. the distributions of negative rule strength with different minimal coverage counts are plotted in figure the fraction of proteins in the pedant database constituting exceptions from strong rules in the strength interval between and as well as the fraction of relevant features participating in such rules is very low. in total, we identified features in the annotation of proteins as potential annotation errors. analysis of potentially erroneous annotation features taxon-specific rules in order to estimate the number of actual annotation errors among exceptions from strong rules the first test was designed to exclude the influence of taxon specificity. it turned out that a very large number of rules combined funcat labels on one side of the rule with the taxon of the protein origin on the other side. there were rules with such structure. because many funcat labels are taxon-specific, these labels should ideally only be present in the annotation of the genes belonging to the corresponding taxa; homology-based transfer of such annotation attributes is highly prone to error. where a taxonomically specific funcat label is incompatible with the known gene taxon, it is the funcat assignment which is guaranteed to be erroneous, since the protein origin is doubtlessly known. this simple test resulted in automatic correction of almost 50% of all exceptions in our set of strong negative rules. figure shows how the fraction of corrected exceptions among all exceptions depends on the rule strength. performance of the method after the filter for taxonomy-specific funcat labels was implemented, the set of rules formed all negative rules for our annotation sample. these rules involved transferable features in the annotation of proteins. to estimate the prevalence of errors among exceptions not corrected by the taxonomy procedure described above we selected randomly a sample of rules and analyzed their exceptions manually. in 96% of examined exceptions at least one of the features constituting the rule was assigned wrongly to the given protein. the overall specificity of the approach was estimated to be as high as 98%: practically all feature combinations associated with exceptions included at least one annotation error. the specificity of the negative rules is thus much higher than that in the case of positive rules which was estimated to be around 68% based on careful manual verification. by design, exceptions from negative association rules can only reveal over-annotation, i.e. erroneous assignment of attributes to protein entries, while under-annotation cannot be detected. while manually curated databases are typically under-annotated and this approach is not efficient for them, over-annotation is a typical problem of many automatic software pipelines, including pedant, and the ability to correct this type of errors using negative rule mining is valuable. at the same time, the approach based on exceptions from strong negative rules yields much smaller coverage than positive rule mining. as seen in figure negative rule mining allows identifying times fewer annotation features that participate in incompatible feature combinations. more than two thirds of these features do not get detected by positive rule mining. what fraction of the annotation features flagged by the negative rules are actual annotation errors? our approach is designed to flag incompatible feature combinations for subsequent manual inspection rather than to automatically correct annotation errors in an unsupervised fashion. with the exception of taxon-specific rules where funcat labels incompatible with the taxonomic origin of a protein are guaranteed to be errors, we do not know exactly which feature of a flagged feature combination is wrong. besides there always exists a chance that all features constituting an exception from a strong negative rule are nevertheless correctly assigned and that the exception is in fact biologically motivated. it would be desirable to validate our predictions against high-quality manually curated databases such as swiss-prot or brenda, but this, unfortunately cannot be done at sufficiently large scale. as discussed above most of the annotation errors found in pedant are over-predictions which can not easily be confirmed by comparison with swiss-prot entries as the latter tend to be under-annotated. if a certain feature is present in a swiss-prot entry, it is almost certainly correct, however, if a feature is absent no statement can generally be made. brenda focuses on one aspect of protein annotation – ec numbers – providing detailed classification of enzymes at four hierarchical levels. correspondingly, there are only few proteins associated with each four digit ec number while association rule mining relies on frequent annotation items. in this study rules were required to have coverage count of at least and only six ec numbers satisfied this condition. we therefore attempted to estimate the fraction of actual annotation errors among those features flagged as suspicious and, for comparison, in non-flagged features by careful manual inspection as described in methods. as seen in table features flagged as suspicious are almost fold enriched in actual annotation errors than the unmarked ones.  based on our assessment it becomes apparent that almost all incompatible feature combinations found by negative association rule mining include at least one wrongly assigned annotation term. the fraction of individual features flagged as suspicious is about % from the total number of features assigned by pedant and it is significantly enriched in annotation errors. moreover, roughly two thirds of such erroneous assignments are not identified by positive rule mining. we conclude that applying a combination of positive rule mining described earlier and negative rule mining presented creates an opportunity to enhance the fidelity of genome annotation in two alternative ways. first, insights about the sources of annotation errors gained in this investigation can be used to adjust the automatic annotation pipeline in order to minimize generation of these errors in the future. examples of such possible modifications include taxon-specific homology-based transfer of functional categories and utilization of individualized similarity thresholds for various features. second, suspicious features can be visually marked for subsequent inspection by the user. while this approach is better suited for manually curated databases where errors actually get corrected by human experts, it is also useful for automatic systems such as pedant where users get alerted to specific less trusted annotation items that should be used with caution. authors' contributions iia and df conceived the study. iia designed and executed the analysis of negative rules and rule statistics. gf conducted manual verification of predicted annotation errors. df supervised the project. all authors participated in the drafting and revising of the manuscript, and read and approved the final manuscript. supplementary material additional file 1 the set of all negative rules used in this work. rules.out click here for file acknowledgements we would like to thank christian borgelt for kindly providing his software for association rule mining and his assistance in its adaptation to the negative rule case, shichao and chengqi zhang for providing the initial version of the negative mining algorithm, mikhail gelfand for insightful discussions, urban hafner for technical assistance, and the anonymous reviewers for the valuable suggestions and corrections. this work was conducted in the framework of the biosapiens network of excellence funded by the european commission fp programme, under the thematic area "life sciences, genomics and biotechnology for health", contract number lhsg-ct-2003- iia was partially supported by the russian academy of sciences.
we have previously demonstrated that data mining in large sequence annotation databanks can help identify annotation items that are strongly associated with each other, and that exceptions from strong positive association rules often point to potential annotation errors. positive rule mining does not identify two thirds of these errors. the approach based on exceptions from negative rules is much more specific than positive rule mining, but its coverage is significantly lower. spurious functional assignments are usually caused by unwarranted homology-based transfer of information from existing database entries to the new target sequences. the fraction of annotation features flagged by this approach as suspicious is strongly enriched in errors and constitutes about % of the whole body of the similarity-transferred annotation in the pedant genome database. mining of both negative and positive association rules is a potent tool for finding significant trends in protein annotation and flagging doubtful features for further inspection. here we investigate the applicability of negative association rule mining to revealing erroneously assigned annotation items. almost all exceptions from strong negative association rules are connected to at least one wrong attribute in the feature combination making up the rule.
 unsupervised annotation of proteins by software pipelines suffers from very high error rates. spurious functional assignments are usually caused by unwarranted homology-based transfer of information from existing database entries to the new target sequences. we have previously demonstrated that data mining in large sequence annotation databanks can help identify annotation items that are strongly associated with each other, and that exceptions from strong positive association rules often point to potential annotation errors. here we investigate the applicability of negative association rule mining to revealing erroneously assigned annotation items.  almost all exceptions from strong negative association rules are connected to at least one wrong attribute in the feature combination making up the rule. the fraction of annotation features flagged by this approach as suspicious is strongly enriched in errors and constitutes about % of the whole body of the similarity-transferred annotation in the pedant genome database. positive rule mining does not identify two thirds of these errors. the approach based on exceptions from negative rules is much more specific than positive rule mining, but its coverage is significantly lower.  mining of both negative and positive association rules is a potent tool for finding significant trends in protein annotation and flagging doubtful features for further inspection. 