Threshold Average Precision (TAP-k): a measure of retrieval designed for bioinformatics

Abstract

Motivation: Since database retrieval is a fundamental operation, the measurement of retrieval efficacy is critical to progress in bioinformatics. This article points out some issues with current methods of measuring retrieval efficacy and suggests some improvements. In particular, many studies have used the pooled receiver operating characteristic for n irrelevant records (ROC(n)) score, the area under the ROC curve (AUC) of a 'pooled' ROC curve, truncated at n irrelevant records. Unfortunately, the pooled ROC(n) score does not faithfully reflect actual usage of retrieval algorithms. Additionally, a pooled ROC(n) score can be very sensitive to retrieval results from as little as a single query.

Methods: To replace the pooled ROC(n) score, we propose the Threshold Average Precision (TAP-k), a measure closely related to the well-known average precision in information retrieval, but reflecting the usage of E-values in bioinformatics. Furthermore, in addition to conditions previously given in the literature, we introduce three new criteria that an ideal measure of retrieval efficacy should satisfy.

Results: PSI-BLAST, GLOBAL, HMMER and RPS-BLAST provided examples of using the TAP-k and pooled ROC(n) scores to evaluate sequence retrieval algorithms. In particular, compelling examples using real data highlight the drawbacks of the pooled ROC(n) score, showing that it can produce evaluations skewing far from intuitive expectations. In contrast, the TAP-k satisfies most of the criteria desired in an ideal measure of retrieval efficacy.

Availability and implementation: The TAP-k web server and downloadable Perl script are freely available at http://www.ncbi.nlm.nih.gov/CBBresearch/Spouge/html.ncbi/tap/

Fig. 1.

An example of a PR graph and TAP curve. The E-values at each point are represented by the colors on the bar beneath.

Fig. 2.

Example retrieval list with relevant (blue ‘R’s) and irrelevant (red ‘I’s) records illustrating the j(E₀)-th relevant record, TPIRs and the sentinel record.

Fig. 3.

The distribution of EPQ versus E-value for PSI-BLAST retrieval over all queries in DB_344_Pfam. The dashed green line indicates the mean EPQ; the solid red line, the median EPQ; the top and bottom of the blue boxes, the first and third quartiles of the EPQ distribution; and the top and bottom whiskers, the maximum and minimum EPQ over all queries.

Fig. 4.

PSI-BLAST retrieval results for the homoserine dehydrogenase Pfam family searching in DB_344_Pfam. (a) Individual ROC₅₀ curves, along with the corresponding pooled ROC₅₀. Note that the pooled ROC curve is lower than both of the queries. This same condition continues until 203 irrelevant records. (b) PR curves (and their average) for the same retrieval results. The TAP for each is the AP (with the precision of last record repeated).

Fig. 5.

TAP curves against the E-value threshold E₀, for searching DB_331_CDD with each query from DB_8920_PDB in turn. Retrieval results for GLOBAL are represented with a solid green line; for HMMER_semi-global, with a long-dashed blue line; for HMMER_local, with a medium-dashed red line; and for RPS-BLAST, with a dotted black line. The arrows indicate the maximum TAP and its E-value threshold E₀*(A) for each algorithm A.