BLAST is the dominant survivor of a large crop of software products designed in response to the need for computationally efficient homology searches and sequence alignments. These heuristic algorithms give up the guarantee of absolutely correct answers in return for time and or space efficiency.

We used special purpose hardware (Field Programmable Gate Array boards implementing the Smith-Waterman algorithm) to calculate the optimal hits and alignments from a large set of DNA and amino acid data against a moderate sized (200,000 residue) query set. We evaluated these hits against several software implementations of heuristic algorithms (including BLAST) on two points: Accuracy of hit, and accuracy of alignment. Inaccurate or omitted hits can drive analysts in the wrong direction when annotating protein function. Inaccurate alignments can be used to generate incorrect numbers when calculating evolutionary distances and similar figures.

This presentation shows that with proper parameterization and knowledge of the limitations of the algorithms, heuristic techniques are acceptable substitutes for complete algorithms. We also show that simply using the defaults for these values can lead to misleading and incorrect results.

Read more about Speed at What Cost? by Chris Dwan in this article for The O'Reilly Network.