How can we say that BLAST is based on a heuristic algorithm, as after finding one common word in the query sequence and a database sequence it performs pairwise alignment by dynamic programming - which is an exhaustive algorithm? Also, BLAST provides quantitative analysis by giving bit scores and E-values. As it gives quantitative results, why do we say it is based on a "heuristic algorithm", such as 'word algorithm'?
$\begingroup$
$\endgroup$
1
asked Dec 26, 2015 at 4:16
-
$\begingroup$ I didn't quite get what you meant by "word algorithm" - if it's important to your question, you may want to expand on that point. $\endgroup$– R.M.Jan 13, 2016 at 18:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You might be confused about what "heuristic" means. "Heuristic" doesn't mean random or arbitrary, instead, an algorithm is termed "heuristic" if it employs a shortcut which means that it does not necessarily yield the theoretically best result.
For BLAST, this shortcut is the assumption of first matching the fixed-length words prior to extending the match. Hypothetically, there could be a query sequence and a database where the best scoring match for the query sequence doesn't contain any k-length sequences in common with the database sequence. In this case, BLAST would be unable to find that match. - So the heuristic portion of the algorithm isn't in the dynamic programming portion, it's in that first step of finding pairs which are to be aligned.
The failure of BLAST to find a match is likely to be rare, though, especially with short word lengths. If you find a decent match, it's highly likely that there is a 3-mer (5-mer, etc.) of identical sequence in the pair. But because it's not a guarantee, the use of k-mer word in the process means that BLAST is a heuristic algorithm.
The ability for BLAST to provide quality and statistical metrics is not limited by its heuristic nature. To build an e-value, you don't need to know that BLAST is able to find the absolute best match. Instead, you just need to be able to build a model of the sort of matches BLAST would find by spurious random chance, when applied to a similar database with no "true" matches. Similarly for bit-score. You don't need to know what the absolute best match would be, you just need to know how BLAST would behave on a hypothetical true-match-free database of similar properties.