Hi,
I'm playing around with an exact matching algorithm that takes a long text T (which could be a genome) and a short pattern P (some query sequence) and generates a list of locations where the pattern occurs. I'm trying to extend it to generate locations of possible partial/inexact matches of the pattern. How do I then measure the performance of the algorithm when it comes to accuracy? How do I measure its sensitivity and selectivity?
•
written
by
Mike •
A classical approach to assess accurateness of algorithms (and also diagnostics tests) is by using ROC curves. The rate of false positives (or negatives) against true positives. The further away from the 45 degree line the better. Actually its the area under the curve that matters. Bigger is "usually" better.
Image Source: WikiPedia
Nice answer. Heng Li has a summary of ROC curves for next-gen sequencing aligners for the original problem space, with details on the code to generate them: http://lh3lh3.users.sourceforge.net/alnROC.shtml
First, a quick summary of sensitivity, specificity and accuracy; then some thoughts as to whether they apply in your case. I've linked here to Wikipedia entries, which are very good summaries of this topic.
To calculate sensitivity, specificity and accuracy, you require 4 things:
Sensitivity is then:
TP / (TP + FN)
And specificity is:
TN / (TN + FP)
Accuracy does not have a single, concise definition - it's measured in many ways, using various combinations of TP, FP, TN and FN. One measure is:
TP + TN / (TP + FP + TN + FN)
Another metric is positive predictive value, defined as:
TP / (TP + FP)
Your problem then, is to define what constitutes TP, FP, TN and FN. You can see that this is difficult to do when the algorithm is fuzzy pattern matching between strings. A perfect match to a known motif might be a TP, but what about a partial match - is that a TP? Similarly, what is a TN in this case? No matches when a known motif is not present? Clearly, the definition of a match changes depending on the query and target sequences. So I don't think that specificity and sensitivity are very useful measures in your case.
Since what you are doing sounds very similar to BLAST (and other pattern matching algorithms), I suggest you consult the literature and see how performance of those algorithms was evaluated.
I would like to add, that in this case there are a lot solutions with TP=1, FP=0. While it might be acceptable to have FP!=0 in a case involving uncertainty (e.g. classification) in pattern matching and sequence alignment it is not.
In addition to what Neil wrote and Casey's comment:
Yes there is an easy way of getting a gold standard, use an established algorithm, for
exact matching you are competing with: naive matching (iterating over the reference checking each position), Boyer-Moore, Knuth-Morris-Prat.
For fuzzy or approximate matching with Bitap variants, e.g. Manber-Wu. A way to generate your test-data is readily accessible in the for example in the unix tools grep (exact, not sure with algorithm it uses, BM?) and agrep (fuzzy). These tools can help you verify that you found all matches and only those.
Now, the problem is, you cannot beat these algorithms in accuracy at all, because they all find all possible matches (TP=100%) and only those (FP=0) (given the implementation is correct of course). Actually, you don't want to have any FP in string matching ever (for exact matching at least it is very easy to check), thus the specificity is always 1. What you could try with your own algorithm for purpose of practicing is to compare space and time complexity with the established ones or trade sensitivity for complexity.
Log in to answer this question.
Do you mean like BLAST?
do you have a gold standard to evaluate against?
Do you mean like grep/agrep? ;)
@niallhaslam: Similar to Blast, yes. @Casey: No, I'm actually looking for something like that, if it exists.
Mike, if you say similar to blast (a local alig), do you want do a sequence alignment? Note that alignment is different from pattern matching, please specify what you are going to achieve correctly, otherwise you will fail with your implementation attempt anyway. If dealing with global/local-alignments, then your 'gold-standard' is Needleman-Wunsh (global) or Smith-Waterman(local).
Please read this first http://en.wikipedia.org/wiki/String_searching_algorithm vs. http://en.wikipedia.org/wiki/Sequence_alignment
Thanks for the comments, Michael. My end goal is local alignment. I'm aiming to use the fuzzy matching to essentially give me the initial locations where I can use some method to find good local alignments. (Local DP comes to mind.)
Also, Michael, I'm concerned about S-W as a "gold standard". Yes it is optimal, but I'd like to run the algorithm on a long (perhaps genome-size) text and small query.
I do hope to have faster performance (although less accurate) with my algorithm though.